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

등록일 2001.12.14 한글 (hwp) | 8페이지 | 가격 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를 찾으면 최단경로를 찾게 된다.
*원하는 자료를 검색 해 보세요.
  • [OR 최적화] PrimAlgorithm 1 페이지
    // Prim's Algorithm #include < iostream.h > #include < fstream.h > #define N 7 int main() { int start,i,j,k,v1,..
  • Prim Algorithm 5 페이지
    4. Source Code Option Explicit '변수의 선언을 강제로 한다. Option Base 1 '배열의 인덱스 번호의 시작을 1로 설정한다. Dim M As Variant '변수..
  • 자료구조과목의 최단경로 알고리즘입니다. 5 페이지
    /* 프로그램: 최단 경로 알고리즘 한글파일로 보기 힘드실 수 있으니 가급적 Dev-C++이나 Microsoft Visual Studio 2010과 같은 컴파일이 가능한 프로그램에 복사 붙여넣기 하셔서..
  • 최단경로 탐색 6 페이지
    ▣ 문제개요 한 정점에서 다른 한 정점으로 까지의 최단경로를 탐색하고 나타내어라. 정점의 개수와 각 정점 사이의 거리는 사용자로부터 직접 입력받도록 한다. ▣ 문제 분석 및 해결방법 S를 최단경로가 발견된 정점..
  • JAVA 최단경로 9 페이지
    최단 경로 최단 경로 구하기 그래프는 가중치를 가진 유향(방향성이 있는) 그래프를 전제한다. 문제분석 그래프에 대한 가장 기본적인 연산으로는 모든 정점과 변에 대한 처리를 하면서 순환 하는 것이 있다. 이를 위해서는..
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기
      추천도서