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

태그목록

공지사항

최근에 달린 댓글

글 보관함

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  

'공부_2학년 2학기/자료구조'에 해당되는 글 1

  1. 2013.11.19 11/18 자료구조 - Min-Cost Spanning Tree & 길찾기 알고리즘

* 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 다음