grprim2.cpp

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

void Prim(Graph& G, int s) {      // Priority queue version
  int v;                          // The current vertex
  int D[G.n()];                   // Distance array
  int V[G.n()];                   // Who's closest
  int* E[G.e()];                  // Heap array with lots of space
  E[0] = &D[s];                   // Initialize heap array
  heap H(E, 1, G.e());            // Create the heap
  for (int i=0; i<G.n(); i++)     // Initialize distance array
    D[i] = INFINITY;
  D[s] = 0;
  for (i=0; i<G.n(); i++) {       // Now build MST
    do { v = H.removemin() - D; } // Get position in D
      while (G.Mark[v] == VISITED);
    G.Mark[v] = VISITED;
    if (v != s) AddEdgetoMST(V[v], v); // Add this edge to MST
    if (D[v] == INFINITY) return; // Remaining vertices unreachable
    for (Edge w = G.first(v); G.isEdge(w); w = G.next(w))
      if (D[G.v2(w)] > G.weight(w)) {  // Update D
        D[G.v2(w)] = G.weight(w);
        V[G.v2(w)] = v;                // Update who it came from
        H.insert(&D[G.v2(w)]);    // Insert new distance in heap
      }
  }
}