C++实现最小生成树之普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法

#include <iostream> #include <vector> #include <queue> #include <set> #include <numeric> using namespace std; typedef int Vertex;//顶点 struct Edge{ Vertex v1,v2;//边 int len;//权值 Edge(Vertex v1,Vertex v2,int len):v1(v1),v2(v2),len(len){}//普通构造函数 Edge(const Edge& that):v1(that.v1),v2(that.v2),len(that.len){}//拷贝构造函数 bool operator<(const Edge& other)const//目的是确定比较规则 { return len>other.len; } }; vector<Edge> PrimAlgorithm(vector<vector<int>>& Graph){ int N = Graph.size();//表示节点的数量 priority_queue<Edge> q; set<int> vers; vector<Edge> edges; vers.insert(0); for(int j=1;j<N;j++){ //先把节点0及其边放进去 if(Graph[0][j]==0) continue; q.push(Edge(0,j,Graph[0][j])); } while(vers.size()<6){ Edge e = q.top();q.pop(); if(vers.count(e.v1)==1&&vers.count(e.v2)==1) continue; int i = vers.count(e.v1)==1?e.v2:e.v1; vers.insert(i); edges.push_back(e); for(int j=0;j<N;j++){ if(vers.count(j)==1) continue;//j节点已经在里边了 if(Graph[i][j]==0) continue;//不连通 q.push(Edge(i,j,Graph[i][j])); } } return edges; } int findties(vector<int>& ties,int child){ //找老祖,并查集的小函数 while(ties[child]!=child) child = ties[child]; return child; } vector<Edge> Kruskal(vector<vector<int>>& Graph){ int N = Graph.size();//表示节点的数量 priority_queue<Edge> q; vector<Edge> edges; for(int i=0;i<N;i++){ for(int j=i+1;j<N;j++){ //对所有边排序 if(Graph[i][j]==0) continue; q.push(Edge(i,j,Graph[i][j])); } } vector<int> ties(N,0);//血缘关系 iota(ties.begin(), ties.end(), 0);//一开始只有自己和自己有血缘关系,这两行代码的目的是对节点采用并查集算法 while(edges.size()<N-1){ Edge e = q.top();q.pop(); if(findties(ties,e.v1)==findties(ties,e.v2)) continue;//说明在同一个集合中 ties[findties(ties,e.v1)] = findties(ties,e.v2);//随便认爹，谁当爹都行 edges.push_back(e); } return edges; } vector<vector<int>> edgesToGraph(vector<Edge>& edges){ int N = edges.size()+1; vector<vector<int>> Graph(N,vector(N,0)); for(auto&e:edges){ Graph[e.v1][e.v2] = e.len; Graph[e.v2][e.v1] = e.len; } return Graph; } void printEdges(const vector<Edge>& edges){ for(auto&e:edges){ cout<<e.v1<<","<<e.len<<","<<e.v2<<endl; } } void printGraph(const vector<vector<int>>& Graph){ int N = Graph.size(); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ cout<<Graph[i][j]<<" "; } cout<<endl; } } int main() { //普利姆算法和克鲁斯卡尔算法是图构建最小生成树的两个经典算法 //初始图以邻接矩阵方式给出,不相连记作0 vector<vector<int>> Graph = { { 0,100,400, 0,200,250}, {100, 0,400, 0, 0,300}, {400,400, 0,300, 0,400}, { 0, 0,300, 0, 0,200}, {200, 0, 0, 0, 0,400}, {250,300,400,200,400, 0} };//Graph[i][j]代表i和j构成的边的权值 int N = Graph.size(); vector<Edge> edges = PrimAlgorithm(Graph); //vector<Edge> edges= Kruskal(Graph); printEdges(edges); vector<vector<int>> ret = edgesToGraph(edges); printGraph(ret); return 0; }