C++에서 최소 신장 트리 알고리즘을 사용하는 방법

C++에서 최소 스패닝 트리 알고리즘을 사용하는 방법

최소 스패닝 트리(MST)는 그래프 이론에서 중요한 개념으로 무방향 연결 그래프의 모든 정점을 연결하는 간선의 하위 집합을 나타냅니다. 이 모서리의 가중치는 가장 작습니다. Prim 알고리즘, Kruskal 알고리즘 등 최소 신장 트리를 해결하는 데 사용할 수 있는 알고리즘이 많이 있습니다. 이 기사에서는 C++를 사용하여 Prim의 알고리즘과 Kruskal의 알고리즘을 구현하는 방법을 소개하고 구체적인 코드 예제를 제공합니다.

Prim의 알고리즘은 그리디 알고리즘입니다. 그래프의 정점에서 시작하여 현재 최소 스패닝 트리에 연결된 가중치가 가장 작은 가장자리를 점차 선택하여 최소 스패닝 트리에 가장자리를 추가합니다. 다음은 Prim 알고리즘의 C++ 코드 예입니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1e9;

int prim(vector<vector<pair<int, int>>>& graph) {
    int n = graph.size(); // 图的顶点数
    vector<bool> visited(n, false); // 标记顶点是否已访问
    vector<int> dist(n, INF); // 记录顶点到最小生成树的最短距离
    int minCost = 0; // 最小生成树的总权值

    // 从第一个顶点开始构建最小生成树
    dist[0] = 0;

    // 使用优先队列保存当前距离最小的顶点和权值
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, 0));

    while (!pq.empty()) {
        int u = pq.top().second; // 当前距离最小的顶点
        pq.pop();

        // 如果顶点已访问过，跳过
        if (visited[u]) {
            continue;
        }

        visited[u] = true; // 标记顶点为已访问
        minCost += dist[u]; // 加入顶点到最小生成树的权值

        // 对于顶点u的所有邻接顶点v
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;

            // 如果顶点v未访问过，并且到顶点v的距离更小
            if (!visited[v] && weight < dist[v]) {
                dist[v] = weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    return minCost;
}

int main() {
    int n, m; // 顶点数和边数
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n);

    // 读取边的信息
    for (int i = 0; i < m; ++i) {
        int u, v, w; // 边的两个顶点及其权值
        cin >> u >> v >> w;
        --u; --v; // 顶点从0开始编号
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w));
    }

    int minCost = prim(graph);
    cout << "最小生成树的权值之和为：" << minCost << endl;

    return 0;
}

Kruskal의 알고리즘은 모서리 기반 그리디 알고리즘입니다. 그래프의 모든 모서리 중에서 가중치가 가장 작은 모서리를 선택하고 해당 모서리가 순환을 형성할지 여부를 결정합니다. 순환이 형성되지 않으면 최소 스패닝 트리에 간선을 추가합니다. 다음은 Kruskal 알고리즘의 C++ 코드 예제입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int u, v, weight; // 边的两个顶点及其权值
    Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {}
};

const int MAXN = 100; // 最大顶点数
int parent[MAXN]; // 并查集数组

bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

int findParent(int x) {
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = findParent(parent[x]);
}

void unionSet(int x, int y) {
    int xParent = findParent(x);
    int yParent = findParent(y);
    if (xParent != yParent) {
        parent[yParent] = xParent;
    }
}

int kruskal(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end(), compare);
    int minCost = 0; // 最小生成树的总权值

    for (int i = 0; i < n; ++i) {
        parent[i] = i; // 初始化并查集数组
    }

    for (auto& edge : edges) {
        int u = edge.u;
        int v = edge.v;
        int weight = edge.weight;

        // 如果顶点u和顶点v不属于同一个连通分量，则将该边加入到最小生成树中
        if (findParent(u) != findParent(v)) {
            unionSet(u, v);
            minCost += weight;
        }
    }

    return minCost;
}

int main() {
    int n, m; // 顶点数和边数
    cin >> n >> m;
    vector<Edge> edges;

    // 读取边的信息
    for (int i = 0; i < m; ++i) {
        int u, v, w; // 边的两个顶点及其权值
        cin >> u >> v >> w;
        edges.push_back(Edge(u, v, w));
    }

    int minCost = kruskal(edges, n);
    cout << "最小生成树的权值之和为：" << minCost << endl;

    return 0;
}

위의 코드 예제를 통해 Prim의 알고리즘과 Kruskal의 알고리즘을 사용하여 C++의 최소 스패닝 트리 문제를 해결할 수 있습니다. 실제 적용에서는 특정 상황에 따라 문제를 해결하기 위해 적절한 알고리즘을 선택할 수 있습니다. 이러한 알고리즘의 시간 복잡도는 각각 O(ElogV) 및 O(ElogE)입니다. 여기서 V는 정점 수이고 E는 가장자리 수입니다. 따라서 대규모 그래프를 처리할 때 더 나은 결과를 얻을 수도 있습니다.

위 내용은 C++에서 최소 신장 트리 알고리즘을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!