이 게시글은 윤성우 선생님의 자료구조 강의를 수강 후 나름대로의 내용 정리를 한 것임을 미리 밝힙니다.
스스로의 복습을 위해 작성한 글이므로 심층있는 학습을 위해서는 책의 구매 및 강의수강을 권장합니다.
1. 사이클의 이해
단순 경로란 간선을 중복 포함하지 않는 경로를 말한다.
(최단 경로는 X)
그럼 사이클이란?
시작점과 끝점이 같은 단순 경로를 가리킨다.
이러면 폐공간이 만들어지게 된다.
2. 사이클을 형성하지 않는 그래프
신장트리 (Spanning Tree)
이게 왜 트리냐? 사이클을 형성하지 않으면 이는 트리의 형태를 띄기 때문이다.
(위치를 조정해서 보면 감이 온다. 그리고 어떤게 루트 노드인지 따지는 것은 필요없다. 다만 트리의 형태를 가짐을 이해하는 것이 중요하다.)
3. 최소 비용 신장 트리의 이해와 적용
눈으로 보면 최소 비용 신장 트리가 어떤 것인지 대충 보인다. 이를 만드는 알고리즘을 공부하고 코드를 짜는 것이 우리의 목표이다.
4. 크루스칼 알고리즘 1
쉽게 이야기하면 간선을 다 없애놓고 가중치가 작은 간선들부터 연결해보고 안되면 삭제해가면서 최소 비용 신장 트리 (Minimum cost Spanning Tree)를 만든다.
이 때 신장 트리인지 아닌지를 프로그램으로 검사해야한다.
그 기준은
1. 간선의 수 + 1 은 정점의 수를 만족
2.사이클이 없어야 함
(사이클이 없다는 건 계속 새로운 한 점과 연결된다는 것이고, 사이클 없이 간선의 수 + 1 이 정점의 수이면 신장 트리이다.)
5. 크루스칼 알고리즘 2
크루스칼 알고리즘 1은 간선을 하나씩 더하는 것이라면 크루스칼 알고리즘 2는 간선을 하나씩 빼는 것이다.
빼는 조건
- 홀로 떨어지는 점이 있는지 검사 -> 홀로 떨어지는 점이 생겨서는 절대로 안 된다.
- 신장 트리가 형성이 됐는지 하나씩 빼가며 살펴가는 것
가중치를 내림차순 정렬, 그리고 가장 가중치가 큰 것부터 빼기
고민 - 가장 큰 것을 안 빼고 다른 것을 빼는게 구조상 더 나을 수도 있지 않나?
같은 류의 고민을 크루스칼 알고리즘1에서도 할 수 있다.
+ 구현에서의 고민
1. 크루스칼 알고리즘 1에서 사이클이 있나 없나의 검사
2. 크루스칼 알고리즘 2에서 홀로 떨어지는 점이 있는지의 검사
6. 크루스칼 알고리즘 의 직관적 이해
크루스칼 알고리즘으로 얻은 신장 트리보다 더 작은 비용을 가진 신장 트리가 있다고 가정해보자.
이 때, 크루스칼 알고리즘으로 얻은 신장 트리는 경로 e1을 가지고
더 작은 비용을 가진 신장 트리의 경로 e2를 가지지 않는다고 가정해보자.
이 때 크루스칼 알고리즘 1에 의하면 e2는 먼저 고려대상이었어야 하는데
e2와 e1만이 차이점이라면 크루스칼 알고리즘1에 의해 e2가 추가되었더라도 사이클이 형성되지 않았어야 하므로 크루스칼 알고리즘1에 의해서 e2가 추가되었어야 한다.
따라서 크루스칼 알고리즘으로 만든 스패닝 트리보다 경로 하나만 차이나는 더 작은 비용의 스패닝 트리는 만들어질 수 없다.
그럼 N개의 경로는? N개의 경로일 때도 크루스칼 알고리즘에는 포함되고 더 작은 비용의 스패닝 트리에는 포함되지 않은 e1 ~ eN의 경로보다 작은 비용의 경로 e0가 있을 것이고 이 e0는 무조건 크루스칼 알고리즘1에 의해 포함되었어야 한다.
위의 과정에 의해 크루스칼 알고리즘은 합당함을 알 수 있다.
