Prim算法C++代码 |21xrx.com

Prim算法C++代码

2023-07-14 03:24:54 深夜i -- --

Prim算法 C++ 代码

Prim算法是一种求解最小生成树的常用算法，这篇文章将介绍Prim算法的C++代码实现。

Prim算法的思想是从一个顶点出发，依次选择离该顶点最近的边，然后将该边的另一个端点加入到生成树中。具体实现时，需要使用一个数组来记录每个顶点的最小键值，以及一个标记数组来标记每个顶点是否已经被访问过。

首先，我们需要定义一个邻接矩阵来表示图。假设有n个顶点，邻接矩阵G[i][j]表示顶点i与j之间的边的权值。

接下来，我们可以使用一个vector来存储已经访问过的顶点。初始时，我们将第一个顶点加入到访问列表中，并将该顶点的最小键值设为0。

然后，我们可以通过一个循环来依次访问所有顶点。在循环的每一次迭代中，我们需要找到未访问过的顶点中，与访问列表中的顶点距离最短的节点，并将该节点加入到访问列表中。同时，更新其它未访问节点的最小键值。

最后，可以通过访问列表中的节点，构建最小生成树。

下面是Prim算法的C++代码实现：

#include

using namespace std;

const int MAX_N = 100;

int G[MAX_N][MAX_N];

int n;

int dist[MAX_N];

bool visited[MAX_N];

int prim() {

for(int i = 0; i < n; i++) {

dist[i] = INT_MAX;

visited[i] = false;

}

dist[0] = 0;

visited[0] = true;

int ans = 0;

for(int i = 0; i < n; i++) {

int min_dist = INT_MAX;

int min_index = -1;

for(int j = 0; j < n; j++) {

if(!visited[j] && dist[j] < min_dist) {

min_dist = dist[j];

min_index = j;

}

if(min_index == -1) break;

visited[min_index] = true;

ans += min_dist;

for(int j = 0; j < n; j++) {

if(!visited[j] && G[min_index][j] < dist[j]) {

dist[j] = G[min_index][j];

}

return ans;

}

int main() {

cin >> n;

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {

cin >> G[i][j];

}

int ans = prim();

cout << "最小生成树权值为：" << ans << endl;

return 0;

}

在上述代码中，我们使用常量MAX_N来表示邻接矩阵的大小，使用INT_MAX宏来表示最大的int类型值。在主函数中，我们从标准输入中读取邻接矩阵，并使用prim函数计算最小生成树的权值。最后，我们输出计算结果。

总之，Prim算法是一种求解最小生成树的有效算法。通过以上的C++代码实现，读者可以了解该算法的基本思想及实现方法。

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

下一篇: C++输入十二进制数1a

评论区

()

相似文章