[자료구조] 최소 신장 트리(MST: Minimum Spanning Tree)란

 

최소신장 트리(MST: Minimum Spanning Tree)란

• 그래프의 정점이 다 포함되어있는 트리( 신장 트리 (spanning tree))
• 가중치 그래프가 주어질 경우 간선들의 비용 합이 최소가 되는 신장 트리
• cycle이 발생하면 안됨

위 그래프의 최소신장 트리

 

 

그래프란

→ 노드(정점 vertex)와 그 노드를 연결하는 간선을(edge) 하나로 모아놓은 자료구조

• 무방향 그래프: 간선이 방향이 없는 그래프
• 방향 크래프: 간선의 방향이 있는 그래프

그래프의 표현 방법

1. 인접 행렬
2. 인접 리스트

인접행렬

가중치 그래프란

• 그래프의 간선에 가중치(weight)를 부여한 것

트리란

→ 그래프의 한 종류

→ Cycle이 불가능 (그래프에서 사이클(Cycle)이란 어떤 특정 정점에서 출발하여 간선과 정점들을 지 나 다시 처음에 출발했던 특정 정점으로 되돌아오는 것을 말한다.)

→ 부모 - 자식 관계

cycle이란

• if vertex의 집합을 {v1,v2,v3,v4,v5,v6}가 있다면
• 특정 정점 vi에서 시작해서 다시 vi로 돌아오는 경로(path)가 있을 시
  → 그 경로를 cycle이라고 부른다.

• 이 그림에서 다양한 cycle이 있지만 한가지 예를 들어보면
  • path : 0 → 4 → 2 → 1 → 0 이 있다.

cycle이 발생 확인 알고리즘(이 글에선 다루지 않음)

1. DFS/BFS
2. Union/find 기법

최소신장트리를 구성하는 알고리즘

1. Prim 알고리즘
2. Kruskal 알고리즘

• 위 알고리즘들은 가중치 그래프에서 최소신장트리를 구성하는 알고리즘이다.
• 2개는 대표적인 greedy알고리즘으로 다른 글에서 다루도록 하겠다.