《python算法教程》Day6 - BFS遍历图(邻接字典)BFS简介代码示例

这是《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)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云霄雨霁

追踪收集解决方法

1690
来自专栏青玉伏案

算法与数据结构(十三) 冒泡排序、插入排序、希尔排序、选择排序(Swift3.0版)

本篇博客中的代码实现依然采用Swift3.0来实现。在前几篇博客连续的介绍了关于查找的相关内容, 大约包括线性数据结构的顺序查找、折半查找、插值查找、Fibon...

1887
来自专栏Google Dart

Dart语言指南(二) 顶

Dart是一种面向对象的语言 包含类和基于 mixin 的继承两部分。每个对象是一个类的实例, 并且 Object.是所有类的父类。 基于 mixin 的继承指...

2051
来自专栏木木玲

Reference 、ReferenceQueue 详解

3037
来自专栏散尽浮华

python常用知识梳理

接触python已有一段时间了,下面针对python基础知识的使用做一完整梳理: 1)避免‘\n’等特殊字符的两种方式: a)利用转义字符‘\’ ...

2955
来自专栏前端桃园

看完这几道 Promise 面试题,还被面试官问倒算我输

最近在复习 Promise 的知识,所以就做了一些题,这里挑出几道题,大家一起看看吧。

1061
来自专栏偏前端工程师的驿站

Java魔法堂:四种引用类型、ReferenceQueue和WeakHashMap

一、前言                               JDK1.2以前只提供一种引用类型——强引用 Object obj = new Objec...

2037
来自专栏老九学堂

十七个C语言新手编程时常犯的错误及解决方式

C编译的程序对语法检查并不像其它高级语言那么严格,这就给编程人员留下“灵活的余地”,但还是由于这个灵活给程序的调试带来了许多不便,尤其对初学C语言的人来说,经常...

2977
来自专栏数据之美

Python FAQ(常见问题解答)(1)

声明:转载需署名出处,严禁用于商业用途! 1、python的帮助: help(str) 可以查看str字符类的帮助信息。 2、python没有括号来表明...

2648
来自专栏Java编程技术

并发队列中迭代器弱一致性原理探究

并发队列里面的Iterators是弱一致性的,next返回的是队列某一个时间点或者创建迭代器时候的状态的反映。当创建迭代器后,其他线程删除了该元素时候并不会抛出...

1461

扫码关注云+社区

领取腾讯云代金券