[Algorithms] Minimum spanning tree 알고리즘

우선 Spanning tree의 정의에 대해서 되돌아볼 필요가 있다. 스패닝 트리는 어떠한 그래프의 서브그래프이면서 그래프의 모든 버텍스를 포함하는 트리이다. 그러한 그래프가 edge에 weight를 가질때, weight의 합을 최소화하는 스패닝 트리를 Minimum spanning tree라 하며 그것을 구하는 알고리즘으로 Prim's algorithm과 Kruskal's algorithm이 있다. 위 두가지 방법은 Greedy Approach를 이용하여서 각자의 기준을 가지고 스패닝 트리를 만들게 된다. 우선 첫째로, Prim의 알고리즘은 하나의 버텍스에서 시작하여 인접한 버텍스 중 가장 웨이트가 작은 엣지로 연결된 버텍스를 선택하고 연결한다. 여기에서 인접한 버텍스 중 가장 웨이트가 작은 엣지로 연..
Computer Science 2011. 7. 7. 19:39
1