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

 #include  #include  #include  #include  using namespace std; struct Edge { int u; //边连接的一个顶点编号 int v; //边连接另一个顶点编号 int w; //边的权值 friend bool operator<(const Edge& E1, const Edge& E2) { return E1.w & uset, int n) { uset.assign(n, 0); for (int i = 0; i & uset, int u) { int i = u; while (uset[i] != i) i = uset[i]; return i; } void Kruskal(const vector& edges, int n) { vector uset; vector SpanTree; int Cost = 0, e1, e2; MakeSet(uset, n); for (int i = 0; i > n >> m; vector edges; edges.assign(m, Edge()); for (int i = 0; i > edges[i].u >> edges[i].v >> edges[i].w; sort(edges.begin(), edges.end()); //排序之后，可以以边权值从小到大的顺序选取边 Kruskal(edges, n); in.close(); system("pause"); return 0; }

 #include  #include  #include  #include  #include  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> Adj; priority_queue Q; int FindSet(vector& uset, int v) { int i = v; while (i != uset[i]) i = uset[i]; return i; } void Prim() { int Cost = 0; //用于统计最小生成树的权值之和 vector SpanTree; //用于保存最小生成树的边 vector uset(n,0); //用数组来实现并查集 Edge E(0, 0, 0); for (int i = 0; i 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 > n >> m; Adj.assign(n, list()); for (int i = 0; i > u >> v >> w; Adj[u].push_back(Node(v,w)); Adj[v].push_back(Node(u,w)); } Prim(); in.close(); system("pause"); return 0; }