c++邻接矩阵prim算法

邻接矩阵Prim算法是一种用于解决最小生成树问题的算法，它基于贪心策略，每次选择当前最小的边来扩展生成树。下面是C++实现邻接矩阵Prim算法的基本步骤：

1. 定义一个邻接矩阵来表示图，其中矩阵中的元素表示两个顶点之间的边的权重。

2. 定义一个数组来记录每个顶点是否已经被访问过，初始值为false。

3. 定义一个数组来记录每个顶点到生成树的最小距离，初始值为无穷大。

4. 选择一个起始顶点，将其标记为已访问，并将其到生成树的最小距离设为0。

5. 对于起始顶点的所有邻居，更新它们到生成树的最小距离。

6. 从未访问过的顶点中选择一个到生成树距离最小的顶点，将其标记为已访问，并将其到生成树的最小距离设为0。

7. 重复步骤5和6，直到所有顶点都被访问过。

8. 最终生成的树即为最小生成树。

相关问题

用邻接矩阵表示无向带权图prim c++

无向带权图可以用邻接矩阵来表示，而Prim算法是一种用来寻找最小生成树的算法。首先，我们需要构建一个二维数组作为邻接矩阵来表示图的边的权重。假设该无向带权图有n个顶点，我们可以构建一个n*n的矩阵来表示图中顶点之间的边的权重。

接着，我们可以利用Prim算法来找出该图的最小生成树。具体做法是从任意一个顶点开始，将其加入到最小生成树中，并标记为已访问。然后依次找出与已访问的顶点相连且权重最小的边所连接的顶点，将其加入到最小生成树中，并标记为已访问。

重复上述步骤直到所有的顶点都被访问过，即可得到该图的最小生成树。最小生成树的邻接矩阵就是Prim算法中每一步都选取的顶点与其连接的边所构成的矩阵。

总的来说，用邻接矩阵表示无向带权图prim c 就是利用二维数组来表示图的边的权重，然后利用Prim算法来寻找最小生成树，最后得到最小生成树的邻接矩阵来表示整个图的结构。

c++实现用邻接矩阵存储的图的最小生成树Prim算法

Prim算法是求解最小生成树问题的一种贪心算法，可以使用邻接矩阵来存储图。具体实现步骤如下：

1. 初始化：选择一个起点，将其加入到最小生成树中，将其与其它节点的距离（边权）存入一个数组dist中，将其它节点的前驱节点存入一个数组pre中，将起点的前驱节点设为-1，表示当前点为起点。

2. 重复以下步骤，直到所有节点都被加入到最小生成树中：

a. 找到距离最小的未加入节点v，将其加入到最小生成树中。

b. 更新dist和pre数组，将v与其它未加入节点u之间的距离（边权）与dist[u]比较，若小于dist[u]，则更新dist[u]和pre[u]。

最终得到的pre数组就是最小生成树的构建过程，代码实现如下：

#include <stdio.h>
#include <limits.h>

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵表示的图
int dist[MAX_VERTICES]; // 存储节点到最小生成树的距离
int pre[MAX_VERTICES]; // 存储节点的前驱节点
int visited[MAX_VERTICES]; // 标记节点是否已加入到最小生成树中

int prim(int n) // n为节点数
{
    int i, j;
    int min_dist, u, v;
    int total_weight = 0;

    for (i = 0; i < n; i++) {
        dist[i] = INT_MAX;
        pre[i] = -1;
        visited[i] = 0;
    }

    dist[0] = 0;

    for (i = 0; i < n; i++) {
        min_dist = INT_MAX;
        for (j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }
        visited[u] = 1;
        total_weight += min_dist;
        for (v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] < dist[v]) {
                dist[v] = graph[u][v];
                pre[v] = u;
            }
        }
    }

    return total_weight;
}

int main()
{
    int n, m;
    int i, j, u, v, w;

    scanf("%d%d", &n, &m);

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            graph[i][j] = INT_MAX;
        }
    }

    for (i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w); // 输入边的起点、终点、边权
        graph[u][v] = graph[v][u] = w; // 无向图，所以要将两个方向的边都存储
    }

    printf("Total weight of minimum spanning tree: %d\n", prim(n));

    return 0;
}