最小生成樹c++

最小生成樹（Minimum Spanning Tree, MST）是一種用來找出連通圖中權重總和最小的樹的方法。在C++中，可以使用Prim算法或Kruskal算法來實現最小生成樹。這裡提供一個使用Prim算法的例子：

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

struct Edge {
    int src;
    int dest;
    int weight;
};

class Graph {
public:
    int V;
    vector<vector<int>> edges;

    Graph(int V) {
        this->V = V;
        edges.resize(V);
        for (int i = 0; i < V; i++) {
            edges[i].resize(V);
            for (int j = 0; j < V; j++) {
                edges[i][j] = INT_MAX;
            }
        }
    }

    void addEdge(int src, int dest, int weight) {
        edges[src][dest] = weight;
        edges[dest][src] = weight;
    }

    void primMST() {
        int parent[V];
        for (int i = 0; i < V; i++) {
            parent[i] = -1;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push(make_pair(0, 0));
        parent[0] = -1;

        int totalWeight = 0;
        while (!pq.empty()) {
            int minWeight = -1;
            int u = -1;
            tie(minWeight, u) = pq.top();
            pq.pop();

            if (parent[u] != -1) {
                continue;
            }

            totalWeight += minWeight;
            cout << "(" << u << ", " << parent[u] << ") ";
            for (int i = 0; i < V; i++) {
                if (edges[u][i] != INT_MAX && parent[i] == -1) {
                    parent[i] = u;
                    pq.push(make_pair(edges[u][i], i));
                }
            }
        }
        cout << "\n" << totalWeight << "\n";
    }
};

int main() {
    int V = 5; // 頂點個數
    int E = 6; // 邊個數
    int src = 0; // 起點

    // 圖的建構
    Graph g(V);

    // 邊的資料
    Edge edgesData[] = {
        {0, 1, 10},
        {0, 2, 20},
        {0, 3, 15},
        {1, 2, 12},
        {1, 3, 7},
        {1, 4, 9},
        {2, 3, 14},
        {2, 4, 10},
        {3, 4, 13}
    };

    // 邊的加入
    for (int i = 0; i < E; i++) {
        g.addEdge(edgesData[i].src, edgesData[i].dest, edgesData[i].weight);
    }

    g.primMST();

    return 0;
}

這個程式首先定義了一個Graph類別，用來表示圖和邊的資料。接著定義了一個Edge結構體，用來表示邊的資訊。primMST函數使用了Prim算法來找出最小生成樹，並輸出樹的邊和總權重。

執行這個程式會輸出最小生成樹的邊和總權重，例如：

(0, 1) (1, 2) (2, 3) (3, 4) 
29

這表示最小生成樹的邊為(0, 1), (1, 2), (2, 3), (3, 4)，總權重為29。