BFS ——队列
image-20210129115620630.png
步骤：1、首先A入队列，
2、A出队列时，A的邻接结点B，C相应进入队列
3、B出队列时，B的邻接结点A，C，D中未进过队列的D进入队列
4、C出队列时，C的邻接结点A，B，D，E中未进过队列的E进入队列
5、D出队列时，D的邻接结点B，C，E，F中未进过队列的F进入队列
6、E出队列，没有结点可再进队列
7、F出队列
graph=
{'A':['B','C'],'B':['A','C','D'],
'C':['A','B','D','E'],
'D':['B','C','E','F'],
'E':['D','C'],
'F':['D']}
import queue
def BFS(graph, s):
queue = [] #用数组表示队列
queue.append(s)
seen = set() #存放已经遍历过的节点
seen.add(s)
while len(queue) > 0:
vetex = queue.pop(0) #区别：python中队列和栈都用数组表示，队列取队头pop(0)，弹栈为pop()
nodes = graph[vetex]
for w in nodes:
if w not in seen:
queue.append(w)
seen.add(w)
print(vetex)
BFS(graph,"A")
DFS —— 栈
image-20210129120158011.png
步骤：1、首先A入栈，
2、A出栈时，A的邻接结点B，C相应入栈 （这里假设C在下，B在上）
3、B出栈时，B的邻接结点A，C，D中未进过栈的D入栈
4、D出栈时，D的邻接结点B，C，E，F中未进过栈的E、F入栈（假设E在下，F在上）
5、F出栈时，F没有邻接结点可入栈
6、E出栈，E的邻接结点C，D已入过栈
7、C出栈
def DFS(graph, s):
stack = []
stack.append(s)
seen = set()
seen.add(s)
while len(stack) > 0:
vetex = stack.pop()
nodes = graph[vetex]
for w in nodes:
if w not in seen:
stack.append(w)
seen.add(w)
print(vetex)
