-
그래프를 소개합니다
오일러의 도구
"다리를 한 번씩만 건너 쾨니히스베르크의 모든 지역을 순회할 수 있을까?" 라는 문제를 해결하기 위해 오일러는 그래프를 고안해내고, 이를 도구로 이용하여 불가능함을 밝혀냈다.
오일러는 위의 그림을 좀 더 단순하게 만들어 각 육지를 정점(vertex)으로, 각 육지를 잇는 다리를 간선(edge)으로 표시했다. 이렇게 하면 쾨니히스베르크의 네 육지와 7개의 다리를 4개의 정점과 7개의 간선으로 나타낼 수 있다.
쾨니히스베르크의 다리 문제는 한붓그리기 문제가 됐다. 쾨니히스베르크의 그래프에서 정점 A,B,C,D 네 개는 모두가 홀수개의 선으로 연결되어 있기 때문에 한붓그리기가 불가능하고 따라서 7개의 다리를 한 번씩만 건너서 쾨니히스베르크의 모든 육지를 밟은 것을 불가능하다.
그래프는 오늘날까지 수 백년 동안 수학, 과학, 공학, 사회, 경제학에 이르기까지 폭넓은 분야에 걸쳐 응용되고 있다.
그래프의 정의
그래프는 '정점의 모음'과 이 정점을 잇는 '간선의 모음'과의 결합이다.
"정점의 집합을 V, 간선의 집합을 E, 그리고 그래프를 G라고 했을 때, G = (V, E)이다"
정점 몇개 자체로는 아무것도 아니지만 이들이 간선으로 인해 서로 연결될 때 '관계'가 형성되고 이로 인해 그래프가 형성된다.
간선으로 연결되어 있는 두 정점을 가리켜 '인접(adjacent)', 또는 이웃관계에 있다고 한다. (A,B), (A,D), (A,E), (B,C), (B,E), (C,D)가 서로 이웃관계다.
간선을 통해 서로 이웃이 된 정점은 그래프 안에서의 길을 형성하기도 한다. 정점 A에서 정점 C까지는 A,B,C가 하나의 '경로(path)'를 이루고 A,D,C가 또 하나의 경로를 형성한다. 경로는 길이를 가지는데 길이는 정점과 정점 사이에 있는 간선의 수로 정의된다. 경로 A,B,C 사이에는 간선이 (A,B)와(B,C) 두 개가 있으니 길이가 2가 된다.
어느 경로가 정점 하나를 두 번 이상 거치도록 되어 있다면 이 경로를 일컬어 '사이클(Cycle)'이라고 한다. A,B,C,D,A
간선 때문에 이웃이 생기고 길(경로)이 생기며 사이클이 생긴다. 간선이 방향성을 가지면 방향성 그래프(Directed Graph)가 되고, 간선에 방향성이 없으면 무방향성 그래프(Undirected Graph)가 된다.
그래프 세계에는 '연결성(Connectivity)'라는 단어가 있다. 무방향성 그래프 내의 두 정점 사이에 경로(path)가 존재하면 '이 두 정점이 연결되어 있다'고 한다. 그리고 그래프 내의 각 정점들이 다른 모든 정점들과 연결되어 있으면 '이 그래프는 연결되었다'라고 한다. 연결성은 정점과 그래프 양쪽에 사용될 수 있으면서도 어느 쪽에 사용되느냐에 따라 의미는 조금 달라진다고 할 수 있다.
-
그래프를 어떻게 표현할 것인가?
정점의 집합은 배열이나 링크드 리스트, 어떤 자료구조를 사용하더라도 쉽게 표현이 가능하다. 문제는 간선의 집합을 표현한느 방법이다. 간선은 정점과 정점이 '인접' 관계에 있음을 나타내는 존재이다. 그래프의 표현 문제는 "간선, 즉 정점과 정점의 인접 관계를 어떻게 나타내는가?"의 문제이다.
인접 행렬
인접 행렬(Adjacency Matrix)이란, 이름이 가리키는 것처럼 정점끼리의 인접 관계를 나타내는 행렬이다. 그래프의 정점의 수를 N이라고 한다면, N*N 크기의 행렬을 만들어 행렬의 각 원소를 한 정점과 또 다른 정점이 인접해 있는 경우(즉, 정점 사이에 간선이 존재하는 경우)에는 1로 표시하고, 인접해 있지 않은 경우에는 0으로 표시하는 것이다.
이 그래프의 정점 1은 젖엄 2,3,4,5와 인접해 있으니 (1,2), (1,3), (1,4), (1,5)는 모두 1이다. 자기 자신과 인접 관계를 만들 수 없으니 (1,1)은 0이고 (2,2), (3,3), (4,4), (5,5)도 모두 0이다. 이런식으로 나머지 정점들에 대해서도 인접 표시를 하면 아래와 같은 행렬을 얻을 수 있다.
위 인접 행렬이 주 대각선에 대해 대칭(Symmetric)을 이루고 있다. 그래프가 무 방향성인 경우에는 인접 행렬은 이처럼 주 대각선에 대해 대칭을 이루는 것이 특징이다.
방향성 그래프에서의 정점은 자신이 직접 간선을 통해 가리키고 있는 정점에 대해서만 인접해 있다고 표현할 수 있다.
인접 리스트
인접 리스트(Adjacency List)는 그래프 내의 각 정점의 인접 관계를 표현하는 리스트이다. 각 정점을 자신과 인접해 있는 모든 정점의 목록을 리스트로 관리하도록 하는 것이다.
인접 정점들끼리 리스트로 연결한 후 각 정점에 연결한다.
인접 행렬 vs 인접 리스트
인접 행렬을 이용하면 정점 간의 인접 여부를 빠르게 알 수 있지만 인접 관계를 행렬 형태로 저장하기 위해 사용하는 메모리의 양이 '정점 크기 x N2'에 이른다는 단점이 있다.
인접 리스트는 정점 간의 인접 여부를 알아내기 위해 인접 리스트를 타고 순차 탐색을 해야 한다는 단점이 있는 반명에, 정점과 간선의 삽입이 빠르고 인접 관계를 표시하는 리스트에 사용되는 메모리의 양이 적다는 장점이 있다.
따라서 어느 자료구졸르 선택할 것인가는 프로그램의 목적에 따라 결정하는 것이 좋다.
인접 리스트의 구현
인접 리시트에서는 정점, 간선, 그리고 이 두 가지의 집합을 쥐고 있어야 하는 그래프를 위한 구조체가 필요하다.
-
정점(vertex) 구조체
next는 다음 정점을 가리키는 포인터
adjacencyList는 인접 정점의 목록에 대한 포인터
visited는 그래프 순회 알고리즘에서 사용할 필드
index는 정점의 인덱스를 나타냄
typedef struct tagVertex
{
ElementType data;
int visited;
int index;
tagVertex* next;
tagEdge* adjacencyList;
}VERTEX;
-
간선(Edge) 구조체
from과 target은 각각 간선의 시작(from)정점과 끝(target)정점을 나타냄
next는 다음 간선을 가리키는 포인터
weight 필드는 간선의 가중치
typedef struct tagEdge
{
int weight;
tagEdge* next;
VERTEX* from;
VERTEX* target;
}EDGE;
-
그래프(Graph) 구조체
vertices는 정점의 목록에 대한 포인터
vertexCount는 정점의 갯수
typedef struct tagGraph
{
VERTEX* vertices;
int vertexCount;
}GRAPH;
인접 리스트 예제 프로그램
- 예제 Graph.h
-
|
#ifndef _GRAPH_H__ #define _GRAPH_H__
#include <stdio.h> #include <stdlib.h>
enum visitMode { Visited, NotVisited };
typedef int ElementType; // 전방 선언 struct tagEdge;
typedef struct tagVertex { ElementType data; int visited; int index;
tagVertex* next; tagEdge* adjacencyList; }VERTEX;
typedef struct tagEdge { int weight; tagEdge* next; VERTEX* from; VERTEX* target; }EDGE;
typedef struct tagGraph { VERTEX* vertices; int vertexCount; }GRAPH;
GRAPH* createGraph(void); void destroyGraph(GRAPH* g);
VERTEX* createVertex(ElementType data); void destroyVertex(VERTEX* v);
EDGE* createEdge(VERTEX* from, VERTEX* target, int weight); void destroyEdge(EDGE* e);
void addVertex(GRAPH* g, VERTEX* v); void addEdge(VERTEX* v, EDGE* e); void printGraph(GRAPH* g);
#endif |
- 예제 Graph.c
|
#include "Graph.h"
GRAPH* createGraph(void) { GRAPH* graph = (GRAPH*)malloc(sizeof(GRAPH)); graph->vertices = NULL; graph->vertexCount = 0;
return graph; } void destroyGraph(GRAPH* g) { while( g->vertices != NULL ) { VERTEX* v = g->vertices->next; destroyVertex(g->vertices); g->vertices = v; }
free(g); }
VERTEX* createVertex(ElementType data) { VERTEX* v = (VERTEX*)malloc(sizeof(VERTEX));
v->data = data; v->next = NULL; v->adjacencyList = NULL; v->visited = NotVisited; v->index = -1;
return v; } void destroyVertex(VERTEX* v) { while( v->adjacencyList != NULL ) { EDGE* e = v->adjacencyList->next; destroyEdge(v->adjacencyList); v->adjacencyList = e; }
free(v); }
EDGE* createEdge(VERTEX* from, VERTEX* target, int weight) { EDGE* e = (EDGE*)malloc(sizeof(EDGE)); e->from = from; e->target = target; e->next = NULL; e->weight = weight;
return e; } void destroyEdge(EDGE* e) { free(e); }
void addVertex(GRAPH* g, VERTEX* v) { VERTEX* vertexList = g->vertices;
if( vertexList == NULL ) { g->vertices = v; } else { while( vertexList->next != NULL ) { vertexList = vertexList->next; } vertexList->next = v; } v->index = g->vertexCount++; } void addEdge(VERTEX* v, EDGE* e) { if( v->adjacencyList == NULL ) { v->adjacencyList = e; } else { EDGE* adjacencyList = v->adjacencyList;
while( adjacencyList->next != NULL ) { adjacencyList = adjacencyList->next; } adjacencyList->next = e; } } void printGraph(GRAPH* g) { VERTEX* v = NULL; EDGE* e = NULL;
if( (v = g->vertices) == NULL ) return;
while( v != NULL ) { printf("%c : ", v->data);
if( (e = v->adjacencyList) == NULL ) { v = v->next; printf("\n"); continue; }
while( e != NULL ) { printf("%c[%d] ", e->target->data, e->weight); e = e->next; } printf("\n");
v = v->next; } printf("\n"); } |
- 예제 main.c
|
#include "Graph.h"
void main(void) { // 그래프 생성 GRAPH* g = createGraph();
// 정점 생성 VERTEX* v1 = createVertex('1'); VERTEX* v2 = createVertex('2'); VERTEX* v3 = createVertex('3'); VERTEX* v4 = createVertex('4'); VERTEX* v5 = createVertex('5');
// 그래프에 정점을 추가 addVertex(g, v1); addVertex(g, v2); addVertex(g, v3); addVertex(g, v4); addVertex(g, v5);
// 정점과 정점을 간선으로 잇기 addEdge(v1, createEdge(v1, v2, 0)); addEdge(v1, createEdge(v1, v3, 0)); addEdge(v1, createEdge(v1, v4, 0)); addEdge(v1, createEdge(v1, v5, 0));
addEdge(v2, createEdge(v2, v1, 0)); addEdge(v2, createEdge(v2, v3, 0)); addEdge(v2, createEdge(v2, v5, 0));
addEdge(v3, createEdge(v3, v1, 0)); addEdge(v3, createEdge(v3, v2, 0));
addEdge(v4, createEdge(v4, v1, 0)); addEdge(v4, createEdge(v4, v5, 0));
addEdge(v5, createEdge(v5, v1, 0)); addEdge(v5, createEdge(v5, v2, 0)); addEdge(v5, createEdge(v5, v4, 0));
printGraph(g);
// 소멸 destroyGraph(g); } |
-
그래프 순회 : 그래프를 따라 산책하기
그래프에서는 특정 데이터를 갖고 있는 정점을 탐색하는 일뿐 아니라 모든 정점을 순회하는 것마저 쉽지 않다.
그래프를 순회하는 대표적인 기법으로 너비 우선 탐색과 깊이 우선 탐색 두 가지가 있다. 너비 우선 탐색을 알아야 그래프에서 최단 경로를 찾는 알고리즘을 익힐 수 있고, 깊이 우선 탐색을 알아야 그래프를 정렬하는 알고리즘을 익힐 수 있다.
깊이 우선 탐색
깊이 우선 탐색(Depth First Search)은 길이 나오지 않을 때까지 그래프의 정점을 타고 깊이 들어가다가 더 이상 방문해왔던 정점 말고는 다른 이웃을 갖고 있지 않은 정점을 만나면 뒤로 돌아와 다른 경로로 뻗어 있는 정점을 타고 방문을 재개하는 방식으로 동작한다.
- 시작 정점을 밟은 후 이 정점을 '방문했음'으로 표시한다
- 그리고 이 정점과 이웃하고 있는 정점(즉, 인접 정점)중에 아직 방문하지 않은 곳을 선택하여 이를 시작 정점으로 삼아 다시 깊이 우선 탐색을 시작한다.
- 정점에 더 이상 방문하지 않은 인접 정점이 없으면 이전 정저므로 돌아가서 2단계를 수행한다.
-
이전 정점으로 돌아가도 더 이상 방문할 이웃이 없다면 그래프의 모든 정점을 방문했다는 뜻이다. 이제 탐색을 종료한다.
void DFS(VERTEX* v)
{
EDGE* e = NULL;
printf("%d ", v->data);
// 방문함 표시
v->visited = Visited;
e = v->adjacencyList;
// 현재 정점의 모든 인접 정점에 대해 DFS()재귀 호출
while( e != NULL )
{
if( e->target != NULL && e->target->visited = NotVisited)
DFS(e->target);
e = e->next;
}
}
너비 우선 탐색
너비 우선 탐색(Breadth First Search)에서는 시작 정점을 지나고 나면 깊이가 1인 모든 정점을 방문하고, 그 다음에는 깊이가 2인 모든 정점을 방문한다. 이런 식으로 한 단계씩 깊이를 더해가며 해당 깊이에 있는 모든 정점들을 방문해 나가다가 나중에는 더 이상 방문할 곳이 없다면 탐색을 종료한다.
깊이 0에 있는 정점을 1밖에 없다. 1을 제일 먼저 방문한다. 깊이 1에 위치하고 있는 정점은 2,3 이므로 두 정점을 방문한다. 깊이 2에 있는 정점은 4,5,6이다. 이 정점들을 방문한 후에 깊이 3에 있는 정점 7에 방문한다. 그리고 깊이 4에 존재하는 정점은 없으므로 탐색을 종료한다.
너비 우선 탐색은 탐색을 도와줄 큐가 따로 필요하다. 너비 우선 탐색은 다음과 같은 과정으로 동작한다.
- 시작 정점을 '방문했음'으로 표시하고 큐에 삽입(Enqueue)한다
- 큐로부터 정점을 제거(Dequeue)한다. 제거한 정점이 이웃하고 있는 인접 정점 중 아직 방문하지 않은 곳들을 '방문했음'으로 표시하고 큐에 삽입한다
- 큐가 비게 되면 탐색이 끝난 것이다. 따라서 큐가 빌 때까지 2의 과정을 반복한다.
void BFS(VERTEX* v LinkedQueue* queue)
{
EDGE* e = NULL;
printf("%d ", v->data);
v->visited = Visited;
// 시작 정점을 큐에 삽입
LQ_enqueue(&queue, LQ_createNode(v));
// 큐가 비어 있는지 검사
while( !LQ_isEmpty(queue))
{
// 큐에서 전단을 제거
NODE* pop = LQ_dequeue(&queue);
v = pop->data;
e = v->adjacencyList;
// 큐에서 꺼낸 정점에 인접 정점을 조사
while( e != NULL )
{
v = e->target;
// 미방문 정점만 방문
if( v != NULL && v->visited = NotVisited )
{
printf("%d ", v->data);
v->visited = Visited;
LQ_enqueue( &queue, LQ_createNode(v));
}
e = e->next;
}
}
}
그래프 순회 예제 프로그램
- 예제 GraphTraversal.h
|
#ifndef _GRAPHTRAVERSAL_H__ #define _GRAPHTRAVERSAL_H__
#include "Graph.h" #include "LinkedQueue.h"
void DFS(VERTEX* v); void BFS(VERTEX* v, LinkedQueue* queue);
#endif |
- 예제 GraphTraversal.c
|
#include "GraphTraversal.h"
void DFS(VERTEX* v) { EDGE* e = NULL;
printf("%d ", v->data);
v->visited = Visited;
e = v->adjacencyList;
while( e != NULL ) { if( e->target != NULL && e->target->visited == NotVisited ) { DFS(e->target); } e = e->next; } }
void BFS(VERTEX* v, LinkedQueue* queue) { EDGE* e = NULL;
printf("%d ", v->data); v->visited = Visited;
// 큐에 삽입 LQ_enqueue(queue, LQ_createNode(v));
while( !LQ_isEmpty(queue) ) { NODE* pop = LQ_dequeue(queue); v = pop->data; e = v->adjacencyList;
while( e != NULL ) { v = e->target;
if( v != NULL && v->visited == NotVisited ) { printf("%d ", v->data); v->visited = Visited; LQ_enqueue(queue, LQ_createNode(v)); } e = e->next; } } } |
- 예제 main.c
|
#include "GraphTraversal.h"
void main(void) { int mode = 0;
GRAPH* graph = createGraph();
VERTEX* v1 = createVertex(1); VERTEX* v2 = createVertex(2); VERTEX* v3 = createVertex(3); VERTEX* v4 = createVertex(4); VERTEX* v5 = createVertex(5); VERTEX* v6 = createVertex(6); VERTEX* v7 = createVertex(7);
addVertex(graph, v1); addVertex(graph, v2); addVertex(graph, v3); addVertex(graph, v4); addVertex(graph, v5); addVertex(graph, v6); addVertex(graph, v7);
// 정점과 정점을 간선으로 잇기 addEdge(v1, createEdge(v1, v2, 0)); addEdge(v1, createEdge(v1, v3, 0));
addEdge(v2, createEdge(v2, v4, 0)); addEdge(v2, createEdge(v2, v5, 0));
addEdge(v3, createEdge(v3, v4, 0)); addEdge(v3, createEdge(v3, v6, 0));
addEdge(v4, createEdge(v4, v5, 0)); addEdge(v4, createEdge(v4, v7, 0));
addEdge(v5, createEdge(v5, v7, 0));
addEdge(v6, createEdge(v6, v7, 0));
printf("Enter Traversal Mode(0:DFS, 1:BFS) : "); scanf("%d", &mode);
if( mode == 0 ) { // 깊이 우선 탐색(Depth First Search) DFS(graph->vertices); } else { LinkedQueue* queue; LQ_createQueue(&queue);
// 너비 우선 탐색(Breadth First Search) BFS(v1, queue);
LQ_destroyQueue(queue); }
destroyGraph(graph); } |
-
위상 정렬
위상 : 어떤 사물이 다른 사물과의 관계 속에서 가지는 위치나 상태
위상 정렬(Topological Sort)이란 정점들의 위치 속성(앞/뒤)를 정렬하는 알고리즘
위상 정렬이 가능하려면 그래프에 방향성이 있어야하고, 그래프 내에 사이클이 없어야 한다. 이러한 그래프를 DAG(Directed Acyclic Graph)라고 한다.
그래프는 정점의 집합과 간선의 집합으로 이루어져 있다. 특히 간선은 정점과 정점 사이의 관계를 설명하는 역할을 수행한다. 두 정점이 이웃 또는 인접 관계에 있다는 사실뿐만 아니라 간선이 방향성을 가지는 경우에는 어느 정점이 선이고 어느 정점이 후인지도 설명한다. 정점은 두 가지 종류의 방향성 간선을 가질 수 있는 그 중 하나는 정점으로 들어가는 진입 간선(Incoming Edge)이고, 다른 하나는 진출 간선(Outgoing Edge)이다.
위상 정렬은 다음과 같은 과정을 거쳐 완성된다.
- 리스트를 하나 준비한다.
- 그래프에서 진입 간선이 없는 정점을 리스트에 추가하고, 해당 정점 자신과 진출 간선을 제거한다.
- 모든 정점에 대해 2번을 반복하고 그래프 내에 정점이 남아 있지 않으면 종료한다. 이때 리스트에는 위상 정렬된 그래프가 저장된다.
이 알고리즘과 똑같이 위상 정렬을 수행하지만 깊이 우선 탐색을 이용하여 위상 정렬을 할 수 있다.
- 리스트를 준비 한다.
- 그래프에 진입 간선이 없는 정점에 대해 깊이 우선 탐색을 시행하고, 탐색 중에 더 이상 옮겨갈 수 있는 인접 정점이 없는 정점을 만나면 이 정점을 리스트의 새로운 '헤드'로 입력한다.
- 2번을 반복하다 더 이상 방문할 정점이 없으면 깊이 우선 탐색을 종료한다. 깊이 우선 탐색이 끝난 후 리스트에는 위상 정렬된 그래프가 남는다.
위상 정렬 예제 프로그램
위상 정렬 예제는 Graph.h, Graph.c, LinkedList.h, LinkedList.c, TopologicalSort.h, TopologicalSort.c, main.c로 7개 파일로 이루어진다.
- 예제 TopologicalSort.h
|
#include "Graph.h" #include "LinkedList.h"
#ifndef TOPOLOGICALSORT_H #define TOPOLOGICALSORT_H
void TopologicalSort( Vertex* V, Node** List ); void TS_DFS( Vertex* V, Node** List );
#endif |
- 예제 TopologicalSort.c
|
#include "TopologicalSort.h"
void TopologicalSort( Vertex* V, Node** List ) { while ( V != NULL && V->Visited == NotVisited ) { TS_DFS( V, List );
V = V->Next; } }
void TS_DFS( Vertex* V, Node** List ) { Node* NewHead = NULL; Edge* E = NULL;
V->Visited = Visited;
E = V->AdjacencyList;
while ( E != NULL ) { if ( E->Target != NULL && E->Target->Visited == NotVisited ) TS_DFS( E->Target, List );
E = E->Next; }
printf("%c\n", V->Data );
NewHead = SLL_CreateNode( V ); SLL_InsertNewHead( List, &NewHead ); } |
- 예제 main.c
|
#include "Graph.h" #include "TopologicalSort.h"
int main( void ) { Node* SortedList = NULL; Node* CurrentNode = NULL;
/* 그래프 생성 */ Graph* graph = CreateGraph();
/* 정점 생성 */
Vertex* A = CreateVertex( 'A' ); Vertex* B = CreateVertex( 'B' ); Vertex* C = CreateVertex( 'C' ); Vertex* D = CreateVertex( 'D' ); Vertex* E = CreateVertex( 'E' ); Vertex* F = CreateVertex( 'F' ); Vertex* G = CreateVertex( 'G' ); Vertex* H = CreateVertex( 'H' );
/* 그래프에 정점을 추가 */ AddVertex( graph, A ); AddVertex( graph, B ); AddVertex( graph, C ); AddVertex( graph, D ); AddVertex( graph, E ); AddVertex( graph, F ); AddVertex( graph, G ); AddVertex( graph, H );
/* 정점과 정점을 간선으로 잇기 */ AddEdge( A, CreateEdge( A, C, 0 ) ); AddEdge( A, CreateEdge( A, D, 0 ) );
AddEdge( B, CreateEdge( B, C, 0 ) ); AddEdge( B, CreateEdge( B, E, 0 ) );
AddEdge( C, CreateEdge( C, F, 0 ) );
AddEdge( D, CreateEdge( D, F, 0 ) ); AddEdge( D, CreateEdge( D, G, 0 ) );
AddEdge( E, CreateEdge( E, G, 0 ) );
AddEdge( F, CreateEdge( F, H, 0 ) );
AddEdge( G, CreateEdge( G, H, 0 ) );
/* 위상 정렬 */ TopologicalSort( graph->Vertices, &SortedList );
printf("Topological Sort Result : ");
CurrentNode = SortedList;
while ( CurrentNode != NULL ) { printf("%C ", CurrentNode->Data->Data ); CurrentNode = CurrentNode->NextNode; } printf("\n");
/* 그래프 소멸 */ DestroyGraph( graph );
return 0; } |
-
최소 신장 트리
지금부터는 간선에 '가중치(Weight)'라는 새로운 속성이 부여된다.
간선이 가중치를 가지면 그래프로 표현할 수 있는 것이 훨씬 다양해진다.
Spanning Tree(신장 트리)의 Spanning은 떨어져 있는 둘 사이를 다리 등으로 연결한다는 뜻으로 사용된다. 즉 신장 트리는 그래프의 모든 정점을 연결하는 트리이다.
그래프는 사이클을 형성하는 간선만 제거하면 트리로 변신한다.
최소 시장 트리(Minimum Spanning Tree)란 '최소 가중치 신장 트리'라고도 불린다. 각 간선이 갖고 있는 가중치의 합이 최소가 되는 신장 트리가 최소 신장 트리인 것이다.
프림 알고리즘
프림 알고리즘(Prim's Algorithm)은 로버트 프림이 고안한 그래프에서 최소 신장 트리를 만들어내는 알고리즘이다. 이 알고리즘이 최소 신장 트리를 만들어내는 과정은 다음과 같다.
- 그래프와 최소 신장 트리를 준비한다. 물론 이때의 최소 신장 트리는 노드가 하나도 없는 상태이다.
- 그래프에서 임의의 정점을 시작 정점으로 선택하여 최소 신장 트리의 루트 노드로 삽입한다.
- 최소 신장 트리에 삽입되어 있는 정점들과 이 정점들의 모든 인접 정점 사이에 있는 간선의 가중치를 조사한다. 간선 중에 가장 가중치가 작은 것을 골라 이 간선에 연결되어 있는 인접 정점을 최소 신장 트리에 삽입한다. 단, 새로 삽입되는 정점은 최소 신장 트리에 삽입되어 있는 기존의 노드들과 사이클을 형성해서는 안된다.
- 3번의 과정을 반복하다가 최소 신장 트리가 그래프의 모든 정점을 연결하게 되면 알고리즘을 종료한다.
B를 시작 정점으로 사용한다.
정점 B에 연결되어 있는 간선은 B-A, B-C, B-F의 세 개가 있는데 이중 가장 가중치가 작은 간선은 35인 B-A이므로 A를 최소 신장 트리에 추가한다.
그리고 최소 신장 트리에 등록되어 있는 노드는 B,A 2개가 되었다. 이 노드들에 연결되어 있는 간선들은 B-C, B-F, A-E인데 이중에서 '최소 가중치'를 가진 간선을 찾는다. B-C의 가중치가 126으로 작으니 C를 최소 신장 트리에 추가한다.
C-F 간선은 C-F 간선이 B-C-F를 통과하는 사이클을 형성시키기 때문에 사이클이 형성되는 것을 막기 위해 B-F와 C-F 둘 중 하나를 제외해야 하는데 그 중 C-F를 선택해서 제외시킨 것은 B-F가 가진 가중치가 C-F의 것보다 작기 때문이다.
그리고 이번 단계에서 가중치르르 조사할 간선이 모두 네개(A-E, B-F, C-D, C-G)이다. 이중에서 가장 가중치가 작은 간선은 C-D(117)이므로 D를 최소 신장 트리에 추가한다.
최소 가중치를 조사할 간선 B-F, C-G, A-E 중에서 가장 가중치가 작은 간선은 B-F(150)이므로 F를 최소 신장 트리에 추가한다.
F가 최소 신장 트리에 추가됨으로써 조사 대상에 큰 변화가 생긴다. A-E 간선은 가중치가 더 작은 F-E 간선에 의해, 또 C-G 간선 역시 가중치가 더 작은 F-G 간선에 의해 조사 대상에서 제거되었다. 그리고 F-H 간선이 새로 추가되었다. 이 중에서 가장 작은 가중치를 갖는 간선은 F-E(82)이므로 이를 최소 신장 트리에 추가한다.
이번에는 F-H가 조사 대상에서 제거되었다. 그리고 E-H, F-G중 더 가중치가 작은 간선이 E-H(98)이므로 최소 신장 트리에 H가 추가된다.
이제 남은 간선은 F-G이므로 G를 최소 신장 트리에 추가한다.
남은 간선도 G-I 하나이므로 I를 최소 신장 트리에 추가한다.
프림 알고리즘 구현에서 고려해야 할 것은 두 가지 문제가 있다.
첫 번째 문제는 최소 신장 트리의 자료구조로 무엇을 사용할 것인가 하는 것이다.
두 번째는 조사 대상 간선에서 최소 가중치를 가진 녀석을 골라내는 과정에서 발생하는 성능 문제이다.
그래프에 정점이 N개가 존재한다면 최소 신장 트리에 정점을 추가하는 작업을 N회 해야하고, 정점을 추가 할때마다 그래프 내의 정점 N개를 순회해야 하므로 N*N회, 즉 N2회 반복을 돌아야 한다.
이 문제를 해결하기 위해 '이진 탐색 트리에 조사 대상 간선 입력하기'를 생각해 볼 수 있지만, 삽입 삭제가 빠르고 최소값을 찾는데 거의 비용이 들지 않는 우선순위 큐를 이용하는 것이 적절할 것이다.
크루스칼 알고리즘
크루스칼 알고리즘(Kruskal's Algorithm)은 그래프 내의 모든 간선들의 가중치 정보를 사전에 파악하고 이 정보를 토대로 최소 신장 트리를 구축해나가는 것이 특징이다. 크루스칼 알고리즘은 아래의 순서대로 작동한다.
- 그래프 내의 모든 간선을 가중치의 오름차순으로 목록을 만든다.
- 1번에서 만든 간선의 목록을 차례대로 순회하면서 간선을 최소 신장 트리에 추가한다. 단, 이때 추가된 간선으로 인해 최소 신장 트리 내에 사이클이 형성되면 안된다.
크루스칼 알고리즘에서는 "최소 신장 트리에 생기는 사이클을 어떻게 효율적으로 감지할 것인가?"라는 문제를 해결해야 한다.
이에 대한 대안으로 사용가능한 사이클 탐지 방법은 분리 집합을 이용하는 것이다. 우선 각 정점들을 각각의 집합 안에 입력하고, 간선으로 연결되어 있는 정점들에 대해서는 합집합을 수행한다. 이때 간선으로 연결할 두 정점이 같은 집합에 속해 있다면 이 연결은 사이클을 이루게 된다.
간선으로 이을 두 정점이 같은 집합에 소속되어 있는지만 확인하면 사이클 형성 여부를 금세 알 수 있다. 탐색 비용도 깊이 우선 탐색에 비하면 미미한 수준이다.
크루스칼 알고리즘의 동작 방식은 다음과 같이 이루어진다.
우선 그래프 내의 정점 사이에 있는 모든 간선들을 가중치의 오름차순으로 정렬한다. A-B(35)가 가장 작고, A-E(247)로 가장 크다
A-B : 35
E-F : 82
E-H : 98
G-I : 106
C-D : 117
F-H : 120
B-C : 126
B-F : 150
F-G : 154
C-F : 162
C-G : 220
A-E : 247
그리고 각 정점 별로 분리 집합을 만든다
이제 가장 작은 가중치를 갖고 있는 간선부터 본격적인 작업을 시작한다. 첫 번째 간선은 A-B(35)이다. 정점 A와 B는 별개의 분리 집합의 원소이므로 이 둘을 최소 신장 트리에 추가하고 간선으로 연결한다. 그리고 분리 집합 A와 B에 대해 합집합을 수행하여 하나의 분리집합으로 만든다
두번째로 작은 가중치의 간선은 E-F(82)이다. 이 간선의 양 종단 정점도 별개의 분리 집합에 있으므로 최소 신장 트리에 추가할 수 있다. E-F를 최소 신장 트리에 추가하고 분리 집합 E와 F를 하나의 분리 집합으로 만든다
그 다음 간선은 E-H(98)이다. E는 분리 집합 {E, F}에 소속되어 있고 H는 {H}에 소속되어 있으니 서로 다른 속에 소속되어 있다. 따라서 최소 신장 트리에 들어갈 조건을 갖췄다. 간선 E-H를 최소 신장 트리에 추가하고 분리 집합 {E, F}와 {H}에 대해 합집합을 수행한다.
다음 순서는 G-I(106)이다. G-I를 하나의 합집합으로 만든다.
다음 순위의 간선은 C-D(117)이다. 이 둘은 서로 다른 집합에 소속되어 있으므로 최소 신장 트리에 간선을 추가하고 두 정점을 하나의 집합으로 만든다.
다음은 간선 F-H(120)이다. 하지만 정점 F와 H는 이미 같은 집합에 속해 있다. 간선의 양끝에 있는 정점이 같은 집합에 있다는 것은 이 간선으로 인해 사이클이 형성된다는 뜻이다. 따라서 간선 F-H는 무시하고 다음 순위의 간선을 채택한다.
다음은 B-C(126)이다. B와 C는 서로 다른 집합이므로 이 간선을 최소 신장 트리에 추가하고 B가 속해 있는 집합{A,B}와 C가 속해 있는 집합{C,D}에 대해 합집합을 수행한다.
다음 순위는 B-F(15)이다. B와 F는 서로 다른 집합이므로 간선B-F는 최소 신장 트리에 추가하고 B의 집합과 F의 집합을 합집합을 한다.
다음 순위의 간선은 F-G(154)이다. F와 G를 서로 다른 집합이므로 최소 신장 트리에 F-G를 추가하고 합집합 한다
이제 모든 정점이 하나의 집합에 속해있게 되었다. C-F(162), C-G(220), A-E(247)간선이 남아 있지만 조사할 필요가 없다.
최소 신장 트리 예제 프로그램
DisjointSet.c, DisjointSet.h, PriorityQueue.c, PriorityQueue.h, Graph.c, Graph.h, MST.c, MST.h, test_MST.c파일이 사용된다.
- 예제 MST.h
|
#ifndef _MST_H__ #define _MST_H__
#include "Graph.h" #include "PriorityQueue.h" #include "DisjointSet.h"
#define MAX_WEIGHT 36267
void prim(Graph* g, Vertex* startVertex, Graph* MST); void kruskal(Graph* g, Graph* MST);
#endif |
- 예제 MST.c
|
#include "MST.h"
void prim(Graph* g, Vertex* startVertex, Graph* MST) { int i = 0;
PQNode startNode = {0, startVertex}; PriorityQueue* PQ = PQ_Create(10);
Vertex* currentVertex = NULL; Edge* currentEdge = NULL;
int* weight = (int*)malloc(sizeof(int) * g->VertexCount);
Vertex** MSTVertices = (Vertex**)malloc(sizeof(Vertex*) * g->VertexCount); Vertex** fringes = (Vertex**)malloc(sizeof(Vertex*) * g->VertexCount); Vertex** precedences= (Vertex**)malloc(sizeof(Vertex*) * g->VertexCount);
currentVertex = g->Vertices; while( currentVertex != NULL ) { Vertex* newVertex = CreateVertex(currentVertex->Data); AddVertex(MST, newVertex);
fringes[i] = NULL; precedences[i] = NULL; MSTVertices[i] = newVertex; weight[i] = MAX_WEIGHT; currentVertex = currentVertex->Next; i++; }
PQ_Enqueue(PQ, startNode); weight[startVertex->Index] = 0;
while( !PQ_IsEmpty(PQ) ) { PQNode pop; PQ_Dequeue(PQ, &pop); currentVertex = (Vertex*)pop.Data;
fringes[currentVertex->Index] = currentVertex;
currentEdge = currentVertex->AdjacencyList; while( currentEdge != NULL ) { Vertex* targetVertex = currentEdge->Target;
if( fringes[targetVertex->Index] == NULL && currentEdge->Weight < weight[targetVertex->Index] ) { PQNode newNode = {currentEdge->Weight, targetVertex}; PQ_Enqueue(PQ, newNode);
precedences[targetVertex->Index] = currentEdge->From; weight[targetVertex->Index] = currentEdge->Weight; } currentEdge = currentEdge->Next; } }
for( i = 0 ; i < g->VertexCount ; i++ ) { int fromIndex, toIndex; if( precedences[i] == NULL ) { continue; }
fromIndex = precedences[i]->Index; toIndex = i;
AddEdge(MSTVertices[fromIndex], CreateEdge(MSTVertices[fromIndex], MSTVertices[toIndex], weight[i])); AddEdge(MSTVertices[toIndex], CreateEdge(MSTVertices[toIndex], MSTVertices[fromIndex], weight[i])); }
free(fringes); free(precedences); free(MSTVertices); free(weight);
PQ_Destroy(PQ); } void kruskal(Graph* g, Graph* MST) { int i = 0; Vertex* currentVertex = NULL; Vertex** MSTVertices = (Vertex**)malloc(sizeof(Vertex*) * g->VertexCount); DisjointSet** vertexSet = (DisjointSet**)malloc(sizeof(DisjointSet*) * g->VertexCount);
PriorityQueue* PQ = PQ_Create(10);
currentVertex = g->Vertices; while( currentVertex != NULL ) { Edge* currentEdge;
vertexSet[i] = DS_MakeSet(currentVertex); MSTVertices[i] = CreateVertex(currentVertex->Data); AddVertex(MST, MSTVertices[i]);
currentEdge = currentVertex->AdjacencyList; while( currentEdge != NULL ) { PQNode newNode = { currentEdge->Weight, currentEdge }; PQ_Enqueue(PQ, newNode);
currentEdge = currentEdge->Next; }
currentVertex = currentVertex->Next; i++; }
while( !PQ_IsEmpty(PQ) ) { Edge* currentEdge; int fromIndex; int toIndex; PQNode pop;
PQ_Dequeue(PQ, &pop); currentEdge = (Edge*)pop.Data;
printf("%c - %c : %d\n", currentEdge->From->Data, currentEdge->Target->Data, currentEdge->Weight); fromIndex = currentEdge->From->Index; toIndex = currentEdge->Target->Index;
if( DS_FindSet(vertexSet[fromIndex]) != DS_FindSet(vertexSet[toIndex]) ) { AddEdge(MSTVertices[fromIndex], CreateEdge(MSTVertices[fromIndex], MSTVertices[toIndex], currentEdge->Weight)); AddEdge(MSTVertices[toIndex], CreateEdge(MSTVertices[toIndex], MSTVertices[fromIndex], currentEdge->Weight));
DS_UnionSet(vertexSet[fromIndex], vertexSet[toIndex]); } }
for( i = 0 ; i < g->VertexCount ; i++ ) { DS_DestroySet(vertexSet[i]); }
free(vertexSet); free(MSTVertices); } |
- 예제 test_MST.c
|
#include "Graph.h" #include "MST.h"
void main() { // 그래프 생성 Graph* graph = CreateGraph(); Graph* primMST = CreateGraph(); Graph* kruskalMST = CreateGraph();
// 정점 생성 Vertex* A = CreateVertex('A'); Vertex* B = CreateVertex('B'); Vertex* C = CreateVertex('C'); Vertex* D = CreateVertex('D'); Vertex* E = CreateVertex('E'); Vertex* F = CreateVertex('F'); Vertex* G = CreateVertex('G'); Vertex* H = CreateVertex('H'); Vertex* I = CreateVertex('I');
// 그래프에 정점 추가 AddVertex(graph, A); AddVertex(graph, B); AddVertex(graph, C); AddVertex(graph, D); AddVertex(graph, E); AddVertex(graph, F); AddVertex(graph, G); AddVertex(graph, H); AddVertex(graph, I);
// 정점과 정점을 간선으로 잇기 AddEdge(A, CreateEdge(A, B, 35)); AddEdge(A, CreateEdge(A, E, 247));
AddEdge(B, CreateEdge(B, A, 35)); AddEdge(B, CreateEdge(B, C, 126)); AddEdge(B, CreateEdge(B, F, 150));
AddEdge(C, CreateEdge(C, B, 126)); AddEdge(C, CreateEdge(C, D, 117)); AddEdge(C, CreateEdge(C, F, 162)); AddEdge(C, CreateEdge(C, G, 220));
AddEdge(D, CreateEdge(D, C, 117));
AddEdge(E, CreateEdge(E, A, 247)); AddEdge(E, CreateEdge(E, F, 82)); AddEdge(E, CreateEdge(E, H, 98));
AddEdge(F, CreateEdge(F, B, 150)); AddEdge(F, CreateEdge(F, C, 162)); AddEdge(F, CreateEdge(F, E, 82)); AddEdge(F, CreateEdge(F, G, 154)); AddEdge(F, CreateEdge(F, H, 120));
AddEdge(G, CreateEdge(G, C, 220)); AddEdge(G, CreateEdge(G, F, 154)); AddEdge(G, CreateEdge(G, I, 106));
AddEdge(H, CreateEdge(H, E, 98)); AddEdge(H, CreateEdge(H, F, 120));
AddEdge(I, CreateEdge(I, G, 106));
// 정점 B를 시작 정점으로 하는 최소 신장 트리 printf("prim Algorithm\n"); prim(graph, B, primMST); PrintGraph(primMST);
// kruskal printf("kruskal Algorithm\n"); kruskal(graph, kruskalMST); PrintGraph(kruskalMST);
// 그래프 소멸 DestroyGraph(primMST); DestroyGraph(kruskalMST); DestroyGraph(graph); } |
-
최단 경로 탐색
최단 경로 탐색이란 그래프 내의 한 정점에서 다른 정점으로 이동할 때 가중치 합이 최소값이 되게 만드는 경롤르 찾는 알고리즘이다.
다익스트라 알고리즘
프림 알고리즘과 동작 방식이 비슷한데, 프림 알고리즘이 단순히 간선의 길이를 이용해 어떤 간선을 먼저 연결할지를 결정하는데 반해, 다익스트라 알고리즘은 '경로의 길이'를 감안해서 간선을 연결한다는 점이 다르다. 다익스트라의 최단 경로 탐색 알고리즘은 사이클이 없는 방향성 그래프에 한해서만 사용할 수 있다.
다익스트라 알고리즘은 다음과 같이 동작한다.
- 각 정점 위에 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 모든 정점 위에 있는 경로의 길이를 무한대로 초기화한다.
- 시작 정점의 경로 길이를 0으로 초기화하고(시작 정점에서 시작정점까지의 거리는 0이니까) 최단 경로를 추가한다.
- 최단 경로에 새로 추가된 정점의 인접 정점들에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가한다. 만약 추가하려는 인접 정점이 이미 최단 경로 안에 존재한다면 갱신되기 이전의 경로 길이가 새로운 경로의 길이보다 더 큰 경우에 한해, 다른 선행 정점을 지나던 기존의 경로를 현재 정점을 경유하도록 수정한다.
- 그래프내의 모든 정점이 최단 경로에 소속될 때까지 3과정을 반복한다.
경로는 시작점과 도착점이 필요하다. 예제에서는 B를 시작점으로 설정하고 도착점은 '나머지의 모든 정점'으로 할 것이다.
우선 각 정점 별로 경로 길이를 무한대로 설정한다. 그리고 시작 정점 B의 경로 길이를 0으로 바꾼다.
시작 정점인 B에 인접한 정점들을 찾고 간선의 가중치를 조사한다. 그리고 각 경로의 길이의 비용 바꾼다.
A의 유일한 인접 정점인 E를 이동하는데 드는 비용 B-A(35) + A-E(247)의 값을 E에 입력한다. 이 값은 무한대보다 작으므로 입력 가능하다
이번에는 C의 인접 정점들을 조사할 차례이다. C의 인접 정점은 D, F, G가 있는데 D의 현재 길이는 무한대이므로 B-C-D 경로의 비용을 그대로 입력하고, G 역시 경로의 길이가 무한대이므로 B-C-G 경로의 비용으르 입력한다. 현재 F가 가지고 있는 경로의 길이는 150이므로 B-C-F 경로의 비용인 288보다 작다. 따라서 새로 발견한 B-C-F는 B-F보다 비용이 크기 때문에 채택할 수 없다.
이번에는 정점 F의 인접한 정점을 보면 E, G, H가 있다. 먼저 E 정점을 보면 기존 경로 길이 282를 갖고 있는데, 새로운 경로인 B-F-E의 비용이 232로 더 작다. 따라서 기존 경로 B-A-E는 폐기하고 새로운 경로 B-F-E를 채택한다.
G도 마찬가지로 기존의 경로 B-C-G(비용 346)보다 새 경로 B-F-G(비용 304)가 훨씬 저렴하므로 기존 경로를 폐기하고 새롭게 발견한 경로를 채택한다. 이제 G의 경로 길이는 304로 갱신되었다. H의 경로 길이는 무한대이므로 B-F-H의 비용 270을 H의 경로 길이에 입력한다.
E에게 인접 정점 H가 있긴 하지만 경로 B-F-E-H의 비용이 330으로써 현재 경로 길이 270보다 크므로 무시하고 다음으로 넘어간다. 정점 G는 방문하지 않은 정점 I와 인접해 있는데 I의 현재 경로 길이는 무한대이므로 B-F-G-I의 비용 410을 입력한다.
이제 더 탐사할 노드가 없으므로 최단 경로 탐색이 끝났다.
다익스트라 알고리즘 예제 프로그램
PriorityQueue.c, PriorityQueue.h, Graph.c, Graph.h, ShortestPath.c, ShortestPath.h, Test_ShortestPash.c 7개 파일로 구성되어 있다.
- 예제 ShortestPath.h
|
#ifndef _SHORTESTPATH_H__ #define _SHORTESTPATH_H__
#include "Graph.h" #include "PriorityQueue.h"
#define MAX_WEIGHT 36267
void dijkstra(Graph* g, Vertex* startVertex, Graph* shortestPath);
#endif |
- 예제 ShortestPath.c
|
#include "ShortestPath.h"
void dijkstra(Graph* g, Vertex* startVertex, Graph* shortestPath) { int i = 0;
PQNode startNode = {0, startVertex}; PriorityQueue* PQ = PQ_Create(10);
Vertex* currentVertex = NULL; Edge* currentEdge = NULL;
int* weight = (int*)malloc(sizeof(int) * g->VertexCount);
Vertex** shortestPathVertices = (Vertex**)malloc(sizeof(Vertex*) * g->VertexCount); Vertex** fringes = (Vertex**)malloc(sizeof(Vertex*) * g->VertexCount); Vertex** precedences = (Vertex**)malloc(sizeof(Vertex*) * g->VertexCount);
currentVertex = g->Vertices; while( currentVertex != NULL ) { Vertex* newVertex = CreateVertex(currentVertex->Data); AddVertex(shortestPath, newVertex);
fringes[i] = NULL; precedences[i] = NULL; shortestPathVertices[i] = newVertex; weight[i] = MAX_WEIGHT; currentVertex = currentVertex->Next; i++; }
PQ_Enqueue(PQ, startNode);
weight[startVertex->Index] = 0;
while( !PQ_IsEmpty(PQ) ) { PQNode pop;
PQ_Dequeue(PQ, &pop); currentVertex = (Vertex*)pop.Data;
fringes[currentVertex->Index] = currentVertex;
currentEdge = currentVertex->AdjacencyList; while( currentEdge != NULL ) { Vertex* targetVertex = currentEdge->Target;
if( fringes[targetVertex->Index] == NULL && weight[currentVertex->Index] + currentEdge->Weight < weight[targetVertex->Index] ) { PQNode newNode = {currentEdge->Weight, targetVertex}; PQ_Enqueue(PQ, newNode);
precedences[targetVertex->Index] = currentEdge->From; weight[targetVertex->Index] = weight[currentVertex->Index] + currentEdge->Weight; }
currentEdge = currentEdge->Next; } }
for( i = 0 ; i < g->VertexCount ; i++ ) { int fromIndex, toIndex;
if( precedences[i] == NULL ) { continue; }
fromIndex = precedences[i]->Index; toIndex = i;
AddEdge(shortestPathVertices[fromIndex], CreateEdge(shortestPathVertices[fromIndex], shortestPathVertices[toIndex], weight[i])); }
free(fringes); free(precedences); free(shortestPathVertices); free(weight);
PQ_Destroy(PQ); } |
- 예제 main.c
|
#include "Graph.h" #include "ShortestPath.h"
void main(void) { // 그래프 생성 Graph* graph = CreateGraph(); Graph* primMST = CreateGraph(); Graph* kruskalMST = CreateGraph();
// 정점 생성 Vertex* A = CreateVertex('A'); Vertex* B = CreateVertex('B'); Vertex* C = CreateVertex('C'); Vertex* D = CreateVertex('D'); Vertex* E = CreateVertex('E'); Vertex* F = CreateVertex('F'); Vertex* G = CreateVertex('G'); Vertex* H = CreateVertex('H'); Vertex* I = CreateVertex('I');
// 그래프에 정점 추가 AddVertex(graph, A); AddVertex(graph, B); AddVertex(graph, C); AddVertex(graph, D); AddVertex(graph, E); AddVertex(graph, F); AddVertex(graph, G); AddVertex(graph, H); AddVertex(graph, I);
// 정점과 정점을 간선으로 잇기 AddEdge(A, CreateEdge(A, E, 247));
AddEdge(B, CreateEdge(B, A, 35)); AddEdge(B, CreateEdge(B, C, 126)); AddEdge(B, CreateEdge(B, F, 150));
AddEdge(C, CreateEdge(C, D, 117)); AddEdge(C, CreateEdge(C, F, 162)); AddEdge(C, CreateEdge(C, G, 220));
AddEdge(E, CreateEdge(E, H, 98));
AddEdge(F, CreateEdge(F, E, 82)); AddEdge(F, CreateEdge(F, G, 154)); AddEdge(F, CreateEdge(F, H, 120));
AddEdge(G, CreateEdge(G, I, 106));
// 정점 B를 시작으로 최소 신장 트리 dijkstra(graph, B, primMST); PrintGraph(primMST);
// 그래프 소멸 DestroyGraph(primMST); DestroyGraph(kruskalMST); DestroyGraph(graph);; } |
'책정리 > 뇌를 자극하는 알고리즘' 카테고리의 다른 글
| 10장 문자열 검색 (0) | 2015.03.31 |
|---|---|
| 8장 해시 테이블 (2) | 2015.03.28 |
| 7장 우선순위 큐와 힙 (0) | 2015.03.25 |
| 6장 탐색 (0) | 2015.03.25 |
| 5장 정렬 (0) | 2015.03.23 |