So verwenden Sie den Minimum Spanning Tree-Algorithmus in C++

So verwenden Sie den Minimum Spanning Tree-Algorithmus in C++

Minimum Spanning Tree (MST) ist ein wichtiges Konzept in der Graphentheorie. Es stellt die Teilmenge der Kanten dar, die alle Eckpunkte eines ungerichteten verbundenen Diagramms verbinden die Gewichte dieser Kanten sind am geringsten. Es gibt viele Algorithmen, die zur Lösung des minimalen Spannbaums verwendet werden können, wie zum Beispiel der Prim-Algorithmus und der Kruskal-Algorithmus. In diesem Artikel wird erläutert, wie C++ zum Implementieren des Prim-Algorithmus und des Kruskal-Algorithmus verwendet wird, und es werden spezifische Codebeispiele gegeben.

Prims Algorithmus ist ein gieriger Algorithmus. Er beginnt an einem Scheitelpunkt des Diagramms, wählt nach und nach die Kante mit dem kleinsten Gewicht aus, die mit dem aktuellen minimalen Spannbaum verbunden ist, und fügt die Kante zum minimalen Spannbaum hinzu. Das Folgende ist ein C++-Codebeispiel des Prim-Algorithmus:

#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;
}

Kruskals Algorithmus ist ein kantenbasierter Greedy-Algorithmus. Er wählt die Kante mit dem kleinsten Gewicht aus allen Kanten des Diagramms aus und bestimmt, ob die Kante einen Zyklus bildet. Wenn kein Zyklus gebildet wird, fügen Sie die Kante zum minimalen Spannbaum hinzu. Das Folgende ist ein C++-Codebeispiel des Kruskal-Algorithmus:

#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;
}

Durch das obige Codebeispiel können wir den Prim-Algorithmus und den Kruskal-Algorithmus verwenden, um das Problem des minimalen Spannbaums in C++ zu lösen. In praktischen Anwendungen kann der geeignete Algorithmus ausgewählt werden, um das Problem entsprechend der spezifischen Situation zu lösen. Die zeitliche Komplexität dieser Algorithmen beträgt O(ElogV) bzw. O(ElogE), wobei V die Anzahl der Eckpunkte und E die Anzahl der Kanten ist. Daher können sie auch bei der Verarbeitung großflächiger Diagramme bessere Ergebnisse erzielen.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Minimum Spanning Tree-Algorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!