블로그 이미지
두번째 블로그, 조금은 개인적인 공간;ㅅ;
메시에

태그목록

공지사항

최근에 달린 댓글

글 보관함

calendar

  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      

* Minimum Cost Spanning Tree

 

1. Kruskal's Algorithm

 

- cost가 가장 작은 edge 순으로 선택해 나가서 모든 node를 연결한다.

- edge를 cost 작은 순으로 정렬, 또는 min-heap을 만든다.

 

2. Prim's Algorithm

 

- 초기 상태 : Set A = 출발점 노드

- Set A에서 Set A의 밖에 있는 노드 사이를 잇는 edge들 중에서 cost가 가장 작은 것을 선택하여 연결, 연결된 노드는 Set A에 추가

- 위 과정을 반복하여 모든 노드를 Set A에 넣으면 종료.

 

3. Sollin's Algorithm

 

Step 1)

- 모든 노드가 edge에 연결될 때까지 cost가 작은 순으로 edge를 뽑는다.

- 단, edge가 이어주는 두 노드가 이미 다른 edge에 연결되어 있다면 뽑지 않는다.

 

Step 2)

- Step 1의 결과로 나온 서브그래프들을 잇는다. (cost가 가장 작은 edge 순으로)

 

 

* Shortest Path Problem

 

- Prim's Algorithm의 응용으로, 이미 방문한 노드를 Set에 넣고 다음 노드로 갔을 때의 각 경로별 cost를 따져보면서 진행.

 

이전 1 2 3 4 5 6 7 다음