C++实现根据图的顶点、边和权值输入，输出最小生成树 |21xrx.com

C++实现根据图的顶点、边和权值输入，输出最小生成树

2023-07-05 15:10:20 深夜i -- --

C++ 图顶点边权值最小生成树

最小生成树是一种常见的图论算法，是求解无向图最小生成树的问题。它的应用广泛，比如网络设计、路由问题等。在C++中，我们可以使用Kruskal算法或Prim算法来实现最小生成树的求解。

Kruskal算法的基本思想是先把所有边按权值从小到大排序，然后从小到大选择边，如果选择的边不与已选的边构成环，则将它加入最小生成树中，否则，放弃此边。使用并查集来维护连通性，判断边加入是否会导致环的出现。

具体实现过程如下：

1.对图的边按权值从小到大排序；

2.初始化并查集；

3.遍历边集合，如果边的两个端点不在同一个连通块中，则将它们合并，并把此边加入最小生成树中；

4.重复步骤3，直到最小生成树中有n-1条边，n为图中的顶点数。

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

#include

using namespace std;

struct Edge{

int u, v, w;

Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){}

bool operator < (const Edge& e)const

return w < e.w;

};

int find(int x, vector & parent){

if(parent[x] == x)

return x;

return parent[x] = find(parent[x], parent);

}

void unite(int x, int y, vector & parent){

x = find(x, parent);

y = find(y, parent);

parent[x] = y;

}

int kruskal(vector & edges, int n){

sort(edges.begin(), edges.end());

vector parent(n);

for(int i=0; i

parent[i] = i;

int cnt = 0, ans = 0;

for(auto e: edges){

if(cnt == n - 1)

break;

if(find(e.u, parent) != find(e.v, parent)){

unite(e.u, e.v, parent);

cnt++;

ans += e.w;

}

return ans;

}

int main(){

int n, m;

cin >> n >> m; //n为顶点数，m为边数

vector edges;

for(int i=0; i

int u, v, w;

cin >> u >> v >> w;

edges.push_back(Edge(u-1, v-1, w)); //输入顶点、边和权值，编号从1开始，需要减1

}

int ans = kruskal(edges, n);

cout << ans << endl; //输出最小生成树的边权和

return 0;

}

另外，Prim算法的实现也比较简单。其思想是从一个起点开始，每次找到与当前树最近的一个点加入树中，直到所有的点都被加入。具体实现过程如下：

1.从一个起点开始，将其加入树中；

2.重复以下步骤n-1次，其中n为图的顶点数：

1）找到与树最近的一个点；

2）将这个点加入树中；

3）更新树到其他点的最短距离。

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

#include

using namespace std;

struct Edge{

int to, w;

Edge(int _to, int _w): to(_to), w(_w){}

bool operator > (const Edge& e)const

return w > e.w;

};

int prim(vector >& adj, int n){

int ans = 0;

priority_queue , greater > pq; //小根堆

vector dist(n, INT_MAX); //到各点最近距离

vector vis(n);

dist[0] = 0;

pq.push(Edge(0, 0));

while(!pq.empty()){

Edge e = pq.top();

pq.pop();

if(vis[e.to]) continue;

vis[e.to] = true;

ans += e.w;

for(auto ne: adj[e.to]){

if(!vis[ne.to] && ne.w < dist[ne.to]){

dist[ne.to] = ne.w;

pq.push(Edge(ne.to, dist[ne.to]));

}

return ans;

}

int main(){

int n, m;

cin >> n >> m; //n为顶点数，m为边数

vector > adj(n);

for(int i=0; i

int u, v, w;

cin >> u >> v >> w;

adj[u-1].push_back(Edge(v-1, w));

adj[v-1].push_back(Edge(u-1, w));

}

int ans = prim(adj, n);

cout << ans << endl; //输出最小生成树的边权和

return 0;

}

综上，C++通过Kruskal算法或Prim算法，可以实现根据图的顶点、边和权值输入，输出最小生成树。这些算法在实际应用中具有重要的意义，可以为网络设计、路由问题等提供有效的解决方案。

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

下一篇: C++中vector的push_back用法

评论区

()

相似文章