4. 拓扑排序¶
4.1. 拓扑排序¶
假设我们需要调度一系列任务，如课程或施工项目， 其中一个任务在其前置任务完成后才能开始。 我们希望将任务组织成线性顺序， 使得我们可以逐个完成它们而不违反任何前置条件。 我们可以使用 DAG 对该问题建模。 图是有向的，因为一个任务是另一个任务的前置条件—— 顶点具有有向关系。 它是无环的，因为环将表示一系列冲突的前置条件， 这些条件在不违反至少一个前置条件的情况下无法完成。 将 DAG 的顶点排列成线性顺序以满足前置条件规则的过程 称为 拓扑排序。
待处理
- type: Slideshow
将上图替换为包含以下段落的幻灯片。
图 19.4.1 说明了问题。 此示例的可接受拓扑排序为 J1、J2、J3、J4、J5、J6、J7。 但是，其他顺序也是可接受的， 例如 J1、J3、J2、J6、J4、J5、J7。
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);
}
待处理
- type: Slideshow
将以下段落替换为幻灯片。
使用此算法从 J1 开始并按字母顺序访问相邻邻居， 图 19.4.1 中的顶点 按 J7、J5、J4、J6、J2、J3、J1 的顺序打印出来。 反转此顺序得到拓扑排序 J1、J3、J2、J6、J4、J5、J7。
以下是另一个示例。
4.1.2. 基于队列的解法¶
我们可以使用队列代替递归来实现拓扑排序，如下所示。
待处理
- type: Slideshow
将以下内容整合到幻灯片中。
首先访问所有边，计算指向每个顶点的边数 （即计算每个顶点的前置条件数）。 所有没有前置条件的顶点被放入队列。 然后我们开始处理队列。 当顶点 \(v\) 从队列中取出时， 打印它，并且 \(v\) 的所有邻居 （即所有以 \(v\) 为前置条件的顶点） 的计数减一。 将计数变为零的任何邻居放入队列。 如果队列变空而没有打印所有顶点， 则图包含一个环（即没有可能的任务顺序 不违反某些前置条件）。 将队列版本的拓扑排序应用于 图 19.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\) 可到达的每个邻居的计数减一。 如果所有节点在按此顺序访问时计数都为零， 则这是一个有效的拓扑排序。
待处理
- type: Proficiency Exercise
提供一个熟练度练习，随机交替进行基于 DFS 和基于队列的拓扑排序熟练度训练。该练习的初步框架可在
AV/Development/TopSort/topSortDFSPE.*中找到
待处理
- type: AV
提供一个统一的 AV，允许用户选择哪种拓扑排序（DFS 或队列），以及图中是否包含环。此工作的起点位于
AV/Development/TopSort/topSortAV*（仅随机 DFS）、AV/Development/TopSort/qTopSortAV.*（仅随机基于队列的拓扑排序）和AV/Development/TopSort/topSortAVs*（尝试统一）。
待处理
- type: Summary Questions
提供一组总结性问题。
