[C언어] 자료구조 - 가중치 그래프 Weighted Graph + Kruscal - 1

그래프에 대해서 많이 배웠는데 이제 진짜로 적용하려면 가중치 그래프라는 것을 배워야한다.

영어로는 위에 제목에 써놨다.

가중치 그래프라는 것은 간선에 비용이나 가중치가 추가된 그래프를 말하는데

이는 정점 사이의 연결상태뿐만 아니라 연결에 필요한 비용까지 함께 표현할 수 있다.

 

여기서 비용이란 꼭 돈이아니라 무엇이든 될 수 있는거다.

정말 돈이 될 수도, 아니면 간선의 길이가 될 수도 있는 것이다.

이렇게 도로를 표현하는 그래프에서는 도로의 길이를 표현하면 좋겠지??

뭐 이렇게 지도로도 쓰일 수 있고, 사실 네트워크같은 곳에 많이 쓰인다고 한다.

예를 들어 지도에서 최단거리를 가고싶다..? 그렇다면 목적지까지 경로에서 가중치의 합이 가장 적은 경로가

가장 최단거리가 되겠지??

 

 

---

 

우선 그렇다면 가중치 그래프를 어떻게 구현할 것인가를 생각해보자. 그래프는 배열과 연결리스트로 구현했다.

얘도 똑같이 구현할 수 있겠다 라고 생각하면 굿

 

우선 배열을 통해 구현한다면 2가지 방법이 있다.

 

1. 가중치배열을 만드는 것

2. 기존 배열에서 가중치를 바로 저장하는 것

 

1번에서는 2차 행렬을 또 만들어서 구현해야하는데, 좀 그렇잖아.. 배열 또만들기 귀찮아ㅠㅠㅠ

그래서 우린 2번을 해보자.

그니까 우리는 방문했을 때 1을 집어넣었잖아. 그런것처럼 이제 간선에다도 값을 집어넣을거야.

 

간선이 있는 경우에는 양수의 값을 넣어주도록 하고

간선이 없는 경우에는 매우 큰값을 넣어주도록 하자.

 

이런 식으로 표현된다는 것인데 우선 저렇게 그림과 표를 그렸지만 실행할 때는

 

실제로 간선이 없는 부분은 메모장에서 불러올 때는 0으로 선언해부렀다. ㅎㅎ 무한대를 어떻게써 ㅋㅋㅋ

 

사실 파일 불러와서 출력하는 함수도 코드로 써주고싶은데,, 너무 힘들어...

 

 

 

 

.. 아무튼 이러한 가중치그래프로 뭐할지 더 생각해보면?

 

신장트리를 배웠듯이 가중치를 가진 신장트리를 생각해보면...?

 최소비용을 가진 신장트리를 만들어야겠다. 라고 생각하면 굿굿

 

 

 

가장 많이쓰이는 그래프가 뭔가 생각해보면 통신망, 도로망, 유통망 같이

최소의 비용으로 최대의 효과를 꾀하는 그러한 분야에서 이러한 최소비용 신장그래프를 쓸 것 같다.

 

---

 

 

영어로 (MST: minimum spanning tree)라고 한다. 

최소비용 신장트리라는 것인데 조건은 신장트리의 조건과 거의 똑같다.

 

 

 

 

1. 반드시 n-1개의 간선으로 n개의 노드를 연결해야한다.

2. 사이클이 포함되어서는 안된다.

3. 간선의 가중치의 합이 최소여야한다.

 

그렇다면 어떤 방법으로 최소비용 신장트리를 만들까?

그 때 그대로 그냥 깊이탐색, 너비탐색으로 가능할까??

 

걔네들은 가중치를 고려하지 않은 탐색이기에 불가능하고 다른 알고리즘이 있다.

 

Kruskal 과 Prim 이라는 알고리즘이 있다.

설명하고 코드를 통해서 알아볼 것인데 좀 어려울 수 있으니 집중해야한다.

 

우선 Kruskal 부터

이 알고리즘은 "그 순간에 최적" 이라는 모토를 가지고 

정점에 방문했을 때(순간) 간선 중 가장 낮은 가중치의 간선 선택(최적) 의 누적으로

최소비용 신장트리가 만들어지는 것이다. 또한 이 방법은 최적의 해답을 주는 것으로 증명을 누군가가 했다고 한다.

// 우리는 믿고 쓴다.

 

 

 

말로 표현하자면

1. 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다.

2. 가장 가중치가 작은 간선 e를 뽑는다.

3. e를 넣어 신장트리에 사이클이 생기면 넣지 않고 2번으로 이동한다.

4. 사이클이 생기지 않으면 최소 신장 트리에 삽입한다.

5. n-1개의 간선이 삽입될 때 까지 2번으로 이동한다.

 

이런식으로 가중치를 오름차순으로 정렬해놓고. 그때마다 최적의 길을 선택하는 것이다.

 

 

---

 

 

근데 여기서 문제점이,,, 위에서는 순차적으로 골랐을 때 x나온 부분이 있다. 

사이클이 생겨서 x부분을 만든 것인데 이것을 어떻게 골라낼 것이냐...? 가  문제다.

그래서 다른 사람이 이것에 대한 해결책을 제시했는데

"지금 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해있는지를 판단" 이 판단하는 함수를

Union-Find 라고 부르는데 이러한 함수는 다른 곳에도 쓰인다.

 

 

 

이런식으로 추가할 때 같은 집합(왼쪽) 이면 추가 ㄴㄴ 집합이 다르면(오른쪽) 추가 ㅇㅇ

 

그럼 어떠한 방식으로 Union-Find가 구동이 되는지 알아보자. 

2가지 기능이 있는데

 

1. Find

원소가 속하는 집합이 무엇인지 알아냄

 

2. Union

집합을 입력받아서 합집합을 만드는 연산이라한다.

 

 

예를 들어서 1,2,3,4,5,6 있다고 치자

그리고 union(1,4) union(2,5) 를 선언하면

(1,4) ,(2,5) 3,6 이런식으로 합집합이 된다.

 

또한 그리고 여기서 

union(4, 5}와 union(3, 6) 처리한다면??

즉 4,5 의 집합이 무엇인지 입력받아서 4,5의 합집합을 만든다.

3,6 또한 같다.

 

 

코드로 알아본다면

 

최종부모노드 ㅋㅋㅋㅋ 말도 이상한데 그냥 그 집합 트리의 루트?? 이런식으로 생각하면 될듯

 

또한 사이클은 이렇게 피한다 생각하고

그렇다면 최소 간선은 어떻게 선택하느냐??

 

간선을 오름차순으로 정렬해야하는데 어떻게 정렬할까..?

정렬은 뭐 나중에 또 배우긴하는데 이미 배운 최소 힙으로 min heap으로 정렬해보자.

 

즉 힙에서 꺼낼 때 마다 항상 작은 값이 나올 수 있겠지?? ㅋㅋㅋㅋ 최소힙이니까

 

그렇다면 Kruscal 을 구현할 준비는 끝마쳤다. 진짜로 구현하면 어떻게 될지 코드로 보자

 

 

실행결과는??

 

 

 

 

후,,, Prim은 다음에 알아보도록 하자ㅎㅎ ㅃㅃ