Spanning Tree, Minimum Spanning Tree Algorithm   스패닝 트리, 신장 트리, 생성 트리, 최소 신장트리 알고리즘

(2017-09-05)

최소 비용 신장 트리

Top > [기술공통]
[기초과학]
[진동/파동]
[방송/멀티미디어/정보이론]
[전기전자공학]
[통신/네트워킹]
[정보기술(IT)]
[공학일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
정보기술(IT) >   1. 정보기술
[전산기초]
[컴퓨터구조]
[프로그래밍]
[데이터베이스]
[소프트웨어 공학]
[운영체제]
[정보보호/보안]
[IT 기타기술]
프로그래밍 >   1. 프로그램, 프로그래밍
[프로그래밍 언어론]
[프로그래밍 방법론]
[객체지향 프로그래밍]
[자료표현코드]
[자료구조]
[알고리즘]
[시스템 소프트웨어]
[프로그래밍언어 종류]
[프로그래밍 기타일반]
자료구조 >   1. 자료구조
  2. 자료구조 종류
[선형 자료구조 (리스트 등)]
[비선형 자료구조 (트리,그래프)]
[기타 자료구조]
[자료구조 기타일반]
비선형 자료구조 (트리,그래프) > [그래프]
[트리]
그래프 >   1. 그래프
  2. 그래프 종류
  3. 그래프 표현
[그래프 용어]
[그래프 알고리즘]
그래프 알고리즘   1. 그래프 알고리즘
  2. 그래프 순회
  3. 최단 경로
  4. 최소비용 신장트리

Top > [기술공통]
[기초과학]
[진동/파동]
[방송/멀티미디어/정보이론]
[전기전자공학]
[통신/네트워킹]
[정보기술(IT)]
[공학일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
통신/네트워킹 >   1. 통신 이란?
  2. 신뢰적 통신
[통신이론]
[선로/전송]
[통신망 일반]
[회선교환(PSTN)]
[무선/이동통신]
[광통신]
[인터넷/데이터통신]
인터넷/데이터통신 >   1. 데이터통신망
  2. 인터넷
  3. 데이터 네트워크 설계
[데이터 단위]
[프로토콜/계층]
[데이터 링크]
[TCP/IP]
[라우팅]
[인터넷 QoS]
[인터넷 관리]
[웹기술]
[인터넷 응용]
[인터넷 기타]
[패킷교환(PSN)]
[인터넷 관련 기관]
데이터 링크 >   1. 데이터 링크
  2. 데이타링크 계층
[데이터링크 제어]
[데이터링크제어프로토콜]
[LAN (유선)]
LAN (유선) >   1. LAN 이란?
[이더넷]
[브리지]
[스위칭/스위치]
[VLAN]
브리지 >   1. 브리지
  2. Brouter
  3. 브로드캐스트 스톰
  4. 충돌 도메인
  5. 포워딩
  6. 플러딩
  7. 혼잡모드
  8. 투명 브리지
  9. 브리지 테이블
[STP(Spanning Tree)]
STP(Spanning Tree)   1. STP(스패닝 트리 프로토콜)
  2. BPDU
  3. 루트 브리지
  4. 브리지 ID
  5. 스패닝 트리
  6. 브리지 루프
  7. 링크 비용

Top > [기술공통]
[기초과학]
[진동/파동]
[방송/멀티미디어/정보이론]
[전기전자공학]
[통신/네트워킹]
[정보기술(IT)]
[공학일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
정보기술(IT) >   1. 정보기술
[전산기초]
[컴퓨터구조]
[프로그래밍]
[데이터베이스]
[소프트웨어 공학]
[운영체제]
[정보보호/보안]
[IT 기타기술]
프로그래밍 >   1. 프로그램, 프로그래밍
[프로그래밍 언어론]
[프로그래밍 방법론]
[객체지향 프로그래밍]
[자료표현코드]
[자료구조]
[알고리즘]
[시스템 소프트웨어]
[프로그래밍언어 종류]
[프로그래밍 기타일반]
자료구조 >   1. 자료구조
  2. 자료구조 종류
[선형 자료구조 (리스트 등)]
[비선형 자료구조 (트리,그래프)]
[기타 자료구조]
[자료구조 기타일반]
비선형 자료구조 (트리,그래프) > [그래프]
[트리]
트리   1. 트리
  2. 트리 용어
  3. 트리 종류
  4. 이진 트리
  5. 이진 탐색 트리
  6. 스패닝 트리
  7. 트리 순회
  8. B 트리
  9.
  10. 멀티캐스트 트리

1. 스패닝 트리 / 신장 트리 / 생성 나무 (Spanning Tree)루프가 없는 그래프
     - 일종의 루프 순환(looping, 예: Bridge Loop)을 방지하게되는 트리
        . 한 노드에서 다른 노드에 이르는 경로가 오직 하나 뿐인 토폴로지
           .. (트리 : 노드 및 가지로 형성되는 그래프의 특수한 경우를 일컬음)


2. 스패닝 트리 구조 (Spanning Tree Structure)

  ㅇ 최상의 정점(중심)을 루트(Root Node)로 하고, 
     - 모든 그룹 멤버들을 자손으로 갖는 트리구조


3. 최단 경로 스패닝 트리 (Shortest Path Spanning Tree)

  ㅇ 루트로부터 리프(Leaf Node)까지의 경로가 가장 짧도록 최적의 트리가 되도록하는 것


4. 최소 비용 신장 트리, 최소 신장 트리
   (Minimum Cost Spanning Tree, Minimum Spanning Tree, MST)

  ㅇ 신장 트리 중 모든 간선의 가중치 합이 최소

  ㅇ 특징 : (간선의 수 + 1) = (정점의 수)


5. 최소비용 신장트리 생성 알고리즘

  ㅇ 크루스칼(Kruskal) 알고리즘
     - 가중치로 간선을 정렬한 후 사이클이 형성되지 않도록 간선을 하나씩 선택 또는
       삭제하며 신장트리 그래프를 만들어감
 
  ㅇ 프림(Prim) 알고리즘
     - 하나의 정점을 시작으로 트리를 점차 확장시켜가며 신장트리 그래프를 만들어감

  ※ 참고용어 ☞ 스패닝 트리 프로토콜


[그래프 알고리즘] 1. 그래프 알고리즘 2. 그래프 순회 3. 최단 경로 4. 최소비용 신장트리

 
        최근수정     요약목록     참고문헌