DFS与BFS的python实现

本文主要是介绍DFS与BFS的python实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

最近复习题目，发现对图的python实现比较无知，所以实现一下。

在python中采用字典来表示图的结构，访问非常方便。

BFS与DFS非递归的写法最大的差别是在遍历的过程中路过的结点一个用队列保存，一个用栈保存，其他结构几乎是一样的！

这么理解的话应该很好记忆了

直接上代码

graph={
    1:[2,6],
    2:[1,3],
    3:[2,4,6],
    4:[3,5],
    5:[4,6],
    6:[1,3,5]

}
 
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:  # 如果w没挖掘过，就放进去
                stack.append(w)
                seen.add(w)
        print(vertex)
    return




def BFS(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: #如果w没挖掘过，就放进去
                queue.append(w)
                seen.add(w)
        print(vertex)
    return


BFS(graph,list(graph.keys())[0])
DFS(graph,list(graph.keys())[0])

这篇关于DFS与BFS的python实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！