grprim1.c

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

void Prim(Graph& G, int s) {           // Prim's MST algorithm
//  int D[G.n()];                        // Distance vertex
//  int V[G.n()];                        // Who's closest
  int *D, *V;
  D = new int [G.n()];
  V = new int [G.n()];
  for (int i=0; i<G.n(); i++)          // Initialize
    D[i] = INFINITY;
  D[s] = 0;
  for (i=0; i<G.n(); i++) {            // Process the vertices
    int v = minVertex(G, D);
    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)) {
        D[G.v2(w)] = G.weight(w);      // Update distance
        V[G.v2(w)] = v;                // Update who it came from
      }
  }
}

int minVertex(Graph& G, int* D) { // Find min cost vertex
  int v;  // Initialize v to any unvisited vertex;
  for (int i=0; i<G.n(); i++)
    if (G.Mark[i] == UNVISITED) { v = i; break; }
  for (i=0; i<G.n(); i++)  // Now find smallest value
    if ((G.Mark[i] == UNVISITED) && (D[i] < D[v])) v = i;
  return v;
}