[Data Structure & Alogrithm] MST

📝Spanning Tree

📌 핵심 요약

"스패닝 트리는 원본 그래프의 정점 전부와 간선의 부분 집합으로 이루어진 부분 그래프다. 스패닝 트리의 간선들은 사이클을 이루지 않는다는 특징이 있다."

📌 설명

• 스패닝 트리는 원본 그래프의 정점 전부와 간선의 부분 집합으로 이루어진 부분 그래프다.

• 스패닝 트리의 간선들은 사이클을 이루지 않는다.

📝(MST)Minimum Spanning Tree

📌 핵심 요약

"최소 스패닝 트리는 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리다."

📌 설명

• 최소 스패닝 트리는 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리이다.
• 즉, 그래프의 연결성을 그대로 유지하는 가장 ‘저렴한’ 그래프이다.
• 최소 스패닝 트리를 만드는 알고리즘에는 크루스칼 알고리즘, 프림 알고리즘이 있다.

📌Kruskal’s MST Algorithm

• 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.

• 정렬된 간선 목록을 순회하면서, 가중치가 작은 간선부터 차례로 스패닝 트리에 추가한다.

• 스패닝 트리에 간선을 추가할 때, 해당 간선이 사이클을 유발하는지 확인해야한다.

• Union-Find 자료구조를 활용하여 추가하려는 간선에 대해 Find 연산을 통해 사이클 여부를 판단한다.

• 추가하려는 간선이 사이클을 만들지 않으면 Union 연산으로 스패닝 트리에 추가한다. (두 집합을 합친다.)

📌Prim’s MST Algorithm

• 작성 예정