최소 신장 트리(Minimum Spanning Tree)

MST는 간선에 가중치를 고려하여, 최소 비용의 스패닝 트리를 선택하는 것이다. 

[조건]

• 본래의 그래프의 모든 노드를 포함한다.
• 간선의 가중치의 합이 최소여야 한다.
• 모든 노드가 서로 연결되어 있다.
• 트리의 속성을 만족한다. 즉, 사이클이 존재하지 않는다. 
  *사이클 : 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있는 것을 뜻한다

사이클이 있는 그래프 / 사이클이 없는 그래프

✅ 크루스칼 알고리즘

---

최소 비용 신장 트리를 찾는 알고리즘으로, 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 

최소 스패닝 트리를 찾음으로써 간선의 가중치의 합이 최솟값으로 되도록 하는 알고리즘이다. 

동작원리

1. 모든 간선들을 가중치를 기준으로 오름차순으로 정렬한다.
2. 가중치가 가장 적은 간선을 선택한다.
3. 선택한 간선이 연결하려는 2개의 노드가 서로 연결되어 있지 않은 상태라면, 2개의 노드를 서로 연결한다. 
4. 이 과정을 반복한다. 

동작 과정

• 간선 선택을 기반으로 하는 알고리즘으로, 이전 단계에서 만들어진 신장트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이다. 
• 다음 간선을 이미 선택된 간선들의 집합에 추가할 때, 사이클이 생성하는지를 체크한다. 
• 새로운 간선이 이미 다른 경로에 의해 연결되어 있는 정점들을 연결할 때 사이클이 형성된다. 이때 사이클 생성 여부는 union-find 알고리즘을 이용한다.
  *union-find 알고리즘을 이용하면, 시간 복잡도는 간선들을 정렬하는 시간에 좌우된다. 그래프 내에 적은 숫자의 간선만을 가지는 그래프의 경우 크루스칼 알고리즘이 적합하고, 간선이 많이 존재하는 그래프의 경우 프림 알고리즘이 적합하다.

Union-find 알고리즘 설명 되어 있는 블로그 💁🏻‍♀️https://todaycode.tistory.com/108

✅ Prime알고리즘

---

최소 신장 트리(Minimum Spanning Tree) 구현에 사용되는 알고리즘으로 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장하는 기법이다.

• 최소 신장 트리 알고리즘(MST)
• 정점을 하나씩 늘려감
• 배열로 구현할 경우 시간 복잡도 o(n^2)
• 최소 힙으로 구현할 경우 시간 복잡도 O(Elog n)
• 탐욕법 사용

동작 과정

초기 상태로 정점(=노드)는 서로 연결되어 있지 않다. 정점과 연결된 간선을 하나씩 추가하면서 MST를 만든다.
프림 알고리즘은 시작 정점을 정해 우선 순위 큐에 넣는다. 우선 순위 큐에는 (정점, 가중치) 형식으로 저장되며, 첫 시작은 (시작 정점, 0)으로 넣는다.

 

우선 순위 큐가 빌 때까지 아래를 반복한다.
1) 우선 순위 큐에서 하나를 꺼낸다. 꺼낸 정점을 v라고 하겠다.
2) v가 이미 MST에 포함됐다면 1)로 돌아간다. 그렇지 않다면 아래를 진행한다.
3) v와 연결된 간선을 모두 살핀다. 간선 (w, cost)는 v와 정점 w 사이 연결된 간선이며 cost 가중치를 가진다. 만약 w를 방문하지 않았다면 우선순위 큐에 추가한다.

 

Prime 알고리즘 설명 되어 있는 블로그 💁🏻‍♀️ https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%ED%94%84%EB%A6%BCPrim-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

Union-Find 쉽게 이해하기