leetcode 图相关的题

图

图相关知识有leetcode207课程表1(有环判断)以及210 课程表2(拓扑排序).

• 链表遍历

def dfs(n):print(n)dfs(n)

• 二叉树遍历

def dfs(n):print(n)dfs(n.left)dfs(n.right)

• 多叉树遍历

dfs(root)
def dfs(n):for node in n.nodes:dfs(node)

• 图遍历

visited = [False] * n_nodes
g = build_graph() # list[list[]]
for idx in range(node_num):dfs(g, idx, visited)def dfs(g, idx, visited):if visited[idx]:returnvisited[idx] = Truefor idx in range(g[idx]):dfs(g, idx, visited)

遍历链表(只dfs(node))->遍历二叉树(dfs(node.left), dfs(node.right)-> 遍历多叉树 for(n:nodes) dfs(n) ->遍历图:for(n:nodes) visited[n]=True,dfs(n)

• 图遍历完整示例

def traverse_graph():def build_graph(num_nodes, edges):g = []for _ in range(num_nodes):g.append([])for e in edges:FROM = e[0]TO = e[1]g[FROM].append(TO)return gdef dfs(g, idx, visited):if visited[idx]:returnprint(idx)visited[idx] = Truefor s in g[idx]:dfs(g, s, visited)def start_traverse(num_nodes: int, edges: List[List[int]]):g = build_graph(num_nodes, edges)visited = num_nodes * [False]for s in range(num_nodes):dfs(g, s, visited)"""0, 1为图的入口,2, 4为出口, 另外有个独立的图 5->60 -> 1 -> 23/^   \>  45 -> 6"""edges = [[0, 1],[1, 2],[3, 1],[1, 4],[5, 6]]n_nodes = 7start_traverse(n_nodes, edges)

参考:
https://mp.weixin.qq.com/s/7nP92FhCTpTKIAplj_xWpA?forceh5=1