C++使用Kruskal和Prim算法实现最小生成树分享！

很久以前就学过最小生成树之Kruskal和Prim算法，这两个算法很容易理解，但实现起来并不那么容易。最近学习了并查集算法，得知并查集可以用于实现上述两个算法后，我自己动手实现了最小生成树算法。

宏观上讲，Kruskal算法就是一个合并的过程，而Prim算法是一个吞并的过程，另外在Prim算法中还用到了一种数据结构——优先级队列，用于动态排序。由于这两个算法很容易理解，在此不再赘述。接下来给出我的源代码。

输入

第一行包含两个整数n和m，n表示图中结点个数，m表示图中边的条数；接下来m行，每一行包含三个整数u,v,w，表示途中存在一条边(u,v)，并且其权重为w；为了便于调试，我的程序是从文件中输入数据的；

输出

输出程序选择的最小生成树的权值之和以及每一条边信息；

Kruskal算法：

  #include <iostream>  #include <vector>  #include <algorithm>  #include <fstream>  using namespace std;     struct Edge  {   int u; //边连接的一个顶点编号   int v; //边连接另一个顶点编号   int w; //边的权值   friend bool operator<(const Edge& E1, const Edge& E2)   {   return E1.w < E2.w;   }  };  //创建并查集  void MakeSet(vector<int>& uset, int n)  {   uset.assign(n, 0);   for (int i = 0; i < n; i++)   uset[i] = i;  }  //查找当前元素所在集合的代表元  int FindSet(vector<int>& uset, int u)  {   int i = u;   while (uset[i] != i) i = uset[i];   return i;  }  void Kruskal(const vector<Edge>& edges, int n)  {   vector<int> uset;   vector<Edge> SpanTree;   int Cost = 0, e1, e2;   MakeSet(uset, n);   for (int i = 0; i < edges.size(); i++) //按权值从小到大的顺序取边   {   e1 = FindSet(uset, edges[i].u);   e2 = FindSet(uset, edges[i].v);   if (e1 != e2) //若当前边连接的两个结点在不同集合中，选取该边并合并这两个集合   {   SpanTree.push_back(edges[i]);   Cost += edges[i].w;   uset[e1] = e2; //合并当前边连接的两个顶点所在集合   }   }   cout << "Result:n";   cout << "Cost: " << Cost << endl;   cout << "Edges:n";   for (int j = 0; j < SpanTree.size(); j++)   cout << SpanTree[j].u << " " << SpanTree[j].v << " " << SpanTree[j].w << endl;   cout << endl;  }  int main()  {   ifstream in("data.txt");      int n, m;   in >> n >> m;   vector<Edge> edges;   edges.assign(m, Edge());   for (int i = 0; i < m; i++)   in >> edges[i].u >> edges[i].v >> edges[i].w;   sort(edges.begin(), edges.end()); //排序之后，可以以边权值从小到大的顺序选取边   Kruskal(edges, n);      in.close();      system("pause");   return 0;  }

Prim算法：

  #include <iostream>  #include <fstream>  #include <vector>  #include <list>  #include <queue>  using namespace std;  struct Node  {   int v;   int w;   Node(int a, int b) :v(a), w(b){}  };  struct Edge  {   int u;   int v;   int w;   Edge(int a, int b, int c) :u(a), v(b), w(c){}   friend bool operator<(const Edge& E1, const Edge& E2)   {   return E1.w>E2.w;   }  };  int n, m;  vector<list<Node>> Adj;  priority_queue<Edge> Q;     int FindSet(vector<int>& uset, int v)  {   int i = v;   while (i != uset[i]) i = uset[i];   return i;  }     void Prim()  {   int Cost = 0; //用于统计最小生成树的权值之和   vector<Edge> SpanTree; //用于保存最小生成树的边   vector<int> uset(n,0); //用数组来实现并查集   Edge E(0, 0, 0);   for (int i = 0; i < n; i++) uset[i] = i; //并查集初始化   for (auto it = Adj[0].begin(); it != Adj[0].end(); it++)    Q.push(Edge(0, it->v, it->w)); //根据Prim算法，开始时选取结点0，并将结点0与剩余部分的边保存在优先队列中   //循环中每次选取优先队列中权值最小的边，并更新优先队列   while (!Q.empty())   {   E = Q.top();   Q.pop();   if (0 != FindSet(uset, E.v))   {   Cost += E.w;   SpanTree.push_back(E);   uset[E.v] = E.u;   for (auto it = Adj[E.v].begin(); it != Adj[E.v].end(); it++)   if (0 != FindSet(uset, it->v)) Q.push(Edge(E.v, it->v, it->w));   }   }   cout << "Result:n";   cout << "Cost: " << Cost << endl;   cout << "Edges:n";   for (int j = 0; j < SpanTree.size(); j++)   cout << SpanTree[j].u << " " << SpanTree[j].v << " " << SpanTree[j].w << endl;   cout << endl;  }  int main()  {   ifstream in("data.txt");      int u, v, w;   in >> n >> m;   Adj.assign(n, list<Node>());   for (int i = 0; i < m; i++)   {   in >> u >> v >> w;   Adj[u].push_back(Node(v,w));   Adj[v].push_back(Node(u,w));   }   Prim();      in.close();      system("pause");   return 0;  }

就实现而言，Kruskal算法比Prim算法更容易，代码更易于理解。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持<计算机技术网(www.ctvol.com)!!>。

—-想了解C++使用Kruskal和Prim算法实现最小生成树分享！全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>