困难题:拓扑顺序+图构建
构建图需要使用dict.setdefault(key,value)
对于图来说,如何求解出拓扑顺序呢?
- 广度优先搜索
starts#找到所有入度为0的节点
q = starts
index = 0
while index<len(q):
node = q[index]
for v in g[node]:
inDeg[v] -= 1
if inDeg[v] == 0:
q.append(v)
index += 1
- 深度优先搜索(后序遍历+栈)
用深度优先搜索来探索至最深处,然后返回时记录。