最小生成树prim算法c++

下面是 Prim 算法的 C++ 代码实现（假设图的邻接矩阵为 matrix）：

#include <iostream>
#include <climits>

using namespace std;

const int MAX = 100;

// 找到未被访问的最小权值的顶点
int findMinVertex(bool *visited, int *weights, int n) {
    int minVertex = -1;
    for (int i = 0; i < n; i++) {
        if (!visited[i] && (minVertex == -1 || weights[i] < weights[minVertex])) {
            minVertex = i;
        }
    }
    return minVertex;
}

void prim(int **matrix, int n) {
    bool visited[MAX];
    int weights[MAX];
    int parents[MAX];

    // 初始化所有顶点都没有被访问过
    // 权值被初始化成无限大，因为对于还没有被访问过的顶点来说，我们认为它们之间的距离是无限大
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        weights[i] = INT_MAX;
    }

    // 将第一个顶点的权值初始化为 0，因为第一个顶点是起点
    // 第一个顶点没有任何父节点，因此它的父节点被初始化为 -1
    weights[0] = 0;
    parents[0] = -1;

    for (int i = 0; i < n - 1; i++) {
        // 找到未被访问过的最小权值的顶点
        int minVertex = findMinVertex(visited, weights, n);
        visited[minVertex] = true;

        // 更新所有与该顶点相邻的顶点的权值和父节点
        for (int j = 0; j < n; j++) {
            if (matrix[minVertex][j] != 0 && !visited[j]) {
                if (matrix[minVertex][j] < weights[j]) {
                    weights[j] = matrix[minVertex][j];
                    parents[j] = minVertex;
                }
            }
        }
    }

    // 输出最小生成树的边
    for (int i = 1; i < n; i++) {
        cout << min(i, parents[i]) << " " << max(i, parents[i]) << " " << matrix[i][parents[i]] << endl;
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    int **matrix = new int *[n];
    for (int i = 0; i < n; i++) {
        matrix[i] = new int[n];
        for (int j = 0; j < n; j++) {
            matrix[i][j] = 0;
        }
    }

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        matrix[u][v] = matrix[v][u] = w;
    }

    prim(matrix, n);

    for (int i = 0; i < n; i++) {
        delete[] matrix[i];
    }
    delete[] matrix;

    return 0;
}

这个实现假设图的顶点编号从 0 到 n-1，边的权值都是正数。如果图的顶点编号从 1 到 n，只需要将输出最小生成树的边时将 i 和 parents[i] 加 1 即可。如果图中有负权边，需要使用 Dijkstra 算法或 Bellman-Ford 算法来计算最短路径。