[알고리즘, C] 최소 비용 신장 트리 (크루스칼 알고리즘)

<최소 비용 신장 트리>

[최소 비용 신장 트리에 들어가기에 앞서]

책에서도 나온 말이지만 그래프로 시작했는데 결국 또 트리 이야기가 나왔다.

그런데 사실 트리 역시 그래프의 한 유형이다.

이는 곧 이어서 보게 될 '사이클이 없는 그래프'를 보면 바로 이해가 될 것이다.

 

[사이클을 형성하지 않는 그래프 == 신장 트리]

 

이 그래프에서 정점 B에서 D로 가는 방법을 나열해보면 다음과 같다.

 

B-A-D / B-C-D / B-A-C-D / B-C-A-D

 

이처럼 두 개의 정점을 잇는 간선을 순서대로 나열한 것을 가리켜 '경로(Path)'라고 한다.

그리고 동일한 간선을 중복하여 포함하지 않는 경로를 '단순 경로(Simple Path)'라고 한다.

B-A-C-B-A-D 와 같은 경로는 B-A를 잇는 간선이 두 번 포함되므로 단순 경로가 아니다.

 

 

그렇다면, 단순 경로가 A-B-C-A는 단순 경로인가?

그렇다. 간선이 중복되지 않으면서 경로의 시작과 끝이 같은 단순 경로이다.

그리고 이와 같은 경로를 '사이클(Cycle)'이라고 한다.

 

 

위에 있는 그래프들은 모두 '사이클을 형성하지 않는 그래프'다.

그리고 이는 트리이기도 하다.

 

 

조금만 돌려서 보면 다음과 같이 트리의 구조를 띄고 있는 것을 볼 수 있다.

이진 트리는 아니지만 트리의 일종인 것은 확실하다.

그리고 이와 같이 '사이클을 형성하지 않는 그래프'를 가리켜 '신장 트리(Spanning Tree)'라고 한다.

 

[최소 비용 신장 트리의 이해와 적용]

신장 트리의 특징은 두 가지가 있다.

 

1) 그래프의 모든 정점이 간선에 의해서 하나로 연결되어 있다.

2) 그래프 내에서 사이클을 형성하지 않는다.

 

가중치 그래프 기반의 신장 트리

 

그리고 신장 트리는 가중치 그래프를 대상으로도, 방향성이 포함된 방향 그래프를 대상으로도 구성하는 것이 가능하다.

위의 그림은 가중치 그래프를 대상으로 신장 트리를 구성한 예이다.

 

가중치 그래프

 

최소 신장 트리

 

여기서 가중치 그래프를 대상으로 한 신장 트리의 모든 간선의 합이 최소인 그래프를 '최소 비용 신장 트리(Minimum Cost Spanning Tree' 또는 '최소 신장 트리(Minimum Spanning Tree)'라고 한다. (이하 MST라고 하겠다.)

실제로 MST의 구성은 전기회로의 구성이나 네트워크의 구축과 관련된 문제에서도 사용된다.

 

[MST 구성에 사용하는 알고리즘]

MST를 구성하는데 사용하는 알고리즘은 다양하다.

그 중에서도 대표적으로 꼽을 수 있는 두 가지는 다음과 같다.

 

1) 크루스칼(Kruskal) 알고리즘

가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택하거나 삭제해나가는 방식

 

2) 프림(Prim) 알고리즘

하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해나가는 방식

 

현재 읽고 있는 '열혈 자료구조'에서는 크루스칼 알고리즘에 대해서만 다룬다.

향후 다른 서적을 참고하거나 구글링을 통해서 프림 알고리즘에 대한 부분도 학습하고 기록하겠다.

 

[크루스칼 알고리즘]

1) 오름차순 정렬, 간선 선택

크루스칼 알고리즘은 가중치를 기준으로 간선을 정렬한다.

그리고 MST가 될 때까지 간선을 하나씩 선택하거나 삭제해나가는 방식이다.

핵심은 '가중치를 기준으로 간선을 정렬하는 것'에 있다.

여기서 첫 번째 케이스는 가중치를 오름차순 기준으로 정렬하여 간선을 하나씩 선택하는 방식을 예로 든다.

 

 

 

 

 

여기서 마지막 과정을 보면 가중치가 7인 간선은 건너뛰는 것을 볼 수 있다.

가중치가 7인 간선을 연결하게 되면 사이클이 형성된다.

이는 신장 트리의 조건에 맞지 않는 상황이 된다.

그래서 가중치가 7인 간선은 연결하지 않고 그 다음 간선을 연결하게 된다.

 

그리고 위의 그림에서 추가된 간선의 수는 총 5개로, 전체 정점의 수보다 하나 적은 상태다.

이 이후로는 간선을 더 이상 추가하지 않아도 된다.

MST가 완성되었기 때문이다.

여기서 알 수 있는 MST의 특성은 다음과 같다

 

간선의 수 + 1 = 정점의 수

 

따라서 이 조건을 만족하면 MST가 완성되었다고 볼 수 있다.

첫 번째 케이스의 경우에는 알고리즘을 구성할 때 다음 사항들이 핵심이 된다.

1) 가중치를 기준으로 오름차순으로 정렬한다.

2) 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가한다.

3) 사이클을 형성하는 간선은 추가하지 않는다.

4) 간선의 수가 정점의 수보다 하나 적을 때, MST는 완성된다.

 

2) 내림차순 정렬, 간선 삭제

두 번째 케이스는 가중치를 내림차순 기준으로 정렬하여 간선을 하나씩 삭제하는 방식을 예로 든다.

 

첫 번째 케이스와는 반대로 간선을 내림차순으로 정렬하여 가중치가 높은 간선들부터 삭제하는 방식이다.

이전에 다뤘던 케이스에서는 사이클이 생성되는 것을 고려하여 간선을 추가했었다.

여기서는 사이클이 생성되는 것을 고려하는 것이 아니라 정점이 연결되지 않는 경우를 고려해야 한다.

위의 예에서는 가중치가 8인 간선을 삭제하려고 했을 때, A와 D가 연결되는 간선이 더 이상 존재하지 않게 된다.

그래서 가중치가 8인 간선은 삭제하지 않고 남겨둔다.

이후에는 첫 번째 케이스와 동일하게 '간선의 수 + 1 = 정점의 수' 를 만족할 때 MST가 완성된다.

 

두 번째 케이스의 경우에는 알고리즘을 구성할 때 다음 사항들이 핵심이 된다.

1) 가중치를 기준으로 내림차순으로 정렬한다.

2) 높은 가중치의 간선부터 시작해서 하나씩 그래프에서 삭제한다.

3) 두 정점을 연결하는 다른 경로가 없을 경우 해당 간선은 제거하지 않는다.

4) 간선의 수가 정점의 수보다 하나 적을 때, MST는 완성된다.

 

[구현]

여기서는 두 번째 케이스를 기반으로 크루스칼 알고리즘을 구현한다.

그리고 기존에 구현했던 코드를 기반으로 수정, 확장해나가는 방식을 채택한다.

https://sevenshards.tistory.com/32

[알고리즘, C] 그래프의 탐색 (DFS, BFS)

 

그래프와 관련된 부분은 DFS, BFS 어느쪽 코드를 사용해도 무방하다.

이전에 작성했던 코드는 BFS 알고리즘을 구현한 코드에서 DFS까지 같이 포함하고 있기 때문이다.

여기서는 DFS 알고리즘을 이용하여 크루스칼 알고리즘에서 해결해야 할 문제를 해결하려고 한다.

"이 간선을 삭제한 후에도 이 간선에 의해 연결된 두 정점을 연결하는 경로가 있는가?"

이 문제를 해결하기 위해서는 기존에 구현했던 DFS 알고리즘을 확장하여 해결할 수 있다.

 

또한, 가중치 그래프를 구현하기 위해서는 가중치가 포함된 간선을 표현한 구조체가 필요하다.

그래서 새로운 헤더파일을 통해 간선의 가중치 정보를 저장하는 구조체를 정의한다.

 

그리고 가중치를 기준으로 간선을 정렬하기 위해 기존에 구현했던 우선순위 큐를 활용한다.

https://sevenshards.tistory.com/10

[자료구조, C] 힙을 이용한 우선순위 큐(Priority Queue) 구현

 

https://github.com/sevenshards00/DataStructure_C

GitHub - sevenshards00/DataStructure_C: 자료구조와 알고리즘 공부 모음 (C언어 기반)

 

이번에는 코드의 양이 많아서 깃허브 주소로 대체를 했다.

열혈 자료구조 폴더에 있는 Ch14-Graph/ALGraphKruskal/ALGraphKruskal에서 전체적인 구현을 해뒀다.

깃허브에 있는 모든 코드는 내가 주석을 달아뒀다.

무작정 따라치기만 한 것이 아니라 이 코드가 어떻게 돌아가는 것인가 이해를 하는 것이 더 중요하기 때문이다.

이해가 안된다면 코드와 주석을 보면서 천천히 이해를 하면 된다.

 

p.s

이로써 열혈 자료구조를 완독했다.

사실 읽기는 어제인 11월 30일에 완독을 했고, 내용을 정리하면서 완전한 마무리를 한 것은 오늘이다.

새벽에 회고하면서도 썼던 내용이지만 앞으로 작성할 내용은 시스템 프로그래밍으로 넘어갈 예정이다.

이 책을 통해서 자료구조와 알고리즘에 대해 전반적인 이해를 할 수 있었다.

물론 이것만 가지고는 부족하다.

앞으로도 다른 책과 정보들을 통해 배웠던 것들을 재차 확인하고 새로 배운 것은 이곳에 기록하고자 한다.