Graph 2

Minimum-cost Spanning Tree

Spanning tree

- connected undirected weighted tree를 말한다

( 모든 점들이 연결되어 있어야 하며 cycle이 없는 tree)

- BFS / DFS 로 찾을 수 있다

- cost : 모든 엣지의 weight의 합

- 점이 n개면 엣지는 n-1개 (당연)

 

-> spanning tree중에서 엣지들의 가중치 합이 최소인 트리를 찾는 알고리즘!

 

1. Kruskal Algorithm - edge를 이용!

- 큭큭. 엣지잇게 엣지중에서 엣지하나선택 ㅋㅋ

 

- 엣지를 오름차순으로 정리

- 젤작은거부터 하나씩 고름 ! 이때 사이클이 발생하지 않을때만 고른다! 모든간선에대해 다하면 끗

or n-1개 고르면 끗

 

복잡도는 O(eloge) (e=엣지 개수)

( = 정렬할때의 복잡도)

 

2. Prim's Algorithm - vertex 이용!

: 시작 점에서 출발해서 점점 확장해나감

- 해당 엣지 set(전부) 에서 연결된 엣지중 가장 작은거 선택 이걸 이어나감

알고리즘

1. 시작점 선택

2. 시작점과의 거리는 0, 나머지는 INF로 초기화

3. 시작 점과 연결된 점중 거리값 최소인애를 선택해서 vertext set에 추가하고 거리를 갱신한다

** 이때 연결되는 점(도착점)이 selected에 잇으면 연결불가인것~~

4.  음..

 

3. Sollin's Algorithm

- 시작하면서 모든 정점을 tree로 가정

- 매 수행때 각 tree마다 간선 하나씩 추가함 ; 최소의 weight가진!

( 중복으로되면 하나만수행)

- 오직 하나의 트리만 존재하게 되면 끝!

( 이트리의 경우는 얘랑해야대고 이트리의 경우읜 얘랑이어야대고..일캐)

복잡도

O ( n log n )

 

---

Shortest Path Algorithm

: 어떤 점에서 다른점까지 가는 path중 shortest path를 찾는 알고리즘!

Dijkstra's shortest path algorithm!

: 시작 노드로부터 다른 모든 노드까지의 최소 비용을 구하는 알고리즘

1. 출발노드 설정

2. 그 노드에서 담노드까지 최소비용 적음

3. 이어진애들중에서 방문 x중에서 가장 비용적은노드 고름

4. 고른노드에서 이제 이어진 다른 노드들로 가는데, 이때 그 다음 노드에 저장되어있는 값과 해당노드+이어진엣지값 이 두개 비교해서 작은걸 넣는다

- 그렇게 검색되면 더이상 해당 알파벳 값은 갱신안함

5. 모든 노드 다하면 끝