最近复习题目，发现对图的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])