日日操夜夜添-日日操影院-日日草夜夜操-日日干干-精品一区二区三区波多野结衣-精品一区二区三区高清免费不卡

如何使用C++中的最小生成樹算法

最小生成樹（Minimum Spanning Tree，MST）是圖論中一個重要的概念，它表示連接一個無向連通圖的所有頂點的邊的子集，且這些邊的權(quán)值之和最小。有多種算法可以用來求解最小生成樹，如Prim算法和Kruskal算法。本文將介紹如何使用C++實現(xiàn)Prim算法和Kruskal算法，并給出具體的代碼示例。

Prim算法是一種貪心算法，它從圖的一個頂點開始，逐步選擇與當(dāng)前最小生成樹連接的權(quán)值最小的邊，并將該邊加入到最小生成樹中。以下是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(); // 圖的頂點數(shù)
    vector<bool> visited(n, false); // 標(biāo)記頂點是否已訪問
    vector<int> dist(n, INF); // 記錄頂點到最小生成樹的最短距離
    int minCost = 0; // 最小生成樹的總權(quán)值

    // 從第一個頂點開始構(gòu)建最小生成樹
    dist[0] = 0;

    // 使用優(yōu)先隊列保存當(dāng)前距離最小的頂點和權(quán)值
    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; // 當(dāng)前距離最小的頂點
        pq.pop();

        // 如果頂點已訪問過，跳過
        if (visited[u]) {
            continue;
        }

        visited[u] = true; // 標(biāo)記頂點為已訪問
        minCost += dist[u]; // 加入頂點到最小生成樹的權(quán)值

        // 對于頂點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; // 頂點數(shù)和邊數(shù)
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n);

    // 讀取邊的信息
    for (int i = 0; i < m; ++i) {
        int u, v, w; // 邊的兩個頂點及其權(quán)值
        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 << "最小生成樹的權(quán)值之和為：" << minCost << endl;

    return 0;
}

登錄后復(fù)制

Kruskal算法是一種基于邊的貪心算法，它從圖的所有邊中選擇權(quán)值最小的邊，并判斷該邊是否會形成環(huán)路。如果不會形成環(huán)路，則將該邊加入到最小生成樹中。以下是Kruskal算法的C++代碼示例：

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

struct Edge {
    int u, v, weight; // 邊的兩個頂點及其權(quán)值
    Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {}
};

const int MAXN = 100; // 最大頂點數(shù)
int parent[MAXN]; // 并查集數(shù)組

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; // 最小生成樹的總權(quán)值

    for (int i = 0; i < n; ++i) {
        parent[i] = i; // 初始化并查集數(shù)組
    }

    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; // 頂點數(shù)和邊數(shù)
    cin >> n >> m;
    vector<Edge> edges;

    // 讀取邊的信息
    for (int i = 0; i < m; ++i) {
        int u, v, w; // 邊的兩個頂點及其權(quán)值
        cin >> u >> v >> w;
        edges.push_back(Edge(u, v, w));
    }

    int minCost = kruskal(edges, n);
    cout << "最小生成樹的權(quán)值之和為：" << minCost << endl;

    return 0;
}

登錄后復(fù)制

通過以上代碼示例，我們可以在C++中使用Prim算法和Kruskal算法求解最小生成樹的問題。在實際應(yīng)用中，可以根據(jù)具體情況選擇合適的算法來解決問題。這些算法的時間復(fù)雜度分別為O(ElogV)和O(ElogE)，其中V為頂點數(shù)，E為邊數(shù)。因此，它們在處理大規(guī)模圖的情況下也能夠得到較好的效果。

以上就是如何使用C++中的最小生成樹算法的詳細(xì)內(nèi)容，更多請關(guān)注www.xfxf.net其它相關(guān)文章！