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

billyang916

发布于 2018-06-04 14:54:23

1K0

发布于 2018-06-04 14:54:23

文章被收录于专栏：python读书笔记

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

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)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018.06.02 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法