7.2.1 그래프 설계(DFS 알고리즘에 사용할 그래프)

그래프를 표현하는 방법은 다양합니다. 이차원 배열을 이용해서 인접 행렬로 표현하는 방법도 있고 정점과 간선의 집합으로 표현하는 방법도 있습니다.

이차원 배열을 이용해서 인접 행렬로 표현하는 방법은 정점의 개수가 n일 때 행과 열이 n인 이차원 배열을 만들고 두 개의 정점 사이의 거리를 배열의 항목 값으로 설정하는 형태로 작성합니다. 이 방법은 다른 책과 인터넷 검색 등을 통해 어렵지 않게 찾아볼 수 있을 것입니다. 하지만 그래프의 정점의 개수가 많으면 실제 정점과 정점 사이에 존재하지 않는 간선을 위한 부분이 전체의 많은 부분을 차지하여 메모리 효율과 수행 속도가 나빠질 수 있습니다.

이 책에서는 정점과 간선의 집합을 이용하여 그래프를 나타내는 방법을 사용할게요. 구현 비용은 인접 행렬을 이용하는 방법보다 어려울 수 있지만 유연성과 확장성 면 등에서 비교 우위에 있고 다른 책이나 인터넷 검색 등에서 인접 행렬로 구현한 것보다 쉽게 찾을 수 없기에 이 방법으로 소개할게요.

정점은 문자열 리터럴 상수로 표현하기로 할게요. 사용하기 쉽게 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);

자료구조와 알고리즘