[C언어 자료구조] 8.1 그래프 설계

8.1 그래프 설계

---

 정점은 문자열 리터럴 상수로 표현하기로 할게요. 사용하기 쉽게 const char * 형식을 Vertex이름으로 타입 재지정할게요.

typedef const char * Vertex;

 

 그리고 간선은 간선의 끝에 있는 두 개의 정점과 무게(거리)를 멤버로 정의할게요.

typedef struct _Edge Edge;

struct _Edge

{

    Vertex ep1;

    Vertex ep2;

    int weight;

};

 

 그래프는 정점을 보관하는 컬렉션과 간선을 보관하는 컬렉션으로 구성할게요. 여기에서는 동적 배열을 사용합시다.

typedef struct _Graph Graph;

struct _Graph

{

    Array *vertexs;

    Array *edges;

};

 

 동적으로 그래프를 생성하는 함수와 소멸하는 함수를 제공합시다.

Graph *New_Graph();

void Delete_Graph(Graph *graph);

  

 그래프에 정점을 추가하는 함수를 제공합시다. 이 함수에서는 이미 존재하는 정점일 때는 추가하지 않고 0을 반환하며 없을 때 추가하고 1을 반환합시다.

int Graph_AddVertex(Graph *graph,Vertex pt);

 

 그래프에 간선을 추가하는 함수를 제공합시다. 입력 인자로 그래프와 두 개의 정점과 무게(거리)를 받아 두 개의 정점이 존재하는지 확인하고 두 정점 사이의 간선이 없는지 확인한 이후에 간선을 동적으로 생성하여 보관하기로 합시다. 만약 두 개의 정점 중에 존재하지 않는 정점이 있거나 이미 두 정점 사이에 간선이 있을 때는 0을 반환하게 구현합시다.

int Graph_AddEdge(Graph *graph,Vertex ep1, Vertex ep2, int weight);

 

 그래프에 특정 정점이 존재하는지 확인하는 함수를 제공합시다.

int Graph_ExistVertex(Graph *graph,Vertex pt);

 

 두 개의 정점 사이에 간선이 있는지 확인하는 함수를 제공합시다.

int Graph_ExistEdge(Graph *graph,Vertex ep1, Vertex ep2);

 

 그래프 정보를 출력하는 함수를 제공합시다. 그리고 정점 목록과 간선 목록을 출력하는 함수도 제공합시다.

void Graph_View(Graph *graph);

void Graph_ViewVertexs(Graph *graph);

void Graph_ViewEdges(Graph *graph);

 

 특정 정점에서 갈 수 있는 이웃 정점 목록을 찾는 함수를 제공합시다. 입력 인자로 그래프와 정점과 함께 이웃 정점 목록을 보관할 동적 배열을 받게 합니다.

void Graph_FindNeighvor(Graph *graph,Vertex ep, Array *neighvor);

 

 두 정점 사이의 간선의 무게(거리)를 구하는 함수를 제공합시다. 만약 두 정점 사이에 간선이 없을 때는 음수(-1)를 반환하게 할게요.

int Graph_GetWeight(Graph *graph,Vertex ep1, Vertex ep2);