簡單來講孟岛，非遞歸形式的DFS使用棧來維護搜索的進程采缚，而BFS使用隊列維護搜索的進程.
圖.png
對于上述圖結(jié)構(gòu)使用字典和列表記錄圖
graph={
'A':['B','C'],
'B':['A','C','D'],
'C':['A','B','D','E'],
'D':['B','C','E','F'],
'E':['C','D'],
'F':['D']
}
- 實現(xiàn)的DFS如下：
使用列表[]模擬棧結(jié)構(gòu)针炉，使用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)
結(jié)果:
In: DFS(graph,'A')
out: A
C
E
D
F
B
- 實現(xiàn)BFS是使用隊列扳抽，隊列頭部彈出的是BFS的訪問結(jié)果
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
