알고리즘 썸네일형 리스트형 크루스칼 알고리즘 (Kruskal's Algorithm) Minimum Spanning Tree 문제를 해결하기 위해서 보통 두 가지 종류의 알고리즘 중 하나를 선택하여 사용한다. 1. 프림 알고리즘 (Prim's Algorithm) 2. 크루스칼 알고리즘 (Kruskal's Algorithm) 이 두 가지 알고리즘 모두 MST 문제에서 최적의 값을 도출할 수 있음이 이미 증명되어 있다. 이번에는 크루스칼 알고리즘에 대하여 알아보도록 하겠다. 크루스칼 알고리즘은 모든 Edge들에 대해 Weight가 작은 것부터 큰 순으로 Sorting 해놓고 Weight가 작은 Edge부터 MST에 포함시켜 나가는 방식을 사용하는데, 여기에서 핵심은 Edge를 추가했을 때 사이클 생성 여부를 체크하여 사이클이 생성되지 않는 경우 해당 Edge를 MST에 추가한다는 것이다. 모.. 더보기 프림 알고리즘 (Prim's Algorithm) Minimum Spanning Tree 문제를 해결하기 위해서 보통 두 가지 종류의 알고리즘 중 하나를 선택하여 사용한다. 1. 프림 알고리즘 (Prim's Algorithm) 2. 크루스칼 알고리즘 (Kruskal's Algorithm) 이 두 가지 알고리즘 모두 MST 문제에서 최적의 값을 도출할 수 있음이 이미 증명되어 있다. 이번에는 프림 알고리즘에 대하여 알아보도록 하겠다. 프림 알고리즘의 핵심은, 현재 우리가 가지고 있는 MST와 Edge 하나로 직접적으로 연결된 Vertex 가운데 Weight가 가장 작은 것을 추가한다는 것이다. 모든 Edge를 확인했는데 V-1개의 Edge가 선택되지 않은 경우가 있다면 그래프가 Disconnected 되어있다는 뜻이다. 이미 MST에 포함된 Vertex에.. 더보기 이전 1 다음
