Directed Acyclic Graphs
Def. An Directed Acyclic Graphs is a directed graph that contains no directed cycles. （有向无环图是一种不包含有向环的有向图。）
Ex. Precedence constraints: edge (vi, vj) means vi must precede vj. （优先约束:edge (vi, vj)意味着vi必须在vj之前）
Def. A topological order of a directed graph G = (V, E) is an ordering of its nodes as v1, v2, …, vn so that for every edge (vi, vj) we have i < j.
（有向图G = (V, E)的拓扑顺序是其节点的顺序为v1, v2，…，vn，使得对于每条边(vi, vj)我们都有i < j）
Precedence Constraints
Precedence constraints. Edge (vi, vj) means task vi must occur before vj. // 优先约束。Edge (vi, vj)表示任务vi必须发生在vj之前。
Applications.
- Course prerequisite graph: course vi must be taken before vj. // 必须在vj之前选修课程vi
- Compilation: module vi must be compiled before vj. // 编译:模块vi必须在vj之前编译
- Pipeline of computing jobs: output of job vi needed to determine input of job vj. // 计算作业流水线:确定作业vj输入需要作业vi的输出
Directed Acyclic Graphs
Lemma. If G has a topological order, then G is a DAG.
Pf. (by contradiction)
- Suppose that G has a topological order v1, ... , vn and that G also has a directed cycle C. Let's see what happens. // 假设G的拓扑序为v1，…， vn ， G也有一个有向循环c，我们看看会发生什么
- Let vi be the lowest-indexed node in C, and let vj be the node just before vi; thus (vj, vi) is an edge. // 设vi是C中索引值最低的节点，vj是vi之前的节点;因此(vj, vi)是一条边。
- By our choice of i, we have i < j. // 根据i的选择，我们有i < j
- On the other hand, since (vj, vi) is an edge and v1, ... , vn is a topological order, we must have j < i, a contradiction. // 另一方面，由于(vj, vi)是一条边，v1，…， vn是拓扑序，我们必须有j < i，矛盾。
Q. Does every DAG have a topological ordering?
Q. If so, how do we compute one?
Lemma. If G is a DAG, then G has a node with no incoming edges.
Pf. (by contradiction)
- Suppose that G is a DAG and every node has at least one incoming edge. Let's see what happens. // 假设G是DAG，且每个节点至少有一条传入边。让我们看看会发生什么
- Pick any node v, and begin following edges backward from v. Since v has at least one incoming edge (u, v) we can walk backward to u. // 选择任意节点v，并开始沿着v向后走，因为v至少有一条传入边(u, v)，我们可以向后走到u。
- Then, since u has at least one incoming edge (x, u), we can walk backward to x. // 然后，由于u至少有一条引入边(x, u)，我们可以往回走到x。
- Repeat until we visit a node, say w, twice. // 重复，直到我们访问一个节点，比如w，两次。
- Let C denote the sequence of nodes encountered between successive visits to w. C is a cycle. // 设C表示连续访问w之间所遇到的节点序列。C是一个循环
Lemma. If G is a DAG, then G has a topological ordering. // 引理。如果G是一个DAG，那么G是拓扑顺序。
Pf. (by induction on n)
- Base case: true if n = 1. // 基本情况:当n = 1时为真
- Given DAG on n > 1 nodes, find a node v with no incoming edges. // 给定DAG上n> 1的节点，找到一个没有传入边的节点v。
- G - { v } is a DAG, since deleting v cannot create cycles. // G - {v}是DAG，因为删除v不能创建循环
- By inductive hypothesis, G - { v } has a topological ordering. // 通过归纳假设，G - {v}具有拓扑有序
- Place v first in topological ordering; then append nodes of G - { v } // 在拓扑排序中把v放在第一位;然后追加G - {v}的节点
- in topological order. This is valid since v has no incoming edges. // 在拓扑秩序。这是有效的，因为v没有进来的边。
Topological Sorting Algorithm: Running Time
Theorem. Algorithm finds a topological order in O(m + n) time. // 算法在O(m + n)时间内找到拓扑顺序
Pf.
- Maintain the following information:
- count [w] = remaining number of incoming edges // count [w] =剩余的进入边数
- S = set of remaining nodes with no incoming edges // S =没有传入边的剩余节点集
- Initialization: O(m + n) via single scan through graph. // 初始化:O(m + n)通过图的单次扫描。
- Update: to delete v // 更新:删除v
- remove v from S // 从S中移除v
- decrement count[w] for all edges from v to w, and add w to S if c count[w] hits 0 // 从v到w的所有边的递减计数[w]，如果c的计数[w]达到0，则将w加到S中
- this is O(1) per edge // 这是每条边O(1）
Topological Ordering Algorithm: Example
