[C언어 알고리즘] 6.2.1 그래프 설계(DFS 알고리즘에 사용할 그래프)

[C언어 알고리즘] 6.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);