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

등록일 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);
*원하는 자료를 검색 해 보세요.
  • 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) 모든 트리
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      [그래프의응용] 그래프의 응용