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

这是《python算法教程》的第5篇读书笔记。这篇笔记的主要内容为运用DFS(深度优先搜索,depth first search)对图(邻接字典)进行遍历。

DFS简介

在解决问题的时候,需要对整个图进行遍历,以获取整个图的节点信息。此时遍历的思路是根据当前访问的点,访问其邻接点,最终使得整个图的节点均被访问。此时,访问邻接节点的策略有DFS(深度优先搜索)和BFS(广度优先搜索)。DFS是先访问当前节点的一个邻接节点,再继续访问该邻接节点的邻接节点,直到访问的邻接节点没有邻接节点。之后再访问上一层节点的另外一个邻接节点,然后继续访问这另一个邻接节点的邻接节点。

代码示例

以下将根据下图给出递归版和迭代版的深度优先搜索代码。

DAG.JPG

递归版DFS

#递归版DFS
def dfs(G,s,S=None,res=None):
    if S is None:
        #储存已经访问节点
        S=set()
    if res is None:
        res=[]
    res.append(s)
    S.add(s)
    for u in G[s]:
        if u in S:
            continue
        S.add(u)
        dfs(G,u,S,res)
    return res

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

res=dfs(G,'a')
print(res)

迭代版DFS

#迭代版DFS
def dfs(G,s):
    Q=[]
    S=set()
    Q.append(s)
    while Q:
        u=Q.pop()
        if u in S:
            continue
        S.add(u)
        Q.extend(G[u])
        yield u
#有向无环图的邻接字典
G={
    'a':{'b','f'},
    'b':{'c','d','f'},
    'c':{'d'},
    'd':{'e','f'},
    'e':{'f'},
    'f':{}
}

res=list(dfs(G,'a'))
print(res) 

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

搜索(1)

 在讨论图的遍历问题之前,我们先来讨论一下图的存储问题,也就是我们在写程序的时候如何保存、表示一个图。首先我们会用连续的整数编号来表示点集。比如1号顶点、2号顶...

1121
来自专栏从流域到海域

图(Graph)的常用代码集合

图的相关概念请查阅离散数学图这一章或者数据结构中对图的介绍。代码来自课本。 /*Graph存储结构*/ //邻接矩阵表示法 #define MAX_VERTEX...

3476
来自专栏向治洪

图算法之bfs、dfs、prim、Dijkstra

概述 在图算法中经常要执行遍历每个顶点和每条边的操作,即图搜索。许多图算法都以图搜索为基础,如2-着色问题、连通性计算基于深度优先搜寻(depth-first ...

4346
来自专栏机器学习与自然语言处理

Lake Counting(POJ-2386)

题目链接: http://poj.org/problem?id=2386 题目大意: 计算出相连的'W'有多少块 所需算法: 深度优先搜索(DFS) 主要思路:...

2347
来自专栏机器学习与自然语言处理

判断有向图是否有圈

1. 拓扑排序 拓扑排序是对有向无圈图的顶点的一种排序:如果存在一条vi到vj的路径,则vj排在vi后面(因为只要满足这个特性就是拓扑序列,所以它不一定是唯一的...

3738
来自专栏calmound

HDU 3652 B-number(数位DP)

http://acm.hdu.edu.cn/showproblem.php?pid=3652 题意:类似3555,0-n之间某个数中包含13,且整个数能被13...

3376
来自专栏用户画像

5.3.2 深度优先搜索(Depth-First-Search,DFS)

与广度优先搜索不同,深度优先搜索(DFS)类似于树的先序遍历。正如其名称中所暗含的意思一样,这种搜索所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下...

923
来自专栏架构之路

Kosaraju算法、Tarjan算法分析及证明--强连通分量的线性算法

一、背景介绍 强连通分量是有向图中的一个子图,在该子图中,所有的节点都可以沿着某条路径访问其他节点。强连通性是一种非常重要的等价抽象,因为它满足 自反性:顶点V...

3656
来自专栏恰同学骚年

数据结构基础温故-5.图(上):图的基本概念

前面几篇已经介绍了线性表和树两类数据结构,线性表中的元素是“一对一”的关系,树中的元素是“一对多”的关系,本章所述的图结构中的元素则是“多对多”的关系。图(Gr...

992
来自专栏kalifaの日々

C++迪杰斯特拉最短路径算法实现

input 第一行表示这个图有4条边,下面五行代表这个图的5条边。 4 0 2 2 0 1 5 1 3 2 2 3 6 -1 0 0 ? 输入样例 out 分别...

3184

扫码关注云+社区

领取腾讯云代金券