DFSBFS 在資料結構裡有教,是很基礎的演算法。

Edd Mann 的網誌上看到 Python 的實作,由其中學到 yield from 的用法。下面利用 yield from 的特性,將該網誌中提到的實作改寫成 generator 的型式。同步放在 Gist 上:DFSBFS

DFS

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
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
if start in visited:
return
yield start
visited.add(start)
for vertex in graph[start] - visited:
yield from dfs(graph, vertex, visited=visited)
def dfs_paths(graph, start, goal, path=None):
if path is None:
path = [start]
if start == goal:
yield path
for vertex in graph[start] - set(path):
yield from dfs_paths(graph, vertex, goal, path=path + [vertex])
graph = {
'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E']),
}
print(repr([vertex for vertex in dfs(graph, 'A')]))
print(repr([path for path in dfs_paths(graph, 'A', 'F')]))

BFS

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
def bfs(graph, queue, visited=None):
if visited is None:
visited = set()
if not queue:
return
start = queue.pop(0)
yield start
visited.add(start)
queue += [vertex for vertex in graph[start] - set(queue) - visited]
yield from bfs(graph, queue, visited=visited)
def bfs_paths(graph, queue, goal):
if not queue:
return
(start, path) = queue.pop(0)
if start == goal:
yield path
queue += [(vertex, path + [vertex]) for vertex in graph[start] - set(path)]
yield from bfs_paths(graph, queue, goal)
graph = {
'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E']),
}
print(repr([vertex for vertex in bfs(graph, ['A'])]))
print(repr([path for path in bfs_paths(graph, [('A', ['A'])], 'F')]))