smallest_tree.rar_最小生成树_最小生成树 C++

//Prim 算法 //注释见书 void Prim(Graph& G, int s) { int *D, *V; D = new int [G.n()]; V = new int [G.n()]; for (int i=0; i<G.n(); i++) D[i] = INFINITY; D[s] = 0; for (i=0; i<G.n(); i++) { int v = minVertex(G, D); G.Mark[v] = VISITED; if (v != s) AddEdgetoMST(V[v], v); if (D[v] == INFINITY) return; for (Edge w = G.first(v); G.isEdge(w); w = G.next(w)) if (D[G.v2(w)] > G.weight(w)) { D[G.v2(w)] = G.weight(w); V[G.v2(w)] = v; } } } int minVertex(Graph& G, int* D) { int v; for (int i=0; i<G.n(); i++) if (G.Mark[i] == UNVISITED) { v = i; break; } for (i=0; i<G.n(); i++) if ((G.Mark[i] == UNVISITED) && (D[i] < D[v])) v = i; return v; }