크루스칼 알고리즘 (최소 신장 트리)

🟩 최소 신장 트리

신장 트리 중 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘

👉 크루스칼 알고리즘 : 가장 적은 비용으로 모든 노드 연결 가능

 

🌟 신장 트리

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

 

🌟 최소 신장 트리

신장 트리 중에서도 최소한의 비용으로 만들 수 있는 신장 트리

왼쪽 그래프에서 최소 신장 트리를 찾으면 25를 제외한 2개의 간선 (23+13)으로 이루어진 신장트리

즉, 신장 트리의 조건을 만족하면서 최소 비용으로 만들 수 있는 신장 트리

 

🟩 크루스칼 알고리즘 동작과정

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.

2. 간선을 하나씩 확인하면서 현재의 간선이 사이클을 발생시키는지 확인

👉 사이클 발생 여부에 따라, 최소 신장 트리에 포함 여부 결정

3. 모든 간선에 대해 2번의 과정을 반복한다.

 

1. 그래프의 모든 간선 정보만 빼내어 정렬을 수행한다. (원래는 비용을 기준으로 오름차순 정렬한다)

 

2. 비용이 가장 최소인 (3,4)를 선택한 후 3번 노드와 4번 노드에 대하여 union 함수를 수행한다.

 

3. 방문하지 않은 간선들 중 가장 최소인 (4,7)을 선택하여 처리한다.

 

4. 방문하지 않은 간선들 중 가장 최소인 (4,6)을 선택하여 처리한다.

 

5. 방문하지 않은 간선들 중에서 가장 최소인 (6,7)을 선택하여 처리한다. 하지만, (6,7)을 선택할 경우 사이클이 발생하므로 (6,7) 간선을 연결하지 않는다.

 

6. 위와 같은 방법으로 간선을 연결해준 최종결과

 

간선의 비용을 모두 더하면 최종 비용에 해당한다. 총 비용은 159이다.

 

🟩 시간복잡도

간선의 개수가 E개일 때, O(ElogE)의 시간복잡도를 가진다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 그래프의 간선을 나타내는 구조체
struct Edge {
    int src, dest, weight;
};

// 부모 노드를 찾는 함수 (Union-Find 알고리즘)
int findParent(int parent[], int i) {
    if (parent[i] == -1)
        return i;
    return findParent(parent, parent[i]);
}

// 간선의 가중치를 기준으로 오름차순으로 정렬하는 비교 함수
bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

// 크루스칼 알고리즘
void kruskalMST(vector<Edge>& edges, int V) {
    // 결과를 저장할 벡터
    vector<Edge> result;

    // 각 정점의 부모 노드를 저장할 배열
    int parent[V];
    fill(parent, parent + V, -1);

    // 간선을 가중치로 정렬
    sort(edges.begin(), edges.end(), compare);

    int edgeCount = 0; // 결과에 포함된 간선의 수
    int index = 0; // 현재 고려 중인 간선의 인덱스

    while (edgeCount < V - 1 && index < edges.size()) {
        Edge nextEdge = edges[index++];

        int srcParent = findParent(parent, nextEdge.src);
        int destParent = findParent(parent, nextEdge.dest);

        // 사이클을 형성하지 않으면 해당 간선을 결과에 추가
        if (srcParent != destParent) {
            result.push_back(nextEdge);
            edgeCount++;

            // Union 연산 수행
            parent[srcParent] = destParent;
        }
    }

    // 결과 출력
    cout << "Edges in MST:\n";
    for (Edge edge : result) {
        cout << edge.src << " - " << edge.dest << " : " << edge.weight << endl;
    }
}

int main() {
    // 그래프의 정점 수와 간선 수
    int V, E;
    cout << "Enter the number of vertices and edges: ";
    cin >> V >> E;

    // 그래프의 간선 정보를 저장할 벡터
    vector<Edge> edges;

    // 간선 정보 입력 받기
    for (int i = 0; i < E; ++i) {
        Edge edge;
        cout << "Enter source, destination and weight of edge " << i + 1 << ": ";
        cin >> edge.src >> edge.dest >> edge.weight;
        edges.push_back(edge);
    }

    // 크루스칼 알고리즘 호출
    kruskalMST(edges, V);

    return 0;
}