4. 拓扑排序¶

4.1. 拓扑排序¶

假设我们需要调度一系列任务，如课程或施工项目，其中一个任务在其前置任务完成后才能开始。我们希望将任务组织成线性顺序，使得我们可以逐个完成它们而不违反任何前置条件。我们可以使用 DAG 对该问题建模。图是有向的，因为一个任务是另一个任务的前置条件—— 顶点具有有向关系。它是无环的，因为环将表示一系列冲突的前置条件，这些条件在不违反至少一个前置条件的情况下无法完成。将 DAG 的顶点排列成线性顺序以满足前置条件规则的过程称为拓扑排序。

图 16.4.1 说明了问题。此示例的可接受拓扑排序为 J1、J2、J3、J4、J5、J6、J7。但是，其他顺序也是可接受的，例如 J1、J3、J2、J6、J4、J5、J7。

4.1.1. 基于深度优先的解法¶

可以通过对图执行 DFS 来找到拓扑排序。访问顶点时不采取任何操作（即函数 PreVisit 不执行任何操作）。当递归弹回到该顶点时，函数 PostVisit 打印该顶点。这产生反序的拓扑排序。只要所有顶点最终都被访问，排序从哪里开始并不重要。以下是基于 DFS 算法的实现。

Java
Java (Generic)

static void topsortDFS(Graph G) {
  int v;
  for (v=0; v<G.nodeCount(); v++) {
    G.setValue(v, UNVISITED); // Initialize
  }
  for (v=0; v<G.nodeCount(); v++) {
    if (G.getValue(v) != VISITED) {
      tophelp(G, v);
    }
  }
}

static void tophelp(Graph G, int v) {
  G.setValue(v, VISITED);
  int[] nList = G.neighbors(v);
  for (int i=0; i< nList.length; i++) {
    if (G.getValue(nList[i]) != VISITED) {
      tophelp(G, nList[i]);
    }
  }
  printout(v);
}

static void topsortDFS(Graph G) {
  int v;
  for (v=0; v<G.nodeCount(); v++) {
    G.setValue(v, null); // Initialize
  }
  for (v=0; v<G.nodeCount(); v++) {
    if (G.getValue(v) != VISITED) {
      tophelp(G, v);
    }
  }
}

static void tophelp(Graph G, int v) {
  G.setValue(v, VISITED);
  int[] nList = G.neighbors(v);
  for (int i=0; i< nList.length; i++) {
    if (G.getValue(nList[i]) != VISITED) {
      tophelp(G, nList[i]);
    }
  }
  printout(v);
}

使用此算法从 J1 开始并按字母顺序访问相邻邻居，图 16.4.1 中的顶点按 J7、J5、J4、J6、J2、J3、J1 的顺序打印出来。反转此顺序得到拓扑排序 J1、J3、J2、J6、J4、J5、J7。

以下是另一个示例。

Settings

Saving...

Server Error
Resubmit

4.1.2. 基于队列的解法¶

我们可以使用队列代替递归来实现拓扑排序，如下所示。

首先访问所有边，计算指向每个顶点的边数（即计算每个顶点的前置条件数）。所有没有前置条件的顶点被放入队列。然后我们开始处理队列。当顶点 \(v\) 从队列中取出时，打印它，并且 \(v\) 的所有邻居（即所有以 \(v\) 为前置条件的顶点）的计数减一。将计数变为零的任何邻居放入队列。如果队列变空而没有打印所有顶点，则图包含一个环（即没有可能的任务顺序不违反某些前置条件）。将队列版本的拓扑排序应用于图 16.4.1 产生 J1、J2、J3、J6、J4、J5、J7。以下是算法的实现。

以下是基于队列的拓扑排序代码：

Java
Java (Generic)

static void topsortBFS(Graph G) {   // Topological sort: Queue
  Queue Q = new LQueue(G.nodeCount());
  int[] Count = new int[G.nodeCount()];
  int[] nList;
  int v;
  for (v=0; v<G.nodeCount(); v++) { Count[v] = 0; } // Initialize
  for (v=0; v<G.nodeCount(); v++) { // Process every edge
    nList = G.neighbors(v);
    for (int i=0; i< nList.length; i++) {
      Count[nList[i]]++;            // Add to v's prereq count
    }
  }
  for (v=0; v<G.nodeCount(); v++) {   // Initialize Queue
    if (Count[v] == 0) {              // V has no prerequisites
      Q.enqueue(v);
    }
  }
  while (Q.length() > 0) {          // Process the vertices
    v = (Integer)Q.dequeue();
    printout(v);                    // PreVisit for Vertex V
    nList = G.neighbors(v);
    for (int i=0; i< nList.length; i++) {
      Count[nList[i]]--;            // One less prerequisite
      if (Count[nList[i]] == 0) {     // This vertex is now free
        Q.enqueue(nList[i]);
      }
    }
  }
}

static void topsortBFS(Graph G) {   // Topological sort: Queue
  Queue Q = new LQueue(G.nodeCount());
  int[] Count = new int[G.nodeCount()];
  int[] nList;
  int v;
  for (v=0; v<G.nodeCount(); v++) { Count[v] = 0; } // Initialize
  for (v=0; v<G.nodeCount(); v++) { // Process every edge
    nList = G.neighbors(v);
    for (int i=0; i< nList.length; i++) {
      Count[nList[i]]++;            // Add to v's prereq count
    }
  }
  for (v=0; v<G.nodeCount(); v++) {   // Initialize Queue
    if (Count[v] == 0) {              // V has no prerequisites
      Q.enqueue(v);
    }
  }
  while (Q.length() > 0) {          // Process the vertices
    v = (Integer)Q.dequeue();
    printout(v);                    // PreVisit for Vertex V
    nList = G.neighbors(v);
    for (int i=0; i< nList.length; i++) {
      Count[nList[i]]--;            // One less prerequisite
      if (Count[nList[i]] == 0) {     // This vertex is now free
        Q.enqueue(nList[i]);
      }
    }
  }
}