7.5 최소 신장 트리
- 그래프는 정점의 집합과 간선의 집합으로 이루어진 자료구조
- 간선은 정점과 정점의 인접 관계를 설명하는 요소
신장 트리 (Spanning Tree)
- 그래프의 모든 정점을 연결하는 트리
- 그래프의 하위 개념
최소 신장 트리 (Maximum Spanning Tree)
- 최소 가중치 신장 트리
- 여러 간선 중 가중치의 합이 최소가 되는 간선만 남긴 신장 트리
- ex) 최소한의 비용으로 모든 도시를 연결하는 도로를 건설할 방법을 찾아라
7.5.1 프림 알고리즘
프림 알고리즘 (Prim's Algorithm) 과정
1) 그래프와 최소 신장 트리를 준비
2) 그래프에서 임의의 정점을 시작 정점으로 선택하여 최소 신장 트리의 뿌리 노드로 삽입
3) 최소 신장 트리에 삽입된 정점들과 이 정점들의 모든 인접 정점 사이에 있는 간선의 가중치를 조사
간선중에 가장 가중치가 작은 것을 골라 이 간선에 연결된 인접 정점을 최소 신장 트리에 삽입
단, 새로 삽입되는 정점은 최소 신장 트리에 삽입된 기존 노드와 사이클을 형성해서는 안됨
4) 3)의 과정을 반복하다가 최소 신장 트리가 그래프의 모든 정점을 연결하게 되면 알고리즘 종료
ex)
- B를 시작 정점으로 사용
- B는 최소 신장 트리의 뿌리가 됨
<그래프>
<최소 신장 트리>
- 정점 B에 연결된 간선은 B-A, B-C, B-F 3개, 이 중에서 가장 가중치가 작은 간선은 가중치가 35인 B-A이므로 A를 최소 신장 트리에 추가
<그래프>
<최소 신장 트리>
- 최소 신장 트리에 등록된 노드는 B,A로 2개가 됨
- 이들 노드에 연결된 간선은 B-C, B-F, A-E인데 이 중 '최소 가중치'를 가진 간선을 찾음
- B-C의 가중치가 126으로 가장 작기 때문에 C를 최소 신장 트리에 추가
<그래프>
<최소 신장 트리>
- 가중치를 조사할 간선은 4개(C-D, B-F, C-G, A-E)
-> C-F 간선이 제외된 이유는 C-F 간선이 B-C-F를 통과하는 사이클을 형성
- 이 중 가중치가 가장 작은 간선은 C-D(117)이므로 D를 최소 신장 트리에 추가
<그래프>
<최소 신장 트리>
- 최소 가중치를 조사할 간선 B-F, C-G, A-E 중 가중치가 가장 작은 간선은 B-F(150)
- F를 최소 신장 트리에 추가
<그래프>
<최소 신장 트리>
- A-E 간서은 가중치가 더 작은 F-E 간선에 의해, C-G 간선 역시 가중치가 더 작은 F-G 간선에 의해 조사대상에서 제거
- 조사 대상 간선 3개 (F-E, F-H, F-G) 중 가장 작은 가중치를 갖는 간선 F-E(82)이므로 E를 최소 신장 트리에 추가
<그래프>
<최소 신장 트리>
- F-H 간선이 E-H 간선에 의해 조사 대상에서 제거됨
- 조사 대상 간선은 E-H, F-G 2개가 됨
- 이 중 더 작은 가중치를 가진 간선은 E-H(98)이므로 최소 신장 트리에 H를 추가
<그래프>
<최소 신장 트리>
- 조사 대상이 F-G 하나만 남음
- G를 최소 신장 트리에 추가
<그래프>
<최소 신장 트리>
- 조사 대상 간선이 G-I 하나이므로 정점 I를 최소 신장 트리에 추가
- 모든 정점이 최소 신장 트리에 입력되었으므로 트리 구축 종료
<그래프>
<최소 신장 트리>
프림 알고리즘 구현
Graph.c
#include "Graph.h"
//그래프 생성
Graph* CreateGraph()
{
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->Vertices= NULL;
graph->VertextCount = 0;
return graph;
}
//그래프 제거
void DestroyGraph(Graph* G)
{
while (G->Vertices != NULL)
{
Vertex* Vertices = G->Vertices->Next;
DestroyVertex(G->Vertices);
G->Vertices = Vertices;
}
free(G);
}
//정점 생성
Vertex* CreateVertex(VElementType 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* Edge = V->AdjacencyList->Next;
DestroyEdge(V->AdjacencyList);
V->AdjacencyList = Edge;
}
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->VertextCount++;
}
//간선 추가
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");
}
PriorityQueue.c
#include "PriorityQueue.h"
PriorityQueue* PQ_Create(int IntitialSize)
{
PriorityQueue* NewPQ = (PriorityQueue*)malloc(sizeof(PriorityQueue));
NewPQ->Capacity = IntitialSize;
NewPQ->UsedSize = 0;
NewPQ->Nodes = (PQNode*)malloc(sizeof(PQNode) * NewPQ->Capacity);
return NewPQ;
}
void PQ_Destroy(PriorityQueue* PQ)
{
free(PQ->Nodes);
free(PQ);
}
void PQ_Enqueue(PriorityQueue* PQ, PQNode NewNode)
{
int CurrentPosition = PQ->UsedSize;
int ParentPosition = PQ_GetParent(CurrentPosition);
if (PQ->UsedSize == PQ->Capacity)
{
if (PQ->Capacity == 0)
PQ->Capacity = 1;
PQ->Capacity *= 2;
PQ->Nodes = (PQNode*)realloc(PQ->Nodes, sizeof(PQNode) * PQ->Capacity);
}
PQ->Nodes[CurrentPosition] = NewNode;
// 후속 처리.
while (CurrentPosition > 0
&& PQ->Nodes[CurrentPosition].Priority < PQ->Nodes[ParentPosition].Priority)
{
PQ_SwapNodes(PQ, CurrentPosition, ParentPosition);
CurrentPosition = ParentPosition;
ParentPosition = PQ_GetParent(CurrentPosition);
}
PQ->UsedSize++;
}
void PQ_SwapNodes(PriorityQueue* PQ, int Index1, int Index2)
{
int CopySize = sizeof(PQNode);
PQNode* Temp = (PQNode*)malloc(CopySize);
memcpy(Temp, &PQ->Nodes[Index1], CopySize);
memcpy(&PQ->Nodes[Index1], &PQ->Nodes[Index2], CopySize);
memcpy(&PQ->Nodes[Index2], Temp, CopySize);
free(Temp);
}
void PQ_Dequeue(PriorityQueue* PQ, PQNode* Root)
{
int ParentPosition = 0;
int LeftPosition = 0;
int RightPosition = 0;
memcpy(Root, &PQ->Nodes[0], sizeof(PQNode));
memset(&PQ->Nodes[0], 0, sizeof(PQNode));
PQ->UsedSize--;
PQ_SwapNodes(PQ, 0, PQ->UsedSize);
LeftPosition = PQ_GetLeftChild(0);
RightPosition = LeftPosition + 1;
while (1)
{
int SelectedChild = 0;
if (LeftPosition >= PQ->UsedSize)
break;
if (RightPosition >= PQ->UsedSize)
{
SelectedChild = LeftPosition;
}
else {
if (PQ->Nodes[LeftPosition].Priority > PQ->Nodes[RightPosition].Priority)
SelectedChild = RightPosition;
else
SelectedChild = LeftPosition;
}
if (PQ->Nodes[SelectedChild].Priority < PQ->Nodes[ParentPosition].Priority)
{
PQ_SwapNodes(PQ, ParentPosition, SelectedChild);
ParentPosition = SelectedChild;
}
else
break;
LeftPosition = PQ_GetLeftChild(ParentPosition);
RightPosition = LeftPosition + 1;
}
if (PQ->UsedSize < (PQ->Capacity / 2))
{
PQ->Capacity /= 2;
PQ->Nodes =
(PQNode*)realloc(PQ->Nodes, sizeof(PQNode) * PQ->Capacity);
}
}
int PQ_GetParent(int Index)
{
return (int)((Index - 1) / 2);
}
int PQ_GetLeftChild(int Index)
{
return (2 * Index) + 1;
}
int PQ_IsEmpty(PriorityQueue* PQ)
{
return (PQ->UsedSize == 0);
}
MST.c
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* Weights = (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;
Weights[i] = MAX_WEIGHT;
CurrentVertex = CurrentVertex->Next;
i++;
}
PQ_Enqueue(PQ, StartNode);
Weights[StartVertex->Index] = 0;
while (!PQ_IsEmpty(PQ))
{
PQNode Popped;
PQ_Dequeue(PQ, &Popped);
CurrentVertex = (Vertex*)Popped.Data;
Fringes[CurrentVertex->Index] = CurrentVertex;
CurrentEdge = CurrentVertex->AdjacencyList;
while (CurrentEdge != NULL)
{
Vertex* TargetVertex = CurrentEdge->Target;
if (Fringes[TargetVertex->Index] == NULL &&
CurrentEdge->Weight < Weights[TargetVertex->Index])
{
PQNode NewNode = { CurrentEdge->Weight, TargetVertex };
PQ_Enqueue(PQ, NewNode);
Precedences[TargetVertex->Index] = CurrentEdge->From;
Weights[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], Weights[i]));
AddEdge(MSTVertices[ToIndex],
CreateEdge(MSTVertices[ToIndex], MSTVertices[FromIndex], Weights[i]));
}
free(Fringes);
free(Precedences);
free(MSTVertices);
free(Weights);
PQ_Destroy(PQ);
}코드 이해 불가 ..
'C언어 > 알고리즘' 카테고리의 다른 글
| [알고리즘] ch 8. 정렬(1) - 버블 정렬, 삽입 정렬 (2) | 2023.11.23 |
|---|---|
| [알고리즘] ch 7. 그래프(4) - 최소 신장 트리( 크루스칼 알고리즘) (2) | 2023.11.06 |
| [알고리즘] ch 7. 그래프 (2) - 위상 정렬 (0) | 2023.10.25 |
| [알고리즘] ch 7. 그래프 (1) (0) | 2023.10.25 |
| [알고리즘] ch 6 우선순위 큐와 힙 (1) | 2023.10.11 |
