12-05 최소 신장 트리

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

 

1.최소 신장 트리(Minimum Spanning Tree)

 1)정의

 -그래프의 간선에는 가중치(weight)라는 정점과 정점의 관계를 나타내는 속성 가중치는 거리,비용 등 다양하게 표현 가능하다.

 -신장트리는 기존 그래프의 모든 정점을 포함하고 순환 구조 없이 연결한 트리를 뜻한다.

 -최소 신장 트리는 신장 트리 중 가중치 합이 가장 최소인 최소 신장 트리를 뜻한다.

 

2.프림 알고리즘(Prim Algorithm)

 1)정의

 -그래프의 임의의 정점을 하나 선택하고 정점과 인접한 정점들 중 가중치가 적은 간선으로 연결된

 정점을 선택하여 최소 신장 트리를 만드는 알고리즘.

 

-정점이 추가될 때마다 정점에 연결된 간선을 전부 조사해야 함으로 이에 대한 비용이 꽤 크다는 단점이

있다.

3.크루스 칼 알고리즘(Kruskal's Algorithm)

 1)정의

 -그래프의 모든 간선을 조사하고 사전에 파악하고 이 정보를 토대로 최소 신장 트리를 만드는 알고리즘.

 -순환구조가 형성되는 것을 해결하기 위해 정점을 다수의 분리집합으로 만들면서 트리를 만든다.

4.최단 경로 탐색 : 데이스크라 알고리즘

 1)정의

 -그래프에서 사용되는 정점과 정점 사이의 최단 거리를 찾는 알고리즘.

 2)과정