图算法之遍历

两种图的遍历算法:广度优先(BFS)与深度优先(DFS)。
广度优先遍历的路径通常短而直接,深度优先遍历的路径通常长而曲折。

广度优先遍历

从起点开始,遍历所有与起点连通的顶点,再遍历与这些顶点连通的顶点,即先搜索距离起点距离为1的顶点,再遍历与起点距离为2的顶点…..

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
def bfsTravel(graph, source):
'''
广度优先遍历
INPUT -> 用邻接表存储的图, 开始遍历的源节点
'''
frontiers = [source] # 表示前驱节点
travel = [source] # 表示遍历过的节点
# 当前驱节点为空时停止遍历
while frontiers:
nexts = [] # 当前层的节点(相比frontier是下一层)
for frontier in frontiers:
for current in graph[frontier]: # 遍历当前层的节点(体现广度)
if current not in travel: # 判断是否访问过
travel.append(current) # 没有访问过则入队
nexts.append(current) # 当前结点作为前驱节点
frontiers = nexts # 更改前驱节点列表
return travel

if __name__ == '__main__':

Graph = {'A': ['B', 'C', 'D'],
'B': ['E'],
'C': ['D', 'F'],
'D': ['B', 'E', 'G'],
'E': [],
'F': ['D', 'G'],
'G': ['E']}

r = bfsTravel(Graph, 'A') # 搜索A到D的所有路径
print(r)

深度优先遍历

从起点开始选择一条边走到下一个顶点,每到一个顶点便标记此顶点已到达,当来到一个标记过的顶点时回退到上一个顶点,再选择一条没有到达过的顶点……直到所有顶点都被访问。

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
def dfsTravel(graph, source):
'''
深度优先遍历
INPUT -> 用邻接表存储的图, 开始遍历的源节点
'''
travel = [] # 存放访问过的节点的列表
stack = [source] # 构造一个堆栈
while stack: # 堆栈空时结束
current = stack.pop() # 堆顶出队
if current not in travel: # 判断当前结点是否被访问过
travel.append(current) # 如果没有访问过,则将其加入访问列表
for next_adj in graph[current]: # 遍历当前结点的下一级
if next_adj not in travel: # 没有访问过的全部入栈
stack.append(next_adj)
return travel

if __name__ == '__main__':

Graph = {'A': ['B', 'C', 'D'],
'B': ['E'],
'C': ['D', 'F'],
'D': ['B', 'E', 'G'],
'E': [],
'F': ['D', 'G'],
'G': ['E']}

r = dfsTravel(Graph, 'A') # 搜索A到D的所有路径
print(r)
0%