C++最小生成树Prim算法详解 |21xrx.com

2023-07-05 18:43:21 深夜i -- --

C++ 最小生成树 Prim算法详解算法实现

Prim算法是解决最小生成树问题的一种算法。最小生成树是一个无向连通图中边权值和最小的生成树。

Prim算法的基本思想是：从一个点开始，不断向外部扩展点，直到扩展完所有的点为止。在扩展点的过程中，选择边权最小的那一条边，实现对树的扩展。

具体实现过程：

首先，从图中任意选择一个点作为起点，把这个点加入到最小生成树中。

然后，找出与这个点相邻、未加入最小生成树中的点中，边权最小的这个点，将其加入最小生成树中。

接着，以加入的这个点为基础，再找出与其相邻、未加入最小生成树中的点中边权最小的点，将其加入最小生成树中。

持续重复上述步骤，直到将所有点都加入最小生成树。这样就得到了最小生成树。

下面我们通过C++代码来进一步展示Prim算法的具体实现：

int prim(int start) {

int result = 0;

bool visited[MAX_VERTEX_NUM] = { 0 };

priority_queue , greater > que;

visited[start] = true;

for (int i = 0; i < graph.vertexNum - 1; ++i) {

for (int j = graph.firstNeighbor(start); j != -1; j = graph.nextNeighbor(start, j)) {

if (!visited[graph.edge[j].to]) {

que.push(graph.edge[j]);

}

while (visited[que.top().to]) {

que.pop();

}

Edge tmp = que.top();

que.pop();

visited[tmp.to] = true;

result += tmp.val;

start = tmp.to;

}

return result;

}

在这段代码中，我们首先初始化visited数组和优先队列que。visited数组用于记录已经加入最小生成树中的点，que代表当前还未加入最小生成树的边。

我们通过for循环，对于每个点，将与其相邻的未加入最小生成树的点加入优先队列中。

然后，我们通过while循环和top()方法，找出当前优先队列中的边权值最小的边。如果这条边连接的点已经在最小生成树中，则弹出这条边；否则将这条边加入最小生成树中。

最后，我们将所以加入最小生成树中的边的边权和返回结果。

综上所述，Prim算法是解决最小生成树问题的一种有效算法。通过对Prim算法的详解，我们可以了解到其基本思路和具体实现方法。

上一篇: idea打包java可执行jar包

下一篇: 江苏师范大学C++期末考试题及答案

()

相似文章