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

(2017-09-05)

최소 비용 신장 트리

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

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. 링크 비용

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. 노드 5. 루프 6. 인접 행렬 7. 최단 경로 8. 트리 9. 트리 관련 용어 10. 트리 종류 11. 스패닝 트리 12. 멀티캐스트 트리 13. 이진 트리 14. 트리 순회
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
      1.   프로그래밍 언어론
      2.   객체지향
      3.   자료구조
            1. 자료구조
        1.   선형자료구조(리스트 등)
        2.   비선형자료구조(트리,그래프)
          1.   1. 그래프
              2. 그래프 관련 용어
              3. 그래프 종류
              4. 노드
              5. 루프
              6. 인접 행렬
              7. 최단 경로
              8. 트리
              9. 트리 관련 용어
              10. 트리 종류
              11. 스패닝 트리
              12. 멀티캐스트 트리
              13. 이진 트리
              14. 트리 순회
        3.   자료구조 기타일반
      4.   알고리즘
      5.   자료표현(알파벳/코드)
      6.   시스템 프로그래밍
      7.   프로그래밍언어 종류
      8.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

 
        최근수정     참고문헌