C언어로 그래프를 구현합시다. 여기에서는 정점과 간선 집합인 그래프를 구현할 거예요.
동적으로 그래프를 생성하는 함수를 구현합시다.
Graph *New_Graph()
{
Graph *graph = 0;
그래프 형식 크기의 메모리를 할당합니다.
graph = (Graph *)malloc(sizeof(Graph));
정점을 보관할 동적 배열과 간선을 보관할 동적 배열을 생성한 후에 그래프를 반환합니다.
graph->vertexs = New_Array();
graph->edges = New_Array();
return graph;
}
동적으로 생성한 그래프를 소멸하는 함수를 구현합시다.
void Delete_Graph(Graph *graph)
{
그래프 내부에서는 간선을 동적으로 생성하므로 그래프를 소멸하는 과정에서 간선들도 소멸해야 합니다. 따라서 간선을 순차적으로 접근하기 위한 반복자 변수를 선언할게요.
Iterator seek = 0, end = 0;
Edge *edge = 0;
간선을 보관한 동적 배열의 시작과 끝을 구합니다.
seek = Array_Begin(graph->edges);
end = Array_End(graph->edges);
순차적으로 보관한 간선을 참조하여 메모리를 해제합니다.
for(seek = seek; seek != end; ++seek)
{
edge = (Edge *)(*seek);
free(edge);
}
정점을 보관하는 동적 배열과 간선을 보관하는 동적 배열을 소멸한 이후에 자신을 소멸합니다.
Delete_Array(graph->vertexs);
Delete_Array(graph->edges);
free(graph);
}
그래프에 정점을 추가하는 함수를 구현합시다.
int Graph_AddVertex(Graph *graph,Vertex pt)
{
먼저 이미 존재하는 정점인지 확인합니다. 만약 존재한다면 0을 반환합니다.
if(Graph_ExistVertex(graph,pt))
{
return 0;
}
정점을 보관하고 1을 반환합니다.
Array_PushBack(graph->vertexs,(Element)pt);
return 1;
}
간선을 추가하는 함수를 구현합시다.
int Graph_AddEdge(Graph *graph,Vertex ep1, Vertex ep2, int weight)
{
먼저 두 개의 정점이 모두 그래프에 있는지 확인합니다.
if(Graph_ExistVertex(graph,ep1) && Graph_ExistVertex(graph,ep2))
{
Edge *edge = 0;
두 개의 정점 사이에 간선이 이미 있다면 0을 반환합니다.
if(Graph_ExistEdge(graph,ep1,ep2))
{
return 0;
}
두 개의 정점이 모두 존재하고 두 정점 사이에 간선이 없는 것을 확인했다면 간선을 동적으로 생성한 후에 보관합니다. 간선을 동적으로 생성하는 함수는 별도로 구현합시다.
edge = New_Edge(ep1,ep2,weight);
Array_PushBack(graph->edges,edge);
return 1;
}
두 개의 정점이 모두 포함하고 있지 않을 때는 0을 반환합니다.
return 0; }
동적으로 간선을 생성하는 함수를 구현합시다.
Edge *New_Edge(Vertex ep1, Vertex ep2, int weight)
{
Edge *edge = 0;
동적으로 메모리를 할당합니다.
edge = (Edge *)malloc(sizeof(Edge));
입력 인자로 전달받은 값으로 설정한 후에 간선을 반환합니다.
edge->ep1 = ep1;
edge->ep2 = ep2;
edge->weight = weight;
return edge;
}
그래프에 특정 정점이 존재하는지 확인하는 함수를 구현합시다.
int Graph_ExistVertex(Graph *graph,Vertex pt)
{
Iterator seek = 0, end = 0;
Vertex stored_pt = 0;
정점을 보관하는 동적 배열의 시작과 끝을 구합니다.
seek = Array_Begin(graph->vertexs);
end = Array_End(graph->vertexs);
순차적으로 이동하면서 보관한 정점을 구합니다.
for(seek = seek; seek != end; ++seek)
{
stored_pt = (Vertex)(*seek);
만약 보관한 정점과 입력 인자로 받은 정점을 비교하였을 때 차이가 없으면 존재하는 것이므로 1을 반환합니다.
if(strcmp(stored_pt,pt)==0)
{
return 1;
}
}
끝까지 찾아도 없으면 0을 반환합니다.
return 0; }
그래프에 특정 간선이 존재하는지 확인하는 함수를 작성합시다.
int Graph_ExistEdge(Graph *graph,Vertex ep1, Vertex ep2)
{
Iterator seek = 0, end = 0;
Edge *stored_eg = 0;
간선을 보관하는 동적 배열의 시작과 끝을 구합니다.
seek = Array_Begin(graph->edges);
end = Array_End(graph->edges);
순차적으로 이동하면서 보관한 간선을 구합니다.
for(seek = seek; seek != end; ++seek)
{
stored_eg = (Edge *)(*seek);
만약 보관한 간선에 입력 인자로 받은 두 개의 정점을 포함하고 있으면 두 정점 사이의 간선이 있는 것이므로 1을 반환합니다.
if(Edge_Include(stored_eg,ep1)&&Edge_Include(stored_eg,ep2))
{
return 1;
}
}
끝까지 찾아도 없으면 0을 반환합니다.
return 0; }
그래프의 정보를 출력하는 함수를 구현합시다.
void Graph_View(Graph *graph)
{
그래프는 정점과 간선의 집합입니다. 따라서 정점 목록을 출력하는 함수와 간선 목록을 출력하는 함수를 호출합시다.
Graph_ViewVertexs(graph);
Graph_ViewEdges(graph);
}
정정 목록을 출력하는 함수를 구현합시다.
void Graph_ViewVertexs(Graph *graph)
{
정점 목록을 출력하기 위해서는 반복자를 이용하여 순차적으로 접근해야 합니다. 이에 필요한 변수를 선언합니다.
Iterator seek = 0, end = 0;
Vertex pt = 0;
먼저 정점 개수를 출력합시다.
printf("정점 개수:%d\n",graph->vertexs->usage);
정점을 보관하는 동적 배열의 시작과 끝을 구합니다.
seek = Array_Begin(graph->vertexs);
end = Array_End(graph->vertexs);
순차적으로 보관한 정점을 구하여 콘솔 화면에 출력합니다.
for(seek = seek; seek != end; ++seek)
{
pt = (Vertex)(*seek);
printf("%s\n",pt);
}
}
간선 목록을 출력하는 함수도 구현합시다.
void Graph_ViewEdges(Graph *graph)
{
Iterator seek = 0, end = 0;
Edge *edge = 0;
간선 개수를 출력합시다.
printf("간선 개수:%d\n",graph->edges->usage);
간선을 보관하는 동적 배열의 시작과 끝을 구합니다.
seek = Array_Begin(graph->edges);
end = Array_End(graph->edges);
순차적으로 이동하여 간선을 구합니다.
for(seek = seek; seek != end; ++seek)
{
edge = (Edge *)(*seek);
간선의 두 정점과 무게(거리)를 출력합니다.
printf("(%s ,%s):%d\n",edge->ep1,edge->ep2,edge->weight);
}
}
이번에는 특정 정점의 이웃 정점 목록을 구하는 함수를 작성합시다.
void Graph_FindNeighvor(Graph *graph,Vertex ep, Array *neighvor)
{
특정 정점과 이웃하는 정점 목록을 구하려면 간선 집합에서 해당 정점을 끝점으로 하는 간선을 찾아야 합니다. 이를 위해 반복자와 보관한 간선을 기억할 변수를 선언합시다.
Iterator seek = 0, end = 0;
Edge *edge = 0;
간선을 보관하는 동적 배열의 시작과 끝을 구합니다.
seek = Array_Begin(graph->edges);
end = Array_End(graph->edges);
순차적으로 이동하면서 보관한 간선을 구합니다.
for(seek = seek; seek != end; ++seek)
{
edge = (Edge *)(*seek);
만약 해당 간선에 입력 인자로 받은 정점을 포함하고 있다면 나머지 한 점이 이웃하는 정점입니다. 간선에 특정 정점을 포함하는지 확인하는 함수는 별도로 구현합시다.
if(Edge_Include(edge,ep))
{
Vertex opt;
나머지 정점을 구합니다. 이 부분은 별도의 함수로 작성합시다.
opt = Edge_AnOther(edge,ep);
구한 정점을 이웃 목록에 추가합니다.
Array_PushBack(neighvor,(Element)opt);
}
}
}
간선에 특정 정점을 포함하는지 확인하는 함수를 작성합시다.
int Edge_Include(Edge *edge,Vertex pt)
{
간선의 두 정점 중에 입력 인자로 받은 정점과 문자열 비교했을 때 차이가 없는 정점이 있으면 포함하고 있는 것입니다.
return (strcmp(edge->ep1,pt)==0)||(strcmp(edge->ep2,pt)==0); }
간선에 특정 정점이 아닌 나머지 정점을 구하는 함수를 작성합시다.
Vertex Edge_AnOther(Edge *edge,Vertex pt)
{
만약 간선의 한 정점과 비교하여 차이가 없다면 나머지 정점을 반환합니다.
if(strcmp(edge->ep1,pt)==0)
{
return edge->ep2;
}
if(strcmp(edge->ep2,pt)==0)
{
return edge->ep1;
}
입력 인자로 받은 정점이 간선의 두 정점과 비교하여 차이가 있다면 빈 문자열을 반환합시다.
return ""; }
그래프의 두 정점 사이의 간선의 무게(거리)를 찾는 함수를 작성합시다.
int Graph_GetWeight(Graph *graph,Vertex ep1, Vertex ep2)
{
Iterator seek = 0, end = 0;
Edge *edge = 0;
간선 집합의 시작과 끝을 구합니다.
seek = Array_Begin(graph->edges);
end = Array_End(graph->edges);
순차적으로 이동하면서 보관한 간선을 구합니다.
for(seek = seek; seek != end; ++seek)
{
edge = (Edge *)(*seek);
만약 해당 간선에 입력 인자로 받은 두 정점을 포함하고 있다면 두 정점 사이의 간선입니다. 이 때는 간선의 무게(거리)를 반환합니다.
if(Edge_Include(edge,ep1)&&Edge_Include(edge,ep2))
{
return edge->weight;
}
}
두 정점을 포함하는 간선을 찾지 못하면 음수를 반환합니다.
return -1; }
참고로 그래프에서 정점과 정점 사이의 거리를 비중 혹은 무게로 많이 표시합니다. 이 책에서 매 번 간선의 거리를 말할 때 무게(거리)라고 표현하고 있는데 논리적으로 보면 거리가 맞는 말이고 일반적으로 그래프에서 사용하는 용어는 비중 혹은 무게로 말할 때가 많기 때문입니다.