[자료구조] minimum spanning tree - prim's algorithim, kruskal's algrithm

자료구조

by ~지우~ 2022. 7. 4. 13:30

728x90

최소의 총 가중치를 갖는 spanning tree를 찾는 방법 중 prim's algorithim과 kruskal's algrithm에 대해 알아보겠다.

spanning tree에 대한 글은 아래 참고

[자료구조] spanning tree (sub graph)

spanning tree: 그래프에서 cycle이 제거된 sub graph -Depth First Traversal을 이용해 spanning tree 만들기 먼저 DFS방식으로 그래프를 순회한다. 위의 그림에서 서로 연결된 노드들만 그래프에서 다시 연결..

jicoding.tistory.com

- Prim's algorithm

1. undirected graph에서 하나의 시작 노드를 정한다.

2. 모든 인접한 노드중에서 가장 작은 가중치를 가진 edge를 선택한다.

3. 선택된 노드를 포함해서 모든 인접한 노드로 위의 과정을 계속 반복한다.

4. 그래프의 모든 노드가 포함되면 종료한다.

노드 G를 시작점으로 잡고 Prim's algorithm을 실행하면 다음과 같은 결과가 나온다.

선택이 가능한 인접한 edge는 분홍색 하이라이터로 표시하고 선택된 노드와 edge는 빨간펜으로 표시했다.

Prim's algorithm 실행 결과, 선택된 edge는 달라도 되지만 선택된 edge의 총 합은 같아야 한다.

- Kruskal's algorithm (greedy algorithm)

1. undirected graph의 모든 노드중에서 가장 작은 가중치를 가진 edge를 선택한다.

2. 모든 노드로 계속 위의 과정을 반복한다.

3. 그래프의 모든 노드가 포함되면 종료한다.

Kruskal's algorithm을 실행하면 다음과 같은 결과가 나온다.

선택된 edge는 빨간펜으로 표시했다.

Kruskal's algorithm 실행 결과, 선택된 edge는 달라도 되지만 선택된 edge의 총 합은 같아야 한다.

728x90