BFS（广度优先搜索）：

图1 BFS
图2 BFS
图3 Queue of BFS
图一是BFS（广度优先搜索）在树的情况下的执行过程，从A出发，搜索A的第二层，发现有B，C，D（必须从左到右搜索），再搜索B的第二层，发现B的第二层没有元素，再搜索C的第二层，发现有E，F，放置于D后面，再搜索D的第二层，发现有G，放置于F后面，再往下搜索E，F，G，发现只有G有第二层H和I，所以最后得到：
A B C D E F G H I
图二是BFS（广度优先搜索）在图的情况下的执行过程，假设从A出发，第二层是B和C，先搜索B的第二层，发现有D，再搜索C的第二层，发现只有E了，最后D，E中只有D有第二层F，所以最后得到：
A B C D E F
⚠️：这里不可以是：A B C E D F，因为必须先搜索B的第二层再搜索C的第二层
同理以E为起始点可以得到：E C D A B F（不同的起始点的路径不同）
BFS在python中实现运用了Queue（队列）将搜索结果进行排列

DFS（深度优先搜索）：

图4 DFS
图5 stack of DFS
图4是DFS（深度优先搜索）在图的情况下的执行过程，其规则是从起始点往下走，走到底再返回，直到走完所有点：
从起始点A出发->B->C->D->F(此时到底了，返回)->E->C(此时所有点都走完了)
DFS在python中实现运用了Stack（栈）将搜索结果进行堆砌：
将起始点A先放入栈->拿出A，A后可以选择走B和C->将B，C放入栈->拿出B，B之后只能走D->将D放入栈->拿出D，D之后可以走E，F->将E，F放入栈->拿出F，F之后到底了->无放入->拿出E->拿出C
最后得到 A B D F E C （不同的起始点的路径不同）

完整python代码解析
从‘A’出发:
BFS得到A B C D E F (答案不唯一)
DFS得到A B D F E C (答案不唯一）

用字典的映射去表示图2
>>> graph = {
... 'A': ['B', 'C'],
... 'B': ['A', 'C', 'D'],
... 'C': ['A', 'B', 'D', 'E'],
... 'D': ['B', 'C', 'E', 'F'],
... 'E': ['C', 'D'],
... 'F': ['D']
... }
>>> graph.keys()-------返回图上所有节点的名称，顺序不固定
dict_keys(['A', 'B', 'C', 'D', 'E', 'F'])
>>> graph['E']------看看E的连接点
['C', 'D']
1
2
3
4
5
6
7
8
9
10
11
12
13
数组可以动态加东西，用append()，动态删东西用pop()
>>> queue = []
>>> queue.append('A')---在列表末端添加元素
>>> queue.append('B')
>>> queue.append('C')
>>> queue
['A', 'B', 'C']
>>> queue.pop(0)---删除第一个元素并返回
'A'
>>> queue
['B', 'C']
>>> queue.pop()----删除最后一个元素并返回
'C'
>>> queue
['B']
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
graph = {
'A': ['B', 'C'],
'B': ['A', 'C', 'D'],
'C': ['A', 'B', 'D', 'E'],
'D': ['B', 'C', 'E', 'F'],
'E': ['C', 'D'],
'F': ['D']
}
# input一个graph和起始点s
def BFS(graph, s):
#创建队列
queue = []
#将起始点s放入队列，假设起始点为‘A’
queue.append(s)
#set():创建一个无序不重复元素集，可进行关系测试，删除重 复数据,还可以计算交集、差集、并集
seen = set()
#'A'我们已经见过，放入seen
seen.add(s)
#当队列不是空的时候
while len(queue) > 0:
#将队列的第一个元素读出来，即‘A’
vertex = queue.pop(0)
#graph['A']就是A的相邻点：['B','C'],将其储存到nodes
nodes = graph[vertex]
#遍历nodes中的元素，即['B','C']
for w in nodes:
#如果w没见过
if w not in seen:
queue.append(w)
#加入seen表示w我们看见过了
seen.add(w)
print(vertex)
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
执行过程：
step 1:queue=[‘A’]->seen=[‘A’]->queue=[ ]->vertex=‘A’->nodes=[‘B’,‘C’]->queue=[‘B’,‘C’]->seen=[‘A’,‘B’,‘C’]->return ‘A’
step 2:vertex=‘B’->queue=[‘C’]->nodes=[‘A’, ‘C’, ‘D’]->queue=[‘C’‘D’]->seen=[‘A’,‘B’,‘C’,‘D’]->return’B’
step 3:vertex=‘C’->queue=[‘D’]->nodes=[‘A’, ‘B’, ‘D’, ‘E’]->queue=[‘D’‘E’]->seen=[‘A’,‘B’,‘C’,‘D’‘E’]->return’C’
…

"DFS的方法就是将BFS中的队列改成栈即可"
def DFS(graph, s):
stack = []
stack.append(s)
seen = set()
seen.add(s)
while len(stack) > 0:
vertex = stack.pop()
nodes = graph[vertex]
for w in nodes:
if w not in seen:
stack.append(w)
seen.add(w)
print(vertex)
print(DFS(graph, 'A'))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
求最短路径问题：

求A到E的最短路径，我们用parent建一个表，表显示每个点的前一个点是哪个点，这样我们先找E的前一个点为C，C的前一个点为A，A前没有点了，因此A到E的最短路径为A->C->E

# 用字典表示S的前一个点为空
parent = {s: None}
之前w的前一个点就是vertex，因此：
parent[w] = vertex
将这两行代码加入之前的代码中：
1
2
3
4
5
完整代码为：

def BFS(graph, s):
queue = []
queue.append(s)
seen = set()
seen.add(s)
parent = {s: None}
while len(queue) > 0:
vertex = queue.pop(0)
nodes = graph[vertex]
for w in nodes:
if w not in seen:
queue.append(w)
seen.add(w)
parent[w] = vertex
print(vertex)
return parent
"测试从‘E’出发"
parent = BFS(graph, 'E')
for key in parent:
print(key, parent[key])
————————————————
原文链接：https://blog.csdn.net/Huangkaihong/article/details/106131950

http://luanren.com/home.php?mod=space&uid=483567

http://luanren.com/home.php?mod=space&uid=289024

http://luanren.com/home.php?mod=space&uid=354351

http://luanren.com/home.php?mod=space&uid=27716

http://luanren.com/home.php?mod=space&uid=485621