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

등록일 2001.12.14 한글 (hwp) | 9페이지 | 가격 1,100원

목차

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를 찾으면 최단경로를 찾게 된다.
*원하는 자료를 검색 해 보세요.
  • 크루스칼 10페이지
    Prim 알고리즘을 구현하라. ▣ 문제분석 및 해결방법 크루스칼 알고리즘은 ... 개의 간선이 T에 포함된다. 프림알고리즘은 크루스칼의 졍우처럼 한번에 ... 각 단계의 선택된 간선의 집합은 포리스트를 이룬다, 프림알고리즘은
  • [컴퓨터 알고리즘]알고리즘 연습문제 4장 5페이지
    ]); } } } /* 프림 알고리즘 */ void prim(int n,int datas ... ",e); } 6. 크루스칼 알고리즘을 사용하여 연습문제 2의 그래프의 ... 최소비용신장트리를 구하고, 수행되는 절차를 단계별로 구하라. 크루스칼
  • [자료구조]프림(prim)알고리즘 4페이지
    . 크루스칼 알고리즘은 구현을 하지 못했습니다. 죄송합니다. ..FILE ... 0~v4로 수정. 1-2. 프림의 알고리즘 소스 #include ... ..FILE:PRIM'S.cpp #include
  • 알고리즘(3판)(FOUNDATION OF ALGORITHMS USING C++ PSEUDOCODE) 4장 연습문제 11페이지
    트리를 가진 그래프를 하나 그려라 ㆍ6 크루스칼 알고리즘을 사용하여 2번 ... 음선을 나타낸다고 가정하자. < 가중치 그래프 > v4에서부터의 최단경로 ... [스템프 찍기] 4장 연습문제 ㆍ2 프림 알고리즘을 이용하여 다음
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      상세우측 배너
      추천도서
      [프로그램 최단경로] 프로그램 최단경로 프림 크루스칼