4.2 최소 신장 트리
그리디 알고리즘을 통해 항상 정답을 도출할 수 있는 알고리즘
최소 신장 트리
(1) 최소 신장 트리란 ?
최소 신장 트리 = 신장트리 + 가중치의 합이 최소
-트리는 그래프의 한 종류이다, 정점과 간선으로 된 그래프이다.
-신장트리는
- 연결 그래프의 부분 그래프로서 그 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리
- 모든 노드는 적어도 하나의 간선에 연결되어 있어야 한다. (노드 = n개 , 간선 = n-1개 )
트리에 간선을 하나 추가 시키면 반드시 사이클이 만들어진다.
하지만 그래프에 사이클이 형성이 되면 안된다.
[크러스컬 알고리즘]
1) 특정한 정점에서 시작되는 것이 아니라 전체 가중치 그래프에서 가중치 가장 작은 간선을 선택한다
2) 먼저 가중치를 기준으로 정렬 후 앞의 인덱스부터 선택한다.
3) 선택 기준 = “사이클 형성 여부”를 확인한다.
[사이클이 생기는지에 대한 여부]
union-find 알고리즘 = 해당 간선의 부모노드를 찾아가서 현재 있는 간선의 부모노드와 같은지 확인
KruskalMST(G)
입력: 가중치 그래프 G=(V,E), |V|=n개 , |E|=m개
출력: 최소 신장 트리 T
1. 가중치의 오름차순으로 간선들을 정렬 : L = 정렬된 간선 리스트
2. T=∅ // 트리 T를 초기화(결과 트리)
3. while ( T의 간선 수 < n-1 ) // n-1개의 간선이 선택되어질 때까지
4. L에서 가장 작은 가중치를 가진 간선 e를 가져오고, e를 L에서 제거
5. if (간선 e가 T에 추가되어 사이클을 만들지 않으면) //결과 트리에 추가할 지에대한 여부
6. e를 T에 추가
7. else // e가 T에 추가되어 사이클이 생기는 경우
8. e를 버린다.
9. return 트리 T // T는 최소 신장 트리
[코드 구현]
#include <stdio.h>
#include <stdlib.h>
typedef struct Edge // 간선을 표현한 그래프
{
char v1, v2;//vertex 구조체로 짜면 좋은데 씨언어 구조상 순환이 불가능하고 순차적으로만 된다 그래서 따로 이름을 설정함
int weight;
struct Edge* next;
}Edge;
typedef struct IncidentEdge //바로 인접한 정점 표현
{
char aName;
Edge* e;
struct IncidentEdge* next;
}IncidentEdge;
typedef struct Vertex // 정점들의 연결리스트
{
char vName;
IncidentEdge* iHead; //첫번째 간선의 시작주소
struct Vertex* next; //다른 정점을 연결할
}Vertex;
typedef struct // 그래프는 정점과 간선의 집합이다.
{ //앞에서 만든 3가지 연결리스트들을 가리키는 header를 따로 빼서 관리(해당 하는 것만 가리키면 된다)
Vertex* vHead;
Edge* eHead;
int eCount, vCount;
}Graph;
void init(Graph* G) //초기화
{
G->vHead = NULL;//정점없음
G->eHead = NULL;//간선 없음
G->vCount = G->eCount = 0;/개수도 없음
}
void makeVertex(Graph* G, char vName)
{
Vertex* v = (Vertex*)malloc(sizeof(Vertex));
v->vName = vName;
v->iHead = NULL;
v->next = NULL; //아직 아무 것도 없음
G->vCount++;
Vertex* q = G->vHead;
if (q == NULL) //자신이 처음 만들어졌을 때 (아무런 노드가 없을 때
G->vHead = v;
else
{
while (q->next != NULL) //그래프에 다른 노드가 있는 경우 끝까지 가면서(마지막은 NULL임)
q = q->next; //자신이 마지막 노드가 된다.
q->next = v;
}
}
void makeIncidentEdge(Vertex* v, char aName, Edge* e)
{
IncidentEdge* p = (IncidentEdge*)malloc(sizeof(IncidentEdge));
p->aName = aName;
p->e = e; //p의 정점 리스트와 포인터 연결 (다른 리스트와의 수직 연결)
p->next = NULL;
IncidentEdge* q = v->iHead;
if (q == NULL) //같은 리스트 내에 수평으로 연결
v->iHead = p;
else
{
while (q->next != NULL)
q = q->next;
q->next = p;
}
}
Vertex* findVertex(Graph* G, char vName)
{
Vertex* v = G->vHead; 그래프에 첫번째 정점부터
while (v->vName != vName) //정접을 찾을 때까지 감
v = v->next;
return v; //정점의 주소 리턴
}
void insertEdge(Graph* G, char v1, char v2, int w)
{
Edge* e = (Edge*)malloc(sizeof(Edge));
e->weight = w;
e->v1 = v1;
e->v2 = v2;
e->next = NULL;
G->eCount++;
Edge* q = G->eHead;
if (q == NULL)
G->eHead = e;
else
{
while (q->next != NULL)
q = q->next;
q->next = e;
}
Vertex* v = findVertex(G, v1); //지금 만들어진 vertax를 그대로 이용하는 것이 아니라 씨언어의 제약으로 따로 char v1을 통해서 이름으로 저장한 것이다. 나중에 이 이름으로 따로 Vertax를 찾는 과정이 필요하다. 이를 findVertax를 통해 이름으로 정점을 찾는다.
makeIncidentEdge(v, v2, e); // v = 현재 정점주소 , v2 = 연결할 정점이름, e = 간선
v = findVertex(G, v2);
makeIncidentEdge(v, v1, e);
}
void print(Graph* G)
{
Vertex* p = G->vHead;
IncidentEdge* q;
for (; p != NULL; p = p->next)
{
printf("[%c] : ", p->vName);
for (q = p->iHead; q != NULL; q = q->next)
printf("[%c, %d] ", q->aName, q->e->weight);
printf("\\n");
}
printf("\\n");
}
void incSort(Graph* G, Edge* e[]) //일단 시간 복잡도가 O(n^2)으로 정렬
{
int i, least;
Edge* p = G->eHead;
for(i = 0; i < G->eCount; i++)
{
e[i] = p;
p = p->next;
}
for (i = 0; i < G->eCount - 1; i++)
{
least = i;
for (int j = i + 1; j < G->eCount; j++)
if (e[j]->weight < e[least]->weight)
least = j;
p = e[least];
e[least] = e[i];
e[i] = p;
}
for(i = 0; i < G->eCount; i++)
printf("[%c%c(%d)] ", e[i]->v1, e[i]->v2, e[i]->weight);
printf("\\n\\n");
}
void vUnion(int v[], int vNum1, int vNum2)
{
int r1 = vFind(v, vNum1);
int r2 = vFind(v, vNum2);
if (r1 != r2)
v[r2] = r1; // 정점 배열에 r2가 r1과 연결되어 있다고 표시
}
void kruskal(Graph* G, Edge* e[], int v[])
{
int eCnt = 0;//간선 카운트
int i = 0;
int vNum1, vNum2;//정점을 연결할 번호
Edge* p;//간선을 저장할 포인터 변수
while (eCnt < G->vCount - 1)//n-1개의 간선이 선택될 때까지 (선택이 되면 쌓아두는 것이 아니라 그때 그때마다 출력
{
p = e[i];//오름차순으로 저장한 간선 배열 중 첫번째 간선을 가지고 옴
vNum1 = vFind(v, p->v1 - 97); // p-> v1는 알파벳인데 아스키코드를 고려하여 인덱스 숫자로 변환해주는 과정
vNum2 = vFind(v, p->v2 - 97); //연결된 두 정점 중 하나
if (vNum1 != vNum2) //다른 그래프 , 사이클이 만들어 지지 않음 -> 연결 가능
{
printf("%d. [%c%c (%d)]\\n", eCnt + 1, p-> v1, p-> v2, p-> weight); // 두 정점과 가중치 출력
eCnt++;
vUnion(v, vNum1, vNum2);//합쳐진다.
}
i++;//다음 엣지
}
}
int vFind(int v[], int vNum)
{
if (v[vNum] == -1)
return vNum; //-1이라면 nNum 그대로 출력
while (v[vNum] != -1) //-1을 만나기 전까지 반복(부모 찾기)
vNum = v[vNum];
return vNum; //-1인 값을 리턴
}
int main()
{
Graph G;
init(&G);
makeVertex(&G, 'a'); makeVertex(&G, 'b'); makeVertex(&G, 'c');
makeVertex(&G, 'd'); makeVertex(&G, 'e'); makeVertex(&G, 'f'); //6개의 정점을 만든다
insertEdge(&G, 'a', 'b', 8); insertEdge(&G, 'a', 'd', 2);
insertEdge(&G, 'a', 'e', 4); insertEdge(&G, 'b', 'c', 1);
insertEdge(&G, 'b', 'd', 4); insertEdge(&G, 'b', 'f', 2);
insertEdge(&G, 'c', 'f', 1); insertEdge(&G, 'd', 'e', 3);
insertEdge(&G, 'd', 'f', 7); insertEdge(&G, 'e', 'f', 9);
print(&G);
Edge* e[20]; //간선을 정렬할 배열, 간선들의 주소들이 있다.
incSort(&G, e); //정렬
int v[10] = { -1, -1,-1, -1,-1, -1, -1, -1,-1, -1}; //유니온 파운드
kruskal(&G, e, v);
return 0;
}
시간 복잡도 - 크러스컬
- Line 1 : 간선 정렬하는데 O(mlogm) 시간 < 분할 정복 기법> 단, m은 입력 그래프에 있는 간선의 수
- Line 2 : T를 초기화하는 것이므로 O(1) 시간
- Line 3~8 • while-루프는 최대 m번 수행< 간선의 개수 m만큼 > 그래프의 모든 간선이 while-루프 내에서 처리되는 경우 • while-루프 내에서는 L로부터 가져온 간선 e가 사이클을 만드는지를 검사하는데 거의 O(1) 시간
- unionfind하는 것
Kruskal 알고리즘의 시간복잡도: O(mlogm)
간선 정렬하는 데 걸리는 시간 정도 걸림
[ 프림 알고리즘 ]
1) 임의의 점 하나를 선택하면 (n-1)개의 간선을 하나씩 추가시켜 트리 생성
2) 추가되는 간선은 현재까지 만들어진 트리에 연결시킬 때 “욕심내어” 항상 최소의 가중치로 연결되는 간선
3) 선택 기준 = “사이클 형성 여부”를 확인 + 임의의 점에서 갈 수 있는 최적의 간선을 선택
- 알고리즘의 입력은 1개의 연결 성분으로 된 가중치 그래프
연결성분이란? 입력된 그래프가 연결 그래프라는 것은 그래프가 1개, 연결 성분이 2개라면 연결 그래프가 아니다. )
PrimMST(G)
입력: 가중치 그래프 G=(V,E), |V|=n, |E|=m
출력: 최소 신장 트리 T
1. G에서 임의의 점 p를 시작점으로 선택 D[p] = 0
// D[v]는 T에 있는 u와 v를 연결하는 간선의 최소 가중치를 저장 하기 위한 원소
2. for (점 p가 아닌 각 점 v에 대하여<p를 제외한 다른 정점>) // 배열 D의 초기화
{
3. if ( 간선 (p, v)가 그래프에 있으면 ) //v는 p의 인접 정점
4. D[v] = 간선 (p, v)의 가중치
5. else
6. D[v]=∞ //초기화 -> 나중에 업데이터
}
7. T= {p} // 초기에 결과 트리 T는 점 p만을 가진다.
8. while (T에 있는 점의 수 < n)
{
9. T에 속하지 않은 각 점 v에 대하여, D[v]가 최소인 점 vmin과 연결된 간선 (u, vmin)을 T에 추가, 여기서 u는 T에 속한 점이고, 점
vmin도 T에 추가
10. for (T에 속하지 않은 각 점 w에 대해서)
{
11. if (간선 (vmin, w)의 가중치 < D[w])
12. D[w] = 간선 (vmin, w)의 가중치 // 더 최솟값이라면 D[w]를 갱신
}
}
13. return T // T는 최소 신장 트리
10. for (T에 속하지 않은 각 점 w에 대해서) {
11. if (간선 (vmin, w)의 가중치 < D[w])
12. D[w] = 간선 (vmin, w)의 가중치 // 더 최솟값이라면 D[w]를 갱신 }
이 부분은 기존에서 갈 수 있는 거리와 점을 추가 후 갈 수 있는 거리를 비교하여 최솟값이 되는 위치를 선택
[프림 알고리즘에서는 사이클 검사하지 않아도 되는 이유]
프림 알고리즘은 선택된 영역(T) 밖에 있는 점을 항상 추가하므로 사이클이 만들어지지 않는다
[코드]
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE 1 // 방문되어있는지 에 대한 플래그
typedef struct Edge // 간선을 표현한 그래프
{
char v1, v2;//vertex 구조체로 짜면 좋은데 씨언어 구조상 순환이 불가능하고 순차적으로만 된다 그래서 따로 이름을 설정함
int weight;
struct Edge* next;
}Edge;
typedef struct IncidentEdge //바로 인접한 정점 표현
{
char aName;
Edge* e;
struct IncidentEdge* next;
}IncidentEdge;
typedef struct Vertex // 정점들의 연결리스트
{
char vName;
int isVisit;
IncidentEdge* iHead; //첫번째 간선의 시작주소
struct Vertex* next; //다른 정점을 연결할
}Vertex;
typedef struct // 그래프는 정점과 간선의 집합이다.
{ //앞에서 만든 3가지 연결리스트들을 가리키는 header를 따로 빼서 관리(해당 하는 것만 가리키면 된다)
Vertex* vHead;
Edge* eHead;
int eCount, vCount;
}Graph;
void init(Graph* G) //초기화
{
G->vHead = NULL;//정점없음
G->eHead = NULL;//간선 없음
G->vCount = G->eCount = 0; // 개수도 없음
}
void makeVertex(Graph* G, char vName)
{
Vertex* v = (Vertex*)malloc(sizeof(Vertex));
v->vName = vName;
v->isVisit = FALSE; //아직 방문하지 않음
v->iHead = NULL;
v->next = NULL; //아직 아무 것도 없음
G->vCount++;
Vertex* q = G->vHead;
if (q == NULL) //자신이 처음 만들어졌을 때 (아무런 노드가 없을 때
G->vHead = v;
else
{
while (q->next != NULL) //그래프에 다른 노드가 있는 경우 끝까지 가면서(마지막은 NULL임)
q = q->next; //자신이 마지막 노드가 된다.
q->next = v;
}
}
void makeIncidentEdge(Vertex* v, char aName, Edge* e)
{
IncidentEdge* p = (IncidentEdge*)malloc(sizeof(IncidentEdge));
p->aName = aName;
p->e = e; //p의 정점 리스트와 포인터 연결 (다른 리스트와의 수직 연결)
p->next = NULL;
IncidentEdge* q = v->iHead;
if (q == NULL) //같은 리스트 내에 수평으로 연결
v->iHead = p;
else
{
while (q->next != NULL)
q = q->next;
q->next = p;
}
}
Vertex* findVertex(Graph* G, char vName) // 문자를 받고 주솟값 알아내기
{
Vertex* v = G->vHead; //그래프에 첫번째 정점부터
while (v->vName != vName) //정접을 찾을 때까지 감
v = v->next;
return v; //정점의 주소 리턴
}
void insertEdge(Graph* G, char v1, char v2, int w)
{
Edge* e = (Edge*)malloc(sizeof(Edge));
e->weight = w;
e->v1 = v1;
e->v2 = v2;
e->next = NULL;
G->eCount++;
Edge* q = G->eHead;
if (q == NULL)
G->eHead = e;
else
{
while (q->next != NULL)
q = q->next;
q->next = e;
}
Vertex* v = findVertex(G, v1); //지금 만들어진 vertax를 그대로 이용하는 것이 아니라 씨언어의 제약으로 따로 char v1을 통해서 이름으로 저장한 것이다. 나중에 이 이름으로 따로 Vertax를 찾는 과정이 필요하다. 이를 findVertax를 통해 이름으로 정점을 찾는다.
makeIncidentEdge(v, v2, e); // v = 현재 정점주소 , v2 = 연결할 정점이름, e = 간선
v = findVertex(G, v2);
makeIncidentEdge(v, v1, e);
}
void print(Graph* G)
{
Vertex* p = G->vHead;
IncidentEdge* q;
for (; p != NULL; p = p->next)
{
printf("[%c] : ", p->vName);
for (q = p->iHead; q != NULL; q = q->next)
printf("[%c, %d] ", q->aName, q->e->weight);
printf("\\n");
}
printf("\\n");
}
char getMinVertax(Graph* G, int D[])
{
Vertex* p = G->vHead;// 연결리스트를 돌면서 가리킬 것임
char vName;
for (; p != NULL; p = p->next)//처음부터 끝까지 돌면서
{
if (p->isVisit == FALSE)//방문한 적 없음
{
vName = p->vName;
break;
}
}
for (p = G->vHead; p != NULL; p = p->next) // 방문한 적 있음
{
if (p->isVisit == FALSE && (D[p->vName - 97] < D[vName - 97])) // 해당 값과 다른 값들의 가중치 비교
vName = p->vName;
}
return vName;
}
void prim(Graph* G, char vName, int D[])
{
Vertex* p = findVertex(G, vName);
IncidentEdge* q;
char c;
D[p->vName - 97] = 0;
for (int i = 0; i < G->vCount; i++)
{
c = getMinVertax(G, D); //가중치 배열을 고려하여 가장 작은 간선을 가져올 것임
p = findVertex(G, c);
p->isVisit = TRUE;
printf("(%c)", p->vName);
for (q = p->iHead; q != NULL; p = p->next)
{
p = findVertex(G, q->aName); // 인접 정점 찾기
if (p->isVisit == FALSE)
D[q->aName - 97] = q->e->weight;
}
}
}
int main()
{
Graph G;
init(&G);
makeVertex(&G, 'a'); makeVertex(&G, 'b'); makeVertex(&G, 'c');
makeVertex(&G, 'd'); makeVertex(&G, 'e'); makeVertex(&G, 'f'); //6개의 정점을 만든다
insertEdge(&G, 'a', 'b', 3); insertEdge(&G, 'a', 'd', 2);
insertEdge(&G, 'a', 'e', 4); insertEdge(&G, 'b', 'c', 1);
insertEdge(&G, 'b', 'd', 4); insertEdge(&G, 'b', 'f', 2);
insertEdge(&G, 'c', 'f', 1); insertEdge(&G, 'd', 'e', 5);
insertEdge(&G, 'd', 'f', 7); insertEdge(&G, 'e', 'f', 9);
print(&G);
Edge* e[20]; //간선을 정렬할 배열, 간선들의 주소들이 있다.
incSort(&G, e); //정렬
int D[10] = { 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}; //유니온 파운드
prim(&G, 'c', D); //그래프 G와 정점 'c'와 배열 D
return 0;
}
시간 복잡도 - 프림 알고리즘
while-루프가 (n-1)회 반복되고,
• 1회 반복될 때 line 9에서 T에 속하지 않은 각 점 v에 대하여, D[v]가 최소인 점 Vmin을 찾는데 O(n) 시간 소요
• 배열 D에서 (현재 T에 속하지 않은 점들에 대해서) 최솟값을 찾는 것이고, 배열의 크기는 n이기 때문
프림 알고리즘의 시간 복잡도 = (n-1) x O(n) = O(n2)
• 최소 힙(Binary Heap)을 사용하여 Vmin을 찾으면 O(mlogn),
<Vmin을 찾기 위해서 n번이 아니라 1번 시간이 소요 된다>
m은 간선 수. 따라서 간선 수가 O(n)이면 O(nlogn)
크러스컬과 프림 알고리즘의 수행 과정 비교
[크러스컬 알고리즘]
•간선이 1개씩 T에 추가되는데, 이는 마치 n개의 점들이 각각의 트리인 상태에서 간선이 추가되면 2개의 트리가 1개의 트리로 합쳐지는 것과 같음
• 크러스컬 알고리즘은 이를 반복하여 1개의 트리인 T를 생성
• n개의 트리들이 점차 합쳐져서 1개의 신장 트리가 만들어진다.
(정점 하나도 트리, 간선 하나도 트리가 되어 점점 합쳐지면서 한 개의 신장트리가 된다)
[프림 알고리즘]
• T가 점 1개인 트리에서 시작되어 간선을 1개씩 추가
• 1개의 트리가 자라나서 신장 트리가 된다.
(1개에서 시작하여 점점 자라난다)
'CS > 알고리즘' 카테고리의 다른 글
| Chap 4-7. 허프만 압축 (0) | 2022.05.04 |
|---|---|
| Chap4-6. 작업스케줄링(Job scheduling) (0) | 2022.04.15 |
| Chap4-1. 동전 찾기 문제 (0) | 2022.04.11 |
| Chap 4. 그리디 알고리즘 (0) | 2022.04.11 |
| Chap3-4. 최근접 점의 쌍 찾기(Closest Pair) (0) | 2022.04.08 |
