Kruskal의 MST 알고리즘

Kruskal이 MST 알고리즘

- 탐욕적인 방법(greedy method)

• 주요 알고리즘 설계 기법
• 각 단계에서 최선의 답을 선택하는 과정을 반복함으로써 최종적인 해답에 도달
• 탐욕적인 방법은 항상 최적의 해답을 주는지 검증 필요
• Kruskal MST 알고리즘은 최적의 해답 임이 증명됨

최소비용 신장 트리 : cycle 안생기는 선에서 최소 값 간선 선택

 

int set_find(정점) : 대표정점을 반환

void set_union(대표정점1, 대표정점2) : 두 집합을 합하며 대표 정점 정한다.

void set_init(n) : 독립적인 집합을 만들어줌

 

- Kruskal 알고리즘은 대부분 간선들을 정렬하는 시간에 좌우됨

- 네트워크의 간선 e개를 퀵정렬과 같은 효율적인 알고리즘으로 정렬한다면 Kruskal 알고리즘의 시간 복잡도는 O(e2)이 된다.

- 힙으로 하면O(eloge)

 

Prim의 MST 알고리즘

- 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나감

- 신장 트리 집합에 인접한 정점 중에서 최저 간선으로 연결된 정점 선택하여 신장 트리 집합에 추가함

- Prim은 시작정점 있음(정점 선택기반), <신장트리집합>에서 모든정점이 선택될 때까지 가까운정점 선택 

- //Kruskal은 시작정점x(간선 선택기반), 최소간선 선택(n-1개의 간선), O(eloge)

- dist[u]: 신장트리집합에서 정점u까지의 최소거리이다.

- selected[u] : u<-1 로 만든다. when? 신장트리집합에 넣을때.

- 밀집한 그래프, 간선이 많은 경우 Prim알고리즘이 유리

- //희박한 그래프는 Kruskal이 유리

 

Dijkstra의 최댄경로 알고리즘

- 각 단계에서 S안에 있지 않은 정점 중에서 가장 distance값이 작은 정점을 S에 추가한다.

- 시작점부터 모든 다른 정점까지의 최단거리