12.4. 拓扑排序¶
12.4.1. 拓扑排序¶
假设我们需要调度一系列任务，如课程或施工项目，其中一个任务在其前置任务完成后才能开始。我们希望将任务组织成线性顺序，使得我们可以逐个完成它们而不违反任何前置条件。我们可以使用 DAG 对该问题建模。图是有向的，因为一个任务是另一个任务的前置条件——顶点具有有向关系。它是无环的，因为环将表示一系列冲突的前置条件，这些条件在不违反至少一个前置条件的情况下无法完成。将 DAG 的顶点排列成线性顺序以满足前置条件规则的过程称为 拓扑排序。
图 12.4.1 说明了问题。此示例的可接受拓扑排序为 J1、J2、J3、J4、J5、J6、J7。但是，其他顺序也是可接受的，例如 J1、J3、J2、J6、J4、J5、J7。
12.4.1.1. 基于深度优先的解法¶
可以通过对图执行 DFS 来找到拓扑排序。访问顶点时不采取任何操作（即函数 PreVisit 不执行任何操作）。当递归弹回到该顶点时，函数 PostVisit 打印该顶点。这产生反序的拓扑排序。只要所有顶点最终都被访问，排序从哪里开始并不重要。以下是基于 DFS 算法的实现。
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 开始并按字母顺序访问相邻邻居，图 12.4.1 中的顶点按 J7、J5、J4、J6、J2、J3、J1 的顺序打印出来。反转此顺序得到拓扑排序 J1、J3、J2、J6、J4、J5、J7。
以下是另一个示例。
12.4.1.2. 基于队列的解法¶
我们可以使用队列代替递归来实现拓扑排序，如下所示。
首先访问所有边，计算指向每个顶点的边数（即计算每个顶点的前置条件数）。所有没有前置条件的顶点被放入队列。然后我们开始处理队列。当顶点 \(v\) 从队列中取出时，打印它，并且 \(v\) 的所有邻居（即所有以 \(v\) 为前置条件的顶点）的计数减一。将计数变为零的任何邻居放入队列。如果队列变空而没有打印所有顶点，则图包含一个环（即没有可能的任务顺序不违反某些前置条件）。将队列版本的拓扑排序应用于图 12.4.1 产生 J1、J2、J3、J6、J4、J5、J7。以下是算法的实现。
以下是基于队列的拓扑排序代码：
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]);
}
}
}
}
确定建议的节点排序是否是图的有效拓扑排序的逆问题可以通过几乎与基于队列的拓扑排序算法相同的算法来解决。首先处理图以生成包含每个节点入度的计数数组。假设建议的排序长度为 \(n\)，按从前到后的顺序遍历建议排序的节点。对于每个节点 \(v\)，检查其计数是否为零。然后将 \(v\) 可到达的每个邻居的计数减一。如果所有节点在按此顺序访问时计数都为零，则这是一个有效的拓扑排序。
