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

등록일 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
  • 알고리즘트리_01 11페이지
    . 자유 트리 - 한 개의 연결 요소로 이루어진 무방향 그래프의 특수한 ... 형태로서, 어떤 단순 사이클도 갖지 않는 연결 그래프의 일종인 트리를 말한다 ... 자료 부분만 다른 두 개의 트리를 닮은 트리라고 하며 위의 순서트리와
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      상세우측 배너
      상세우측 배너
      추천도서
      [그래프의응용] 그래프의 응용
      하나은행 통장 개설 이벤트 오늘 하루 보지 않기 닫기
      ?>
      닫기