leetcode 图相关的题

图

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

• 链表遍历

def dfs(n):
	print(n)
	dfs(n)
1
2
3

• 二叉树遍历

def dfs(n):
	print(n)
	dfs(n.left)
	dfs(n.right)
1
2
3
4

• 矩阵的dfs遍历
  联通岛屿等问题

# 1表示陆地，0表示海水，需要求出联通陆地个数(iland_cnt)
mat=[[...]]
VISITED=2 # 直接修改原始矩阵，防止再次访问
LAND = 1
WATER = 0
iland_cnt = 0
for rr in range(mat.shape[0]):
	for cc in range(mat.shape[1]):
		if mat[rr, cc] == LAND: # 陆地才遍历
			iland_cnt += 1
			dfs(mat, rr, cc)

def dfs(mat, rr, cc):
	h, w = mat.shape[0], mat.shape[1]
	if rr >= h or rr <= 0 or cc <= 0 or cc >= w:
		return
	if mat[rr, cc] != LAND:
		return
  mat[rr, cc] = VISITED
	 dfs(mat, rr-1, cc)
	 dfs(mat, rr+1, cc)
	 dfs(mat, rr, cc-1)
	 dfs(mat, rr, cc+1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 多叉树遍历

dfs(root)
def dfs(n):
	for node in n.nodes:
		dfs(node)
1
2
3
4

• 图遍历

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]:
		return
	visited[idx] = True
	for idx in range(g[idx]):
		dfs(g, idx, visited)

1
2
3
4
5
6
7
8
9
10
11
12

遍历链表(只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 g

    def dfs(g, idx, visited):
        if visited[idx]:
            return
        print(idx)
        visited[idx] = True
        for 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->6
        0 -> 1 -> 2
        3/^   \>  4
        
        5 -> 6
    """
    edges = [
        [0, 1],
        [1, 2],
        [3, 1],
        [1, 4],
        [5, 6]
    ]
    n_nodes = 7
    start_traverse(n_nodes, edges)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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