目录
- 1.什么是DFS和BFS?
- 1.1DFS
- 1.2BFS
- 2.DFS和BFS的代码实现
- 2.1DFS的代码实现
- 2.2BFS的代码实现
1.什么是DFS和BFS?
1.1DFS
- DFS,通俗来讲,就是深度优先搜索,它可以通过栈来实现。
举个例子:
图中的例子以A为出发点。
那么DFS的其中一个结果就是ABDFEC。
简单点概括就是一条路走到黑,如果无路可走了,就会有一个回溯的过程,直到所有的节点都已经走过了。
1.2BFS
- BFS,通俗来讲,就是广度优先搜索,它可以通过队列来实现。
也是上面的图片的例子:
BFS的其中一个结果就是:ABCDEF,
概括来说,就是把每个的相关点都依次的写出来。
2.DFS和BFS的代码实现
2.1DFS的代码实现
graph = {
'A':['B','C'],
'B':['A','C','D'],
'C':['A','B','D','E'],
'D':['B','C','E','F'],
'E':['C','D'],
'F':['D'],
}
def DFS(graph,s): #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)
DFS(graph,'A')
A
C
E
D
F
B
2.2BFS的代码实现
graph = {
'A':['B','C'],
'B':['A','C','D'],
'C':['A','B','D','E'],
'D':['B','C','E','F'],
'E':['C','D'],
'F':['D'],
}
def BFS(graph,s): #graph表示图表关系,s表示开始的节点
queue = [] #新建队列
queue.append(s) #将初始节点加入到队列中
seen = set() #建立一个集合,后续判断是否重复
seen.add(s)
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)
print(vertex)
BFS(graph,'A')
A
B
C
D
E
F
更多推荐
关于DFS和BFS算法——Python的代码实现和讲解。
发布评论