<aside> 💡 DFS & BFS, Greedy 알고리즘, 최소 신장 트리

</aside>

AI 서머리

최소 신장 트리

최소 신장 트리란?

• 모든 정점을 포함하면서 사이클이 존재하지 않는 그래프의 부분 그래프 중에서 간선의 가중치 합이 최소인 트리
• 최소 신장 트리는 그래프에서 가장 중요한 연결 요소를 찾는 데 사용된다.

최소 신장 트리 알고리즘

1. Kruskal's Algorithm

• 탐욕적인 방법을 이용한 알고리즘
• 모든 정점들을 독립적인 집합으로 만든다.
• 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
• 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다.
• 모든 간선에 대하여 2~3 과정을 반복한다.

2. Prim's Algorithm

• 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 정점을 선택한다.
• 선택한 정점과 연결된 정점들을 포함하여 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해 나간다.

시간 복잡도

• Kruskal's Algorithm : O(ElogE)
• Prim's Algorithm : O(ElogV)

예시