grtsb.c

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

void topsort(Graph& G) {   // Topological sort: Queue
  Queue Q(G.n());
//  int Count[G.n()];
  int *Count;

  Count = new int [G.n()];

  for (int v=0; v<G.n(); v++) Count[v] = 0; // Initialize
  for (v=0; v<G.n(); v++)  // Process every edge
    for (Edge w = G.first(v); G.isEdge(w); w = G.next(w))
       Count[G.v2(w)]++;   // Add to v2's prereq count
  for (v=0; v<G.n(); v++)  // Initialize Queue
    if (Count[v] == 0)     // Vertex has no prerequisites
      Q.enqueue(v);
  while (!Q.isEmpty()) {   // Process the vertices
    int v = Q.dequeue();
    printout(v);           // PreVisit for Vertex V
    for (Edge w = G.first(v); G.isEdge(w); w = G.next(w)) {
      Count[G.v2(w)]--;    // One less prerequisite
      if (Count[G.v2(w)] == 0) // This vertex is now free
        Q.enqueue(G.v2(w));
    }
  }
}