[자료구조] 신장 트리

위 이미지를 보면 왼쪽은 그래프이고 오른쪽 세개는 왼쪽에 대한 신장트리이다 

 

• 그래프 상에서 모든 노드가 사이클 없이 연결된 부분 그래프를 뜻함
• 이러한 부분 그래프는 여러개 존재 할 수 있다
• 여러 개의 부분 그래프 중 모든 정점이 최소 간선의 합으로 연결된 부분 그래프
• 모든 정점을 포함하는 트리

그럼 왜? 트리라고 할까

-> 트리는 그래프 중에서 특수한 경우에 해당하는 자료구조이다

즉, 사이클이 존재하지 않는 방향 그래프이다 

 

사이클?  : 순환

 

사이클이 존재하는 그래프를 만약 dfs 탐색을 한다고 하자 그러면 계속 무한으로 탐색을 할 것이다 하지만 사이클이 존재하지 않는다면 모두 다 탐색을 하면 끝나겠죠!

 

 

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

• 신장 트리중에서 가중치 합이 가장 최소인 것을 최소 신장 트리라고 한다
• 간선의 가중치 합이 최소인 트리

 

그럼 이 최소 신장트리는 어떤 알고리즘 문제에 쓰일까?

 

예를들면

• 도시마다 사이에 도로를 만들려고 하는데 최소 거리가 되도록 구축 할때
• 네트워크 망에서 망 사이에 전달하는 시간 및 비용이 최소가 되도록 구축 할때

 

 

최소 신장 트리 알고리즘

최소 신장 트리를 만들기 위한 알고리즘은 총 2가지가 있다

1. Kruscal 크루스칼 알고리즘
   • 간선 중심이다 
   • https://hyeonni.tistory.com/91
2. Prim 프림 알고리즘
   
   • 정점 중심이다

[알고리즘] Kruscal 크루스칼 알고리즘