C++语言实现prim算法的代码 |21xrx.com

C++语言实现prim算法的代码

2023-07-13 12:23:54 深夜i -- --

C++ prim算法代码实现

Prim算法是求解最小生成树的经典算法，它的基本思路是从一个起点开始，每次选择与已有集合最近的一个顶点，不断扩大最小生成树的集合。C++语言是一门流行的编程语言，下面就介绍一下使用C++语言实现Prim算法的代码。

1. 数据结构

在实现Prim算法之前，需要定义一些数据结构。这些数据结构通常包括图的节点、边和最小堆等。下面是用C++语言实现的代码示例：

struct Node {

int v, w;

bool operator < (const Node& rhs) const

return w > rhs.w;

};

vector edges[N]; // 存放边

bool visited[N]; // 标记是否已经访问

priority_queue q; // 最小堆

2. Prim算法的实现

接下来，可以编写Prim算法的主要代码。该算法分为三个主要部分：初始化，进行遍历和输出结果。下面是用C++语言实现的代码示例：

void Prim(int start) {

while (!q.empty()) {

q.pop();

}

memset(visited, false, sizeof(visited));

visited[start] = true;

for (int i = 0; i < edges[start].size(); i++) {

q.push(edges[start][i]);

}

int ans = 0;

while (!q.empty()) {

Node node = q.top();

q.pop();

if (visited[node.v])

continue;

visited[node.v] = true;

ans += node.w;

for (int i = 0; i < edges[node.v].size(); i++) {

q.push(edges[node.v][i]);

}

3. 示例代码

完整的Prim算法代码如下所示，其中包括了定义数据结构和实现Prim算法的代码。

#include

using namespace std;

const int N = 1010;

struct Node {

int v, w;

bool operator < (const Node& rhs) const

return w > rhs.w;

};

vector edges[N];

bool visited[N];

priority_queue q;

void Prim(int start) {

while (!q.empty()) {

q.pop();

}

memset(visited, false, sizeof(visited));

visited[start] = true;

for (int i = 0; i < edges[start].size(); i++) {

q.push(edges[start][i]);

}

int ans = 0;

while (!q.empty()) {

Node node = q.top();

q.pop();

if (visited[node.v])

continue;

visited[node.v] = true;

ans += node.w;

for (int i = 0; i < edges[node.v].size(); i++) {

q.push(edges[node.v][i]);

}

cout << ans << endl;

}

int main() {

int n, m;

cin >> n >> m;

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

int u, v, w;

cin >> u >> v >> w;

edges[u].push_back( w);

edges[v].push_back( w);

}

Prim(1);

return 0;

}

4. 总结

C++语言是一门十分强大的编程语言，在实现Prim算法时，合理的数据结构的定义和优秀的算法实现，可以让代码整体的效率得到很好的提升。此外，熟练掌握C++语言的开发者，在实现其他算法时也会变得更加得心应手。

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

下一篇: C++文件读取中文乱码问题解决

评论区

()

相似文章