grkrusk.cpp

来自「经典c++程序的实现」· C++ 代码 · 共 21 行

Kruskel(Graph& G) { // Kruskal's MST algorithm
  Gentree A(G.n()); // Equivalence class array
  Edge E[G.e()];    // Array of edges for min-heap
  int edgecnt = 0;
  for (int i=0; i<G.n(); i++)  // Put the edges on the array
    for (Edge w = G.first(i); G.isEdge(w); w = G.next(w))
      E[edgecnt++] = w;
  heap H(E, edgecnt, edgecnt); // Heapify the edges
  int numMST = G.n();          // Initially n equiv classes
  for (i=0; numMST>1; i++) {   // Combine equiv classes
    Edge w = H.removemin();    // Get next cheapest edge
    int v = G.v1(w);
    int u = G.v2(w);
    if (A.differ(v, u)) {      // If in different equiv classes
      A.UNION(v, u);           // Combine equiv classes
      AddEdgetoMST(G.v1(w), G.v2(w));  // Add this edge to MST
      numMST--;                // One less MST
    }
  }
}