[그래프의응용] 그래프의 응용

등록일 2003.09.18 한글파일한글 (hwp) | 2페이지 | 가격 1,000원
다운로드
장바구니관심자료
상세신규 배너

목차

없음

본문내용

최소경비 신장트리(MST)
그래프의 모든 노드를 연결하고 그 가중치의 합이 최소인 신장트리
<정의>: 최소경비 신장트리
가중치 그래프 G=(V, E, W)에서 경로 P=(v0, v1,..., vn)가 있는 서브 그래프의 가중치의 합
가 최소인 비싸이클 그래프를 최소경비 신장트리(MST)라 한다.
Kruskal 알고리즘
T: n 노드로 구성된 노드의 집합으로 초기에는 empty
E: 에지의 집합으로 초기에는 모든 에지를 포함
while (edge_nr(T)<n-1 and E≠ε) do
- E로부터 가중치가 최소인 에지 (v, w)∈E를 택한다.
- E=E - {v, w)
- 그리고 (v, w)가 T에서 싸이클을 이루지 않으면 T=T∪{w}
od
if (T가 n-1에지 보다 적은 에지를 갖으면)
then
printf("no spanning tree");
Prim 알고리즘
1) 그래프에서 임의의 출발 노드 x를 정한다. 그리고 다음과 같이 초기화한다.
V1={x}; // 신장트리를 구성하는 노드집합
V2={0}; // V1에 속한 노드들에 인접해 있는 후보노드 집합
V3=V-{V1}; // 아직 신장트리와 무관한 노드의 집합
E1={0}; // 신장트리를 구성하는 에지집합
E2={0}; // (V1, V2)의 관계에 놓인 후보에지로서 같은 노드에 두개의
에지가 있을 경우에는 최소 가중치를 갖는 에지로 구성.

2) while (V1≠V) do // 그래프의 모든 노드가 신장트리를 구성할 때까지
2.1) 정해진 노드로부터 신장트리를 구성할 수 있는 후보에지와 노드를 결정
2.1.1) for (x∈V1 and y∈V2: ∃(x, y)) do // 중첩 후보에지 결정
if (모든 x∈V1에 대해서 노드 y에 에지가 여러개 있으면)
- 가중치가 가장 작은 에지만 남겨두고 모든 에지를 후보에지에서 삭제한다.
E2=E2-{e}∪(x, y)
2.1.2) for (x에 인접한 노드 z∈V3에 대하여) do // 후보노드 결정
{ V2=V2∪{z};
V3=V3-{z};
E2=E2∪(x, z);
  • 구매평가(0)
  • 구매문의(0)
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.

      찾던 자료가 아닌가요?아래 자료들 중 찾던 자료가 있는지 확인해보세요

      • 한글파일 C로 배우는 쉬운 자료구조 9장 연습문제 그래프 솔루션 답(1~5) 2페이지
        : 3. 다음 그래프의 깊이 우선 신장트리와 너비 우선 신장 트리를 구하여라 ... 치 그래프의 최소 비용 신장 트리를 구하여라. ⇒ 최소 비용 신장 트리 5 ... ②큐 ③트리 ④연결리스트 ⑤그래프 ① 비선형구조 : ①,②,⑤ 선형구조
      • 파일확장자 [자료구조] 자료구조(일반트리와 이진트리) 18페이지
        트리의 개요 (1) 정의 · 트리는 연결된 비순환 그래프의 일종이다 ... (비선형 구조).· 트리 구조는 나무나 족보에서 보는 것처럼 노드 사이의 ... 관계가 계급적 관련성을 갖는다.· 트리는 정점에서의 가지수에 따라 이진 트리와 m-원 트리로 나뉜다.
      • 한글파일 트리와 그래프에 관한 레포트 31페이지
        ) 6. 그래프의 응용 ... . 그래프의 정의 ... ) 2. 그래프의
      • 파워포인트파일 트리란 무엇인가 - 발표자료 18페이지
        계층적 자료구조 4/18 트리 (Tree) 그래프의 한 종류 번호 있는 ... 무방향 그래프의 일종 9/18 순서 트리 같은 레벨에 있는 노드들의 좌우배열 ... C D 결론 트리란 ? 비선형 , 계층적 , 비순환형 그래프 자료
      • 한글파일 자료구조 15페이지
        자료구조 2. 그래프의 개요 1 자료 객체(data object)들 ... 구조는 같고 노드의 자료 일부분만 다른 경우 4 대등(동등)한 트리 ... 처리응용 문제를 효과적으로 표현할 수 있는 자료구조 8. 자료구조 선택기준
      • 한글파일 알고리즘 그래프(Graph) 4페이지
        - 그래프를 운행한다는 것은 트리의 운행처럼 그래프의 각 노드를 안 빠지고 전부 ... 그래프(Graph) 1. 그래프의 정의와 종류 (1) 그래프 ... (Topology)이 중요하다고 말할 수 있다. (2) 그래프의 용어 ① E(G
      • 한글파일 자료구조 그래프 과제물 10페이지
        자료구조 과제물 <그래프> 컴퓨터공학과 ○◇△ 2015.03.10 ... 있는 객체간의 관계를 표현할 수 있는 자료구조다. (2) 그래프는 정점 ... 간선도 V1과 V2로만 이어지는 그래프를 말한다. (4) 모든 트리
      더보기
      상세하단 배너
      우수 콘텐츠 서비스 품질인증 획득
      최근 본 자료더보기
      상세우측 배너
      추천도서yes24
      다음
      [그래프의응용] 그래프의 응용