[프로그램 최단경로] 프로그램 최단경로 프림 크루스칼

목차

1. kruskal과 prim 알고리즘을 구현해서 적당한 n(n<=10)에 대하여 임의의 graph를
생성하여 최단 경로 찾기

2.prim's algorithm

3.kruskal's algorithm

아래의 kruskal 알고리즘과 prim 알고리즘 source 실행 결과

output of prim's algorithm source
vertex1: 0 ---> vertex2: 1 , value: 1
vertex1: 0 ---> vertex2: 2 , value: 3
vertex1: 2 ---> vertex2: 4 , value: 1
vertex1: 4 ---> vertex2: 3 , value: 2
vertex1: 2 ---> vertex2: 5 , value: 6
vertex1: 3 ---> vertex2: 6 , value: 4


output of kruskal's algorithm source
vertex1: 0 ---> vertex2: 1 , value: 1
vertex1: 2 ---> vertex2: 4 , value: 1
vertex1: 4 ---> vertex2: 3 , value: 2
vertex1: 0 ---> vertex2: 2 , value: 3
vertex1: 3 ---> vertex2: 6 , value: 4
vertex1: 2 ---> vertex2: 5 , value: 6

본문내용

graph는 교과서에 있는 prim과 kruscal 예제 graph에 몇 개의 vertex와 edge를
추가하여 구현하였습니다. 그리고 소스에 주석을 달아놓았습니다.
tree를 구성하는 것이 목적이 아니므로 tree구성은 단순하게 배열로 하였습니다.
처음에 parent의 초기치로 -100을 넣었습니다. 그 이유는 data가 없는 곳을 구분하기
위해서 입니다. 그러다가 union에서 합칠때 그 data가 root라면 -1을 넣어줍니다.
이 프로그램에서 최단 경로 선택하는 부분은 min heap을 사용하여 찾아냅니다.
cycle의 유무에 대해서는 find와 union 함수를 이용하여 알아냅니다.
구현 소스는 뒷장에 있으며 알고리즘 책과 인터넷 자료실을 참고하여 구현하였습니다.

prim's algorithm
임의의 vertex(이 프로그램상에서는 vertex 0에서 시작)에서 시작하여 그 vertex에서
가장 가까운 vertex를 찾아서 저장한다. 같은 가중치가 2개 이상이면 임의의 vertex를
선택하게 된다. 이러한 방식으로 N-1개의 edge를 찾으면 최단경로를 찾게 된다.

참고자료

· 없음