Skip to content

困难题:拓扑顺序+图构建

剑指 Offer II 114. 外星文字典

构建图需要使用dict.setdefault(key,value)

对于图来说,如何求解出拓扑顺序呢?

  1. 广度优先搜索
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
  1. 深度优先搜索(后序遍历+栈)

用深度优先搜索来探索至最深处,然后返回时记录。