《算法图解》note 6 图以及广度优先搜索和深度优先搜索1.图2.广度优先搜索3.深度优先搜索

这是《算法图解》第六篇读书笔记,涉及的主要内容为图结构、深度优先搜索和广度优先搜索。

1.图

1.1图的概述

图(graph)是一种基本的数据结构,它由点和边构成。 根据边有无指向性,可将图分为有向图、无向图。这两种图分别表明点与点之间的关系是单向的(有向图)还是过双向的(无向图)。

1.2图的用途

图可用于表示物体之间的关系,以及用于查找两地点之间的最短路径等。

1.3图的存储结构(python实现有向图)

图的存储结结构可分为邻接矩阵和邻接列表。 下文将按下图展示邻接矩阵和邻接表。 先约定三点: (1)为简化起见,若使用索引时,字母a至f分别由数字0至5表示。 (2)下方展示的是有向图。

图.JPG

1.3.1邻接矩阵

邻接矩阵的存储思路是枚举所有节点两两组合(包括节点自身)形成一个二维矩阵。若两个节点间联系,则在相应的矩阵位置标记为1,否则为0,指向为由行坐标所指代的节点指向纵坐标所指代的节点。 在python中,邻接矩阵可用套嵌的列表实现。在最外层的列表索引代表矩阵横坐标的节点。外层列表的每一个元素嵌入一个列表,套嵌列表索引代表矩阵处于纵坐标的节点。 代码如下:

G=[
[0,1,0,0,0,1],
[0,0,1,1,0,0],
[0,0,0,1,0,0],
[0,0,0,0,1,1],
[0,0,0,0,1,1],
[0,0,0,0,0,0]
]

1.3.2邻接列表(字典)

邻接列表(字典)只会显示每个节点及其所指向的下一节点。邻接列表与邻接字典的不同之处在于临界列表是用数据代表字母,邻接字典直接存储节点的字母编号。 以下是邻接列表的实现方式:

G=[
[1,5],
[2,3,5],
[3],
[4,5],
[5],
[]
]

以下是邻接字典的实现方式:

G={
'a':{'b','f'},
'b':{'c','d','f'},
'c':{'d'},
'd':{'e','f'},
'e':{'f'},
'f':{}
}

2.广度优先搜索

广度优先搜索(breath-first search)可用于搜索图的最短路径,其思路是先搜索每一层次的节点,搜索完毕后,再搜索下一层次的节点。 代码如下

#迭代版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)

3.深度优先搜索

深度优先搜索(depth first search)是搜索图时常用的另一种方法。

代码如下:

迭代版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 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

POJ 1659 Frogs' Neighborhood(可图性判定—Havel-Hakimi定理)【超详解】

Frogs' Neighborhood Time Limit: 5000MS Memory Limit: 10000K Total Submis...

2988
来自专栏mathor

C++STL中vector使用策略(二)

1714
来自专栏数据小魔方

左右用R右手Python9——字符串合并与拆分

在文本处理和数据清洗阶段,对字符串或者字符型变量进行分割、提取或者合并虽然谈不上什么高频需求,但是往往也对很重要的。 接下来跟大家大致盘点一下在R语言与Pyh...

3465
来自专栏杨建荣的学习笔记

Java随机数算法(一)(r11笔记第14天)

问:如何生成一个随机的字符串?答:让新手退出VIM 。 这可能也是随机字符的一种由来:) 我们今天要说的是随机数算法,这个我策划了好久,但是进展缓慢。...

4347
来自专栏有趣的Python

数据结构探险之图篇(上)理论篇数据结构探险之图篇

数据结构探险之图篇 什么是图? 如下图:无向图 & 有向图 箭头分方向。 无向图中每条认为有来有回两条线 ? 无向图&有向图 图中的概念: ? 有向图...

3866
来自专栏数说工作室

【SAS Says】基础篇:5. 开发数据(一)

本节目录: 开发数据 5.1 创建并重新定义变量 5.2 使用SAS函数 5.3 使用IF-THEN语句 5.4 用IF-THEN语句将观测值分组 5.5 构造...

3224
来自专栏WD学习记录

LeetCode Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

1011
来自专栏IT可乐

由HashMap哈希算法引出的求余%和与运算&转换问题

1573
来自专栏云霄雨霁

有向图----有向环检测和拓扑排序

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

基础野:细说无符号整数

Brief                                 本来只打算理解JS中0.1 + 0.2 == 0.30000000000000004...

2056

扫码关注云+社区

领取腾讯云代金券