DAG/拓扑排序

1. 每两个节点之间都有一端指向另一端的边，这条边有可能有权重。比如上图从A到B要花1块钱。

2. 图中没有环。也就是说不可能从一个节点出发再回到这个节点。

特别是因为第二条图中没有环这个性质，DAG的最值可以通过把节点进行排序来解决。这样的思路类似于动态规划中《最优子结构》的假设，把问题分解为子问题来归纳。我们之后会讲有向图环的检测。

基础：拓扑排序

通过拓扑排序，DAG的节点是有先后次序的。如此遍历就保证不会漏掉我们要找的答案。最简单的例子是二叉树，父节点总是先于儿子节点和孙子节点。如此一来，无论是先序遍历（自顶向下）或者后序遍历（自底向上）都能给我们正确答案。

我们首先来介绍拓扑排序。拓扑排序有两种基本算法：深度优先，广度优先（Khan‘s Algorithm）。

基于深度优先的拓扑排序

def dfs(i):
    vis.add(i)
    for j in graph[i]:
        if j not in vis:
            dfs(j)
    res.append(i) # 后序遍历

vis, res = set(), []
dfs(0)
return res[::-1]

其中深度优先函数dfs相当于进行了后序遍历，所以最后我们把结果反转了一下。最终结果res就是从左到右拓扑排序过的节点。

基于广度优先的拓扑排序

这个算法又叫做Khan's Algorithm，引用了入度的概念。一个节点的入度也就是有几个箭头指着它。这里我们讨论的是无环图，所以一个节点不可能指着自己。

# 计算初始入度
nodes = range(len(graph))
indegrees = {n: 0 for n in nodes}
for i in nodes:
    for j in graph[i]:
        indegrees[j] += 1

# 开始排序，先遍历队列中一直存着入度为0的节
queue = [n for n in n if indegrees[n]==0]
res = []
while queue:
    res.append(queue.pop())
    for j in graph[i]:
        indegrees[j] -= 1
        if indegrees[j]==0:
            queue.append(j)
return res

到此，拓扑排序就完成了。接下来我们可以计算最值且不用担心错过答案了。

DAG的最短或最长路径

假设图中每条路径的花费永远是1（换句话说，我们的总花费=经过节点的个数），那么我们就可以说这个有向无环图是《无权值》的。

无论有否加权，DAG的最短或最长路径都可以用拓扑排序来计算。

讨论：关于图中有否环的存在 - 幸好是有向无环图，我们可以通过拓扑排序来解决这个问题。如果有向图中有环，那么解决方案和是否能够容易地找到答案要分情况讨论。我们把这个讨论留到下一节《无向图的最值》。由于图的边没有指向，一次遍历可以从每一个节点出发再返回到原节点，所以无向图可以考虑成带环有向图的特例。

下面我们用拓扑排序计算DAG最长路径。

nodes = range(len(graph))
dist = {n: float('inf') for n in nodes}
dist[start] = 0

queue = topoSortDFS(graph)
while queue:
    i = queue.pop(0)
    for j, w in graph[i]:
        dist[j] = min(dist[j], w+dist.get(i, 0))
return dist

返回的dist是每个节点到最短路径。

其他情况的处理很简单：

• 如果是无权值的DAG，把graph中权重w设置成1即可。

• 如果求最长路径，把dist初始成最小值，然后比较函数min改为max即可。