▶ 스패닝 트리 알고리즘 (Spanning Tree Algorithm)
- 네트워크 루핑이 발생할 수 있는 경우를 예측하여 사전에 루핑 현상을 예방하기 위한 목적으로 설계된 알고리즘
- 루핑이 발생이 가능한 예상 지점의 스위치 간의 연결을 끊는 방법으로 해결
- 루핑을 미리 막기 위해 두 개이상의 경로가 발생하면 하나를 제외하고 나머지 경로들을 자동으로 막아두었다가 기존 경로에 문제가 생기면 막아 놓은 경로를 이용해 데이터를 전송하는 알고리즘
▶ 최소 신장 트리 (MST - Minimal Spanning Tree)
- 한 버텍스를 기준으로 가능한한 작은 가중치의 아크들을 사용해 모든 버텍스를 연결하는 트리를 만듦
- 최소의 아크값을 사용해 버텍스를 연결
- 오른쪽 그림은 13 가중치의 아크들로 모든 버텍스를 연결, 이런 모양의 트리를 최소 신장 트리라고 명명함
- 최소 신장 트리를 구하는 대표적인 알고리즘은 크루스칼 알고리즘(Kruskal Algorithm)과 프림 알고리즘(Prim Algorithm)이 있음
▶크루스칼 알고리즘 (Kruskal Algorithm)
- 무향 연결 그래프가 주어질때 '최소 스패닝 트리' 서브 그래프를 찾는 알고리즘
- 유니온 파인드 자료구조를 사용함
Step 1) 모든 간선을 끊음
Step 2) 가중치 순으로 간선 정렬
Step 3) 정렬된 간선을 순서대로 선택
ex) 2-3은 연결되어 있지 않으므로 선택된 간선을 통해 연결 - 정점 : 2-3, 가중치 : 2
Step 4) 선택한 간선의 두 정점이 연결되어 있지 않으면 해당 간선을 최소 스패닝 트리에 포함시키고 두 정점을 연결
아래의 그래프는 크루스칼 알고리즘을 이용해 최종적으로 연결된 최소 스패닝 트리 그래프이다.
이미지 출처
'현대리가 생각하는 IT' 카테고리의 다른 글
| IP 주소 클래스 (Class A, B, C) (0) | 2018.09.28 |
|---|---|
| IPv4, IP Address Network/Host Part (0) | 2018.09.28 |
| 네트워크 루핑 (Network looping) (0) | 2018.09.20 |
| 네트워크 스위치 (Switch) (0) | 2018.09.19 |
