목차
신장트리
그래프의 관점에서 트리를 보면 사이클이 없는 연결 그래프이다. 사이클이란 순환 경로에서 시작 정점과 종료 정점이 동일한 경우를 말한다.
모든 정점이 n개인 무방향 그래프에서 정점이 n개이고 간선이 n-1개인 트리의 형태의 부분 그래프를 신장 트리 Spanning Tree라고 한다.
깊이 우선 탐색을 이용하여 생성된 신장 트리를 깊이 우선 신장 트리(Depth First Spanning Tree)라고하며, 너비 우선 탐색을 이용하여 생성된 신장 트리를 너비 우선 신장트리(Breadth First Spanning Tree)라고 한다.
위의 사진을 보면 알다시피 모든 정점이 무조건 한 번씩 연결이 되어있는데 이것이 바로 간선을 최소로 이용하여 모든 정점을 연결한 신장트리이다. 이렇게 간선을 최소화하여 만든 트리는 우리 사회 곳곳에서 이용되는 방식이다.
최소 비용 신장 트리 Minimum Cost Spanning Tree
가중치 그래프에서 간선에 가중치를 부가하는데 이 가중치는 비용, 거리, 시간을 의미하는 값이 될 수 있다. 원하면 다른 의미를 부여해도 된다. 무방향 가중치 그래프에서 신장 트리 비용은 신장 트리를 구성하는 간선 n - 1개의 가중치를 합한 값이 되는데, 이때 가중치 합이 최소인 신장 트리를 최소 비용 신장 트리라고 한다.
내가 공부할 때 사용한 책에는 크루스칼 알고리즘을 1, 2로 나뉘어있고 프림 이렇게 3개가 나와있다. 왜지?....
크루스칼 알고리즘 1
이 알고리즘은 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만들어가는 알고리즘이다.
크루스칼 알고리즘 1을 적용한 최소 비용 신장트리를 만들기 위해서는 밑에 4가지의 순서를 지키며 트리를 생성하면 되는데...
- 그래프의 모든 간선을 가중치에 따라 내림차순으로 정렬한다.
- 그래프에서 가중치가 가장 높은 간선을 제거한다. 단, 이때 정점을 그래프에서 분리시키는 간선은 제거할 수 없으므로 이런 경우에는 그다음으로 가중치가 높은 간선을 제거한다.
- 그래프에 간선이 n-1개만 남을 때까지 2번 과정을 반복한다.
- 그래프에 간선이 n-1개만 남으면 최소 비용 신장 트리가 완성된다.
그렇다 이 순서를 읽어보면 이미 가중치가 부여돼있는 그래프가 생성되어 있고 그 그래프의 가중치를 내림차순으로 정렬하여 간선을 제거하는 것이다.
위에 사진처럼 간선의 가중치가 높은 것부터 삭제를 하다 보면 간선의 개수가 6개(정점의 개수 7, 7 - 1)가 된다.
/*
작성자: 권순욱
작성일: 2023-10-20
최종 수정일: 2023-11-5
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define HEAP_INIT_CAPACITY 8
// 힙에 저장될 데이터 타입
typedef void * HeapData;
// 힙의 데이터를 비교할 함수
typedef int PriorityComp(HeapData d1, HeapData d2);
typedef struct _heap {
PriorityComp * comp; // 데이터의 우선순위를 비교하는 함수 포인터
HeapData * heapArr; // 힙의 데이터를 저장하는 동적 배열
int numOfData; // 힙의 데이터 개수
int capacity; // 힙의 총 용량
} Heap;
// 힙 초기화 함수
void HInit(Heap *ph, PriorityComp pc) {
ph->comp = pc;
ph->capacity = HEAP_INIT_CAPACITY;
ph->numOfData = 0;
ph->heapArr = (HeapData *)malloc(sizeof(HeapData) * ph->capacity);
}
// 힙 파괴 함수
void HDestroy(Heap *ph) {
free(ph->heapArr);
ph->comp = NULL;
ph->numOfData = -1;
ph->capacity = -1;
}
// 힙이 비어 있는지 확인하는 함수
int HIsEmpty(Heap *ph) {
return (ph->numOfData == 0);
}
// 루트 요소 얻기
HeapData HGetRoot(Heap *ph) {
assert(!HIsEmpty(ph));
return ph->heapArr[1];
}
// 왼쪽 자식 노드의 인덱스 얻기
int getLeftChildIdx(int idx) {
return idx * 2;
}
// 오른쪽 자식 노드의 인덱스 얻기
int getRightChildIdx(int idx) {
return getLeftChildIdx(idx) + 1;
}
// 자식 중 높은 우선순위 자식의 인덱스 얻기
int getHighPriorityChildIdx(Heap *ph, int idx) {
int left = getLeftChildIdx(idx);
int right = getRightChildIdx(idx);
if (left > ph->numOfData) {
return 0;
}
if (left == ph->numOfData || ph->comp(ph->heapArr[left], ph->heapArr[right]) >= 0) {
return left;
}
return right;
}
// 부모 노드의 인덱스 얻기
int getParentIdx(int idx) {
return idx / 2;
}
// 힙 용량 늘리기
void resize(Heap *ph) {
ph->capacity *= 2;
ph->heapArr = (HeapData *)realloc(ph->heapArr, sizeof(HeapData) * ph->capacity);
}
// 힙에 요소 삽입
void HInsert(Heap *ph, HeapData data) {
int idx = ph->numOfData + 1;
// 용량이 가득 찬 경우 용량을 늘림.
if (idx == ph->capacity) {
resize(ph);
}
// 부모 노드와 비교하여 위치를 찾음.
while (idx != 1) {
int parentIdx = getParentIdx(idx);
HeapData parentData = ph->heapArr[parentIdx];
// 우선순위 비교하여 적절한 위치를 찾으면 종료.
if (ph->comp(data, parentData) <= 0) {
break;
}
ph->heapArr[idx] = parentData;
idx = parentIdx;
}
// 데이터를 삽입합.
ph->heapArr[idx] = data;
ph->numOfData += 1;
}
// 힙에서 루트 요소 삭제
HeapData HDelete(Heap *ph) {
assert(!HIsEmpty(ph));
int idx = 1;
HeapData root = ph->heapArr[idx];
HeapData last = ph->heapArr[ph->numOfData];
// 루트 노드부터 우선순위에 맞는 위치로 재배.
while (1) {
int childIdx = getHighPriorityChildIdx(ph, idx);
HeapData childData = ph->heapArr[childIdx];
// 자식 노드와 비교하여 올바른 위치를 찾으면 종료.
if (childIdx == 0 || ph->comp(last, childData) >= 0) {
break;
}
ph->heapArr[idx] = childData;
idx = childIdx;
}
// 루트 노드에 마지막 노드의 데이터를 넣고 개수를 감소.
ph->heapArr[idx] = last;
ph->numOfData -= 1;
return root;
}
typedef HeapData PriorityQueueData;
typedef Heap PriorityQueue;
// 우선순위 큐 초기화 함수
void QInit(PriorityQueue *pq, PriorityComp comp) {
HInit(pq, comp);
}
// 우선순위 큐 파괴 함수
void QDestroy(PriorityQueue *pq) {
HDestroy(pq);
}
// 우선순위 큐가 비어 있는지 확인하는 함수
int QIsEmpty(PriorityQueue *pq) {
return HIsEmpty(pq);
}
// 우선순위 큐에서 루트 요소 얻기
HeapData QPeek(PriorityQueue *pq) {
if (QIsEmpty(pq)) {
assert("Queue is Empty! ContainerEmptyException");
}
return HGetRoot(pq);
}
// 우선순위 큐에 요소 삽입
void Enqueue(PriorityQueue *pq, PriorityQueueData data) {
HInsert(pq, data);
}
// 우선순위 큐에서 루트 요소 삭제
HeapData Dequeue(PriorityQueue *pq) {
if (QIsEmpty(pq)) {
assert("Queue is Empty! ContainerEmptyException");
}
return HDelete(pq);
}
#define V 7 // 정점의 개수
#define E 11 // 간선의 개수
typedef struct _edge {
int v1;
int v2;
int weight;
} Edge;
Edge edges[E] = {
{0, 2, 17}, {5, 6, 14}, {1, 6, 12}, {2, 4, 10}, {3, 4, 9},
{2, 5, 8}, {0, 3, 6}, {1, 3, 5}, {4, 5, 4}, {0, 1, 3}, {4, 6, 2}
};
#define NUMBER_OF_VERTICES 7
// 특정 정점에서 다른 정점으로 연결되어 있는지 확인하는 함수
int isConnected(int (*graph)[NUMBER_OF_VERTICES], int *visitInfo, int visit, int destination) {
if (visitInfo[visit]) {
return 0;
}
if (visit == destination) {
return 1;
}
int result = 0;
visitInfo[visit] = 1;
for (int to = 0; to < NUMBER_OF_VERTICES; to++) {
if (graph[visit][to] && !visitInfo[to]) {
result |= isConnected(graph, visitInfo, to, destination);
}
if (result) {
break;
}
}
return result;
}
// 간선 비교 함수
int edgeCompare(void *p1, void *p2) {
Edge *edge1 = p1;
Edge *edge2 = p2;
return (edge1->weight) - (edge2->weight);
}
// 크루스칼 알고리즘을 통해 최소 스패닝 트리를 생성하는 함수
void kruskal(int (*graph)[NUMBER_OF_VERTICES]) {
PriorityQueue priorityQueue;
QInit(&priorityQueue, edgeCompare);
int edgeCount = 0;
for (int i = 0; i < NUMBER_OF_VERTICES; i++) {
for (int j = i + 1; j < NUMBER_OF_VERTICES; j++) {
if (graph[i][j]) {
Edge *edge = (Edge *)malloc(sizeof(Edge));
edge->v1 = i;
edge->v2 = j;
edge->weight = graph[i][j];
Enqueue(&priorityQueue, edge);
edgeCount += 1;
}
}
}
printf("\n%d\n", edgeCount);
while (edgeCount >= NUMBER_OF_VERTICES) {
Edge *edge = (Edge *)Dequeue(&priorityQueue);
int vertex1 = edge->v1;
int vertex2 = edge->v2;
int weight = edge->weight;
graph[vertex1][vertex2] = 0;
graph[vertex2][vertex1] = 0;
edgeCount -= 1;
int visitInfo[NUMBER_OF_VERTICES];
memset(visitInfo, 0, sizeof(visitInfo));
if (!isConnected(graph, visitInfo, vertex1, vertex2)) {
graph[vertex1][vertex2] = weight;
graph[vertex2][vertex1] = weight;
edgeCount += 1;
}
}
QDestroy(&priorityQueue);
}
// 그래프 출력 함수
void showGraph(int (*graph)[NUMBER_OF_VERTICES]) {
for (int i = 0; i < NUMBER_OF_VERTICES; i++) {
printf("Vertex %c: ", i + 65);
for (int j = 0; j < NUMBER_OF_VERTICES; j++) {
if (graph[i][j]) {
printf("%c ", j + 65);
}
}
printf("\n");
}
printf("\n");
}
int main() {
int graph[NUMBER_OF_VERTICES][NUMBER_OF_VERTICES] = {
// A B C D E F G
{ 0, 3, 17, 6, 0, 0, 0 }, // A
{ 3, 0, 0, 5, 0, 0, 12}, // B
{ 17, 0, 0, 0, 10, 8, 0 }, // C
{ 6, 5, 0, 0, 9, 0, 0 }, // D
{ 0, 0, 10, 9, 0, 4, 2 }, // E
{ 0, 0, 8, 0, 4, 0, 14 }, // F
{ 0, 12, 0, 0, 2, 14, 0 } // G
};
showGraph(graph);
kruskal(graph);
printf("\nAdjacency Matrix: ");
for (int i = 0; i < NUMBER_OF_VERTICES; i++) {
printf("\n\t\t");
for (int j = 0; j < NUMBER_OF_VERTICES; j++) {
printf("%3d", graph[i][j]);
}
}
puts("");
showGraph(graph);
return 0;
}
/*
코드의 전반부:
코드는 <stdio.h>, <stdlib.h>, <assert.h>, 및 <string.h> 헤더 파일을 포함하고, 몇 가지 상수 및 데이터 타입 정의를 포함합니다.
pointer to heap = ph, PriorityComp = pc
Heap 구조체:
Heap 구조체는 우선순위 큐(Priority Queue)를 구현하기 위한 구조체입니다. 이 구조체는 다음과 같은 멤버를 포함합니다:
PriorityComp *comp: 데이터의 우선순위를 비교하는 함수를 가리키는 포인터.
HeapData *heapArr: 힙의 데이터를 저장하는 동적 배열.
int numOfData: 힙의 데이터 개수.
int capacity: 힙의 총 용량.
추가해설 : 데이터의 우선순위를 비교하는 함수 포인터. 이 함수는 두 데이터를 비교하여 더 큰 우선순위를 가진 데이터를 식별하는 PriorityComp *comp와
힙의 데이터를 저장하는 동적 배열. 모든 우선순위 큐의 데이터는 이 배열에 저장하는 HeapData *heapArr와 힙의 데이터 개수. 현재 힙에 저장된
데이터의 개수를 나타내는 int numOfData...
힙 관련 함수:
HInit(Heap *ph, PriorityComp pc): 힙을 초기화하는 함수로, 힙 구조체를 초기화하고 필요한 메모리를 할당합니다.
HDestroy(Heap *ph): 힙을 파괴하고 할당된 메모리를 해제하는 함수.
HIsEmpty(Heap *ph): 힙이 비어 있는지 확인하는 함수.
HGetRoot(Heap *ph): 힙의 루트 요소를 반환하는 함수.
HInsert(Heap *ph, HeapData data): 힙에 요소를 삽입하는 함수.
HDelete(Heap *ph): 힙에서 루트 요소를 삭제하고 반환하는 함수.
우선순위 큐 관련 함수:
PriorityQueue와 관련된 함수들은 힙을 기반으로 우선순위 큐를 구현하는 함수들입니다. 이들은 큐에 데이터를 삽입하고 삭제하며, 우선순위에 따라 정렬된 데이터를 관리합니다.
Edge 구조체:
Edge 구조체는 간선 정보를 저장하는 구조체로, 두 정점(v1 및 v2)과 간선의 가중치(weight)를 저장합니다.
edges 배열:
Edge 구조체로 구성된 배열로, 그래프의 간선 정보를 저장합니다.
isConnectedWithoutEdge 함수:
재귀적으로 그래프에서 특정 정점에서 다른 정점으로 연결되어 있는지 확인하는 함수입니다. 크루스칼 알고리즘에서 순환이 발생하는지 확인하기 위해 사용됩니다.
edgeCompare 함수:
두 간선을 비교하는 함수로, 간선의 가중치를 비교합니다. 크루스칼 알고리즘에서 간선을 가중치 순으로 정렬하기 위해 사용됩니다.
kruskal 함수:
크루스칼 알고리즘을 구현하는 함수로, 주어진 그래프의 최소 스패닝 트리를 찾는 역할을 합니다. 간선을 가중치 순으로 정렬하고, 순환을 확인하여 MST를 생성합니다.
showGraph 함수:
그래프를 출력하는 함수로, 그래프의 인접 행렬을 출력합니다.
main 함수:
프로그램의 진입점으로, 주어진 그래프에서 크루스칼 알고리즘을 호출하여 최소 스패닝 트리를 생성하고 결과를 출력합니다.이 크루스칼 알고리즘 1이 크루스칼 알고리즘 2 그리고 프림에 비해 10배 이상은 어려웠다고 볼 수 있다.
다음 블로그 글에 이어서...
'알고리즘' 카테고리의 다른 글
| [알고리즘] 그래프 7 - 최단 경로(다익스트라) (1) | 2023.12.07 |
|---|---|
| [알고리즘] 그래프 6 - 신장 트리와 최소 비용 신장 트리 (0) | 2023.12.07 |
| [알고리즘] 그래프 4 - 그래프의 순회(너비 우선 탐색 BFS) (1) | 2023.12.05 |
| [알고리즘] 그래프 3 - 그래프의 순회(깊이 우선 탐색 DFS) (0) | 2023.12.05 |
| [알고리즘] 그래프 2 - 그래프의 구현(인접 행렬) (0) | 2023.12.05 |