최소비용신장트리(MCST)와 최단거리찾기 [우선순위 검색 방법에 의해]

MCST [Minimum Cost Spanning Tree]

신장트리(Spanning Tree) : 모든 정점(노드)을 방문하는 트리

트리 : 사이클이 없는 그래프를 말한다

그런데 간선에 비용이 있다 => 모든 정점을 방문하면서도 간선의 비용의 합이 최소인 트리를 신장트리라 한다

MCST = Minimum cost spanning tree

최소비용 신장트리로 알려진 알고리즘 들에는

1. 우선순위 탐색

2. Kruskal

3. Sollin

4. Prim

etc...

[1,2 가 성능이 좋다]

---

최소비용신장트리 - 우순순위 검색 에 의한 방법

( PrioityQueue 가 필요 ( PrioityQueue 는 힙으로 만든 것이 적절하다 Heap 은 O(logN)의 성능을 갖는다) )

* 비용을 우선순위로 둔다

모든 노드를 연결하는데 가장 최소의 비용으로 모든 노드를 연결하는 방법

간선 자체를 우선순위로 보고 비교한다

[C++ 알고리즘 참고]

---

[최단경로찾기 ]

A 부터 Z 까지 가는 길 중에 각 길마다 비용이 있고 가장 적은 비용으로 Z 까지 가는 비용을 얻기 위한 방법

* 누적으로 최단 경로를 구한다

먼저

출발점이 A 라면 A 와 인접한 것들을 우선순위 큐에 넣고 ( 이때 우선순위 큐에는 가작 작은 값이 최 상단에 위치하게 한다)

p 큐 가장 위에 있는 것을 뽑아와서 선을 연결 한다

뽑아온 노드의 인접 노드를 다시 p큐에 넣는다

이때!! 큐에 넣기전 현재 도착 노드가 p큐에 있는지 보고 p큐에 도착 노드가 있다면 이제까지 누적해온 경로의 길이를

비교해봐서 p큐보다 값이 작다면 기존 p큐에 있는 노드를 지우고 누적값이 적은 노드값으로 대체한다

- 최소 비용으로 모든 정점을 연결하는 방법