简单来讲，非递归形式的DFS使用栈来维护搜索的进程，而BFS使用队列维护搜索的进程.
图.png
对于上述图结构使用字典和列表记录图
graph={
'A':['B','C'],
'B':['A','C','D'],
'C':['A','B','D','E'],
'D':['B','C','E','F'],
'E':['C','D'],
'F':['D']
}
- 实现的DFS如下：
使用列表[]模拟栈结构，使用set()记录元素访问，栈顶弹出的元素是每次DFS访问的元素
def DFS(graph,s):
stack=[]
visit=set()
stack.append(s)
visit.add(s)
while (len(stack)>0):
vertex=stack.pop()
nodes=graph[vertex]
for node in nodes:
if node not in visit:
stack.append(node)
visit.add(node)
print(vertex)
结果:
In: DFS(graph,'A')
out: A
C
E
D
F
B
- 实现BFS是使用队列，队列头部弹出的是BFS的访问结果
def BFS(graph,s):
queue=[]
visit=set()
queue.append(s)
visit.add(s)
while (len(queue)>0):
vertex=queue.pop(0) #头部弹出
nodes=graph[vertex]
for node in nodes:
if node not in visit:
queue.append(node)
visit.add(node)
print(vertex)
BFS(graph,'A')
A
B
C
D
E
F
