美文网首页Python学习日志《python算法基础》读书笔记
《python算法教程》Day6 - BFS遍历图(邻接字典)

《python算法教程》Day6 - BFS遍历图(邻接字典)

作者: billyang916 | 来源:发表于2018-04-16 23:56 被阅读25次

这是《python算法教程》的第6篇读书笔记。笔记的主要内容为BFS(广度优先搜索,breath-first search)。

BFS简介

BFS会对图逐层访问记先访问某个节点的所有临接节点,之后再访问这个节点的其中一个临接节点的所有临接节点。以下图为例,BFS先访问a节点的邻接节点b、f;再访问b的邻接节点c、d、f;接下来访问a的另一个邻接节点 f 的邻接节点……

代码示例

BFS将遍历下图。


DAG.JPG
#迭代版bfs
import collections

def bfs(G,s):
    #P为记录每一个节点的父节点的字典
    P={s:None}
    Q=collections.deque()
    Q.append(s)
    while Q:
        u=Q.popleft()
        for v in G[u]:
            if v in P.keys():
                continue
            P[v]=P.get(v,u)
            Q.append(v)
    return P

#图的邻接字典
G={
    'a':{'b','f'},
    'b':{'c','d','f'},
    'c':{'d'},
    'd':{'e','f'},
    'e':{'f'},
    'f':{}
}

P=bfs(G,'a')
print(P)


#获取a至e的路径
u='e'
path=[u]
while P[u] is not None:
    path.append(P[u])
    u=P[u]
path.reverse()
print(path)

相关文章

  • 《python算法教程》Day6 - BFS遍历图(邻接字典)

    这是《python算法教程》的第6篇读书笔记。笔记的主要内容为BFS(广度优先搜索,breath-first se...

  • 图论小结

    图的存储 邻接矩阵 邻接表 图的遍历 DFS(双向DFS) BFS(剪枝) 单源最短路径算法 dij 条件:无负权...

  • 图的遍历

    1.采用深度优先搜索(DFS)遍历图 邻接矩阵: 邻接表: 2.采用广度优先搜索(BFS)遍历图 邻接矩阵: 邻接...

  • 《python算法教程》Day5 - DFS遍历图(邻接字典)

    这是《python算法教程》的第5篇读书笔记。这篇笔记的主要内容为运用DFS(深度优先搜索,depth first...

  • 五. 图

    图的存储 顺序表(矩阵存储) 链表(邻接链表) 图的遍历 BFS, DFS 图的最小生成树 Prim, Krusk...

  • 第七章 图

    邻接表定义 邻接表求各点入度 邻接表各点出度 DFS与BFS遍历 已知一个无向图G的邻接表存储表示如下,试写出从顶...

  • 图的搜索算法:BFS和DFS详解(Java实现)

    图的搜索算法:BFS和DFS详解(Java实现) 上一篇我们介绍了图的基本概念以及图的存储方式:邻接矩阵和邻接表;...

  • 课程设计——图的建立和遍历(基于邻接表和邻接矩阵存储)

    本课程设计主要完成邻接矩阵和邻接表两种不同存储方式的图的建立和遍历,其中遍历部分分别进行了DFS和BFS两种不同形...

  • 图的桥和割点

    内容概要: 图中的桥 图的DFS遍历树和BFS遍历树及其与寻桥算法的关系 图的割点 DFS和BFS的对比小结 桥(...

  • 从0开始——图

    1图的概念 2.图的存储结构 1.邻接矩阵 2.邻接表 3.图的遍历 1.2邻接表的深度优先算法 1.3扩展:马踏...

网友评论

    本文标题:《python算法教程》Day6 - BFS遍历图(邻接字典)

    本文链接:https://www.haomeiwen.com/subject/qlbykftx.html