DFS Python#
非递归
1from collections import deque
2
3graph = {
4 "v1": ["v2", "v3", "v4"],
5 "v2": ["v1", "v5", "v6"],
6 "v3": ["v1"],
7 "v4": ["v1", "v6"],
8 "v5": ["v2"],
9 "v6": ["v2", "v4"],
10}
11
12visited = []
13stack = deque()
14
15
16def dfs(graph, node):
17
18 stack.append(node)
19 while len(stack) > 0:
20
21 node = stack.pop()
22 if node not in visited:
23 visited.append(node)
24 for neighbor in graph[node]:
25 if neighbor not in visited:
26 stack.append(neighbor)
27
28
29dfs(graph=graph, node="v1")
30print(visited)
递归
1graph = {
2 "v1": ["v2", "v3", "v4"],
3 "v2": ["v1", "v5", "v6"],
4 "v3": ["v1"],
5 "v4": ["v1", "v6"],
6 "v5": ["v2"],
7 "v6": ["v2", "v4"],
8}
9
10visited = []
11
12
13def dfs(visited, graph, node): # function for dfs
14 if node not in visited:
15 visited.append(node)
16 for neighbour in graph[node]:
17 dfs(visited, graph, neighbour)
18
19
20# Driver Code
21print("Following is the Depth-First Search")
22dfs(visited, graph, "v1")
23print(visited)