数据结构与算法：图（一）—— 概念

发表于 | 更新于: | 分类于 | 阅读次数:
字数统计: 4.7k | 阅读时长 ≈ 19

如果一个问题可以基于实体/状态间的某种多对多的关系来求解，那么可以尝试用图的数据结构和相关算法来求解。用图解决实际问题的一般步骤：

  1. 定义图的数据结构：从实际问题中抽象出相互关联的可区分的状态
    1. 状态作为图的顶点：将状态参数作为不同顶点的唯一标识；
    2. 关联作为节点的边：通过这种关联找到顶点的邻接点；
  2. 图的搜索算法：以某种方式沿着图中的边遍历图中各个顶点，图搜索算法可以用来发现图的结构，可以借助一些辅助的数据结构来描述图中的某种结构；
  3. 原问题的求解：基于图的结构和辅助数据结果求解原问题的解；

如果对图的相关算法熟悉的话，那么解决实际问题的关键就在于第一步了，即如何从实际问题中抽象出相互关联的状态，进而定义出图中的不同顶点和边，然后通过合适的搜索算法发现图中的结构，求解原问题的解。本文相关算法实例将按照以上步骤来整理解题思路。

逻辑结构

图G由有限非空的顶点集V和边集E组成，记做G=(V,E)。

1、有向图：图中的边是有向的，u称为边头，v称为边尾

1
2
3
G = (V,E)
V = {A,B,C,D}
E = {<A,D>,<B,A>,<B,C>,<C,A>}

2、无向图：图中的边是无向的

1
2
3
G = (V,E)
V = {A,B,C,D}
E = {(A,B),(A,C),(A,D),(B,C),(C,D)}

3、简单图：无自边无重复边

4、完全图：任意两个节点间都存在边的简单图，对于含n个顶点的无向完全图来说，存在n(n-1)/2条边，对于含n个顶点的有向完全图来说，存在n(n-1)条边

5、子图：图g中顶点集和边集是图G中顶点集和边集的子集

6、连通图：在无向图中，如果任意两个顶点之间都有路径，则称该图为连通图。如果含n个顶点的无向图中边的个数小于n-1，则该图一定不是连通图

7、连通分量：无向图的极大连通子图（子图中包含子图节点间所有可能的边）称为该图的一个连通分量，直观的理解图中可以相互“导电”的节点和边构成图的一个连通分量

8、强连通图：在有向图中，任意两个顶点u,v间都有从u到v和从v到u的路径，则称该图为强连通图

9、强连通分量：有向图的极大强连通子图称为该图的一个强连通分量

10、生成树/生成森林：在连通图中，包含图中所有顶点的一个极小连通子图称为该图的一个生成树；在非连通图中，每个连通分量的生成树构成了非连通图的生成森林

11、顶点的度：在无向图中，顶点v的度等于依附于该顶点的边的个数；在有向图中，顶点v的度等于顶点v的出度和入度之和，顶点v的出度指所有以顶点v开始的边的个数，顶点v的入度指所有以顶点v结束的边的个数

12、边的权：图中每条边可以标上具有某种含义的数值，该数值称为该边的权值

13、路径：u到v的一条路径是指u,p1,p2,…,v，路径上边权值之和称为路径长度，u==v的路径称为回路或环

14、距离：从顶点u到顶点v的最短路径如果存在，则此路径的长度称为从u到v的距离

15、稀疏/稠密图：边很少的图称为稀疏图，反之称为稠密图，一般将E<VlogV的图称为稀疏图

1.2 存储结构

图的存储结构通常包含两个部分：

  1. 顶点存储V：使用某种数据结构存储图中所有顶点，如果用一个列表存储图中所有顶点，那么后面我们就可以用顶点下标来指代该顶点
  2. 关系存储E：存储顶点间的所有邻接关系，关系存储是图的存储结构的核心，根据关系存储形式的不同，可以将图的存储结构划分为邻接表、邻接矩阵、边表等

对于存储结构的选择需要综合考虑空间和时间上的开销，时间上的开销可以用图上最常用的基本操作来衡量，以下简单列举了图中最常用的操作API:

  1. adj(G,u):获取图G中顶点u的所有邻接点
  2. edge(G,u,v):获取图G中的边(u,v)
  3. insert_v(G,u):在图G中添加顶点u
  4. delete_v(G,u):删除图G中的顶点u
  5. insert_e(G,u,v):在图G中添加边(u,v)
  6. delete_e(G,u,v):删除图G中的的边(u,v)

比较常用的几种图的存储结构对于空间存储以及以上各种操作的时间效率：

存储结构 空间 获取邻接点 获取边 插入顶点 删除顶点 插入边 删除边
邻接表 $O(V+E)$ $O(1)$ $O(1)$ $O(V)$ $O(V)$ $O(1)$ $O(1)$
邻接矩阵 $O(V^2)$ $O(V)$ $O(1)$ $O(V)$ $O(V)$ $O(1)$ $O(1)$
边表 $O(V+E)$ $O(E)$ $O(E)$ $O(V)$ $O(E)$ $O(1)$ $O(1)$

假设以上邻接表通过hash实现，可见在大多数情形邻接表的哈希实现效率更高

1.2.1 邻接表

1.2.1.1 邻接表实现

邻接表存储了各个顶点到其邻接点集的映射关系：

  • v1：顶点
  • {$adjv1:weight1,… $}：v1的邻接表
  • adjv1：顶点v1的一个邻接点
  • weight1：边(v1,adjv1)的权重

邻接表存储结构通常包含两部分结构：

  1. 存储图中每个顶点的结构:可以用字典、列表等数据结构
  2. 存储每个顶点的邻接点集：可以用字典、集合、列表、元组、链表等数据结构
1
2
3
4
5
6
# 字典-字典(适用范围最广，可以直接以状态作为键值)
G = {0:{1:1,2:5,3:2},1:{2:3,4:7},2:{5:6},3:{5:8},4:{5:4},5:{}}
# 字典-列表
G = {0:[(1,1),(2,5),(3,2)],1:[(2,3),(4,7)],2:[(5,6)],3:[(5,8)],4:[(5,4)],5:[]}
# 列表-列表(如果顶点不是0~n-1范围，可以定义另一个数组建立下标与顶点的映射)
G = [[(1,1),(2,5),(3,2)],[(2,3),(4,7)],[(5,6)],[(5,8)],[(5,4)],[]]

邻接表基本操作实现

1
2
3
4
5
6
7
8
9
G = {0:{1:1,2:5,3:2},1:{2:3,4:7},2:{5:6},3:{5:8},4:{5:4},5:{}}

def adj(G,u):
    return G[u]

def edge(G,u,v):
    return G[u][v]
print adj(G,1)
print edge(G,1,2)

邻接表转化为邻接矩阵和边表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
G = {0:{1:1,2:5,3:2},1:{2:3,4:7},2:{5:6},3:{5:8},4:{5:4},5:{}}
# 邻接表转化为邻接矩阵
def adj2matrix(G):
    V = G.keys()
    n = len(V)
    matrix = [[float('inf')] * n for _ in xrange(n)]
    for u,adj in G.items():
        for v,w in adj.items():
            matrix[u][v] = w
    return matrix

adj2matrix(G)   
[[inf, 1, 5, 2, inf, inf],
 [inf, inf, 3, inf, 7, inf],
 [inf, inf, inf, inf, inf, 6],
 [inf, inf, inf, inf, inf, 8],
 [inf, inf, inf, inf, inf, 4],
 [inf, inf, inf, inf, inf, inf]]
 
# 邻接表转化为边表
def adj2edge(G):
    V = G.keys()
    n = len(V)
    edge = []
    for u,adj in G.items():
        for v,w in adj.items():
            edge.append((u,v,w))
    return edge

adj2edge(G) 
[(0, 1, 1),
 (0, 2, 5),
 (0, 3, 2),
 (1, 2, 3),
 (1, 4, 7),
 (2, 5, 6),
 (3, 5, 8),
 (4, 5, 4)]

邻接矩阵

邻接矩阵实现

邻接矩阵：用一个二维数组存储图中边的信息

邻接矩阵基本操作实现

1
2
3
4
5
6
7
def adj(G,u):
    return [v for v in G[u] if v != float('inf')]

def edge(G,u,v):
    return G[u][v]
print adj(G,1)
print edge(G,1,2)

邻接矩阵转化为邻接表和边表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
inf = float('inf')
G = [[inf, 1,   5,   2,   inf, inf],
     [inf, inf, 3,   inf, 7,   inf],
     [inf, inf, inf, inf, inf, 6  ],
     [inf, inf, inf, inf, inf, 8  ],
     [inf, inf, inf, inf, inf, 4  ],
     [inf, inf, inf, inf, inf, inf]]
 # 将邻接矩阵转化为邻接表
def matrix2adj(G):
    n = len(G)
    adj = collections.defaultdict(dict)
    for u in xrange(n):
        for v in xrange(n):
            if G[u][v] != float('inf'):
                adj[u][v] = G[u][v]
    return adj
matrix2adj(G) 
defaultdict(dict,
            {0: {1: 1, 2: 5, 3: 2},
             1: {2: 3, 4: 7},
             2: {5: 6},
             3: {5: 8},
             4: {5: 4}})
 # 将邻接矩阵转化为边表
def matrix2edge(G):
    n = len(G)
    edge = []
    for u in xrange(n):
        for v in xrange(n):
            if G[u][v] != float('inf'):
                edge.append((u,v,G[u][v]))
    return edge

matrix2edge(G)
[(0, 1, 1),
 (0, 2, 5),
 (0, 3, 2),
 (1, 2, 3),
 (1, 4, 7),
 (2, 5, 6),
 (3, 5, 8),
 (4, 5, 4)]

边表

边表实现

起点 0 0 0 1 1 2 3 4
终点 1 2 3 2 4 5 5 5
权 1 5 2 3 7 6 8 4

边表中不能包含所有顶点，需与顶点存储相结合使用。

边表基本操作实现

1
2
3
4
5
6
7
8
9
10
11
12
13
def adj(G,u):
    return {y:w for x,y,w in G if x == u}

def edge(G,u,v):
    for x,y,w in G:
        if (x,y) == (u,v):
            return x,y,w
            
    return None
print adj(G,1)
print edge(G,1,2)
{2: 3, 4: 7}
(1, 2, 3)

边表转化为邻接表和邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def edge2adj(G):
    adj = collections.defaultdict(dict)
    for u,v,w in G:
        adj[u][v] = w
    return adj
print edge2adj(G)
defaultdict(<type 'dict'>, {0: {1: 1, 2: 5, 3: 2}, 1: {2: 3, 4: 7}, 2: {5: 6}, 3: {5: 8}, 4: {5: 4}})

def edge2matrix(G,V):
    n = len(V)
    matrix = [[float('inf')] * n for _ in xrange(n)]
    for u,v,w in G:
        matrix[u][v] = w
    return matrix

print edge2matrix(G,xrange(6))
[[inf, 1, 5, 2, inf, inf], 
 [inf, inf, 3, inf, 7, inf], 
 [inf, inf, inf, inf, inf, 6], 
 [inf, inf, inf, inf, inf, 8], 
 [inf, inf, inf, inf, inf, 4], 
 [inf, inf, inf, inf, inf, inf]]

实战篇

python的collections库提供了众多容器，方便对图的操作，包括:

  • defaultdict：常用于存储图的数据结构
  • deque：相比于内置的list，双端队列deque可以实现在O(1)的时间复杂度下在两端进行append和pop操作
  • set：常用于visited

DIJ单源最短路径：488祖玛游戏

应用：

有环、无环、环中元素；

连通子图

强连通图；

生成树；

最小生成树；

最短路径；

802拓扑排序；前提：有向无环图

并查集：

括号匹配：

  1. DFS进行拓扑排序
  2. BFS出度入度进行拓扑排序：每次取出一个入度/出度为0的节点，并更新相关节点的出度/入度；一般由邻接表得到，零度队列、入度字典，出度邻接点；
    1. 初始化零度队列、出度入度字典
    2. 出队收集、更新相关节点的度，如果更新后度为0放入队列！！

割韭菜，有环的话，会把环剩下！！！

从BFS视角看，拓扑排序类似于层序遍历，首先将所有度为0的节点入队，然后每一次出队，修改与出队元素相关的节点的度，将修改后度为0的入队

  1. 邻接法
    1. 邻接矩阵
    2. 邻接表
    3. 邻接字典
  2. 边表法

Dijkstra

前提：如果权值非负，最短路径上的子路径也必定是最短路径

分治思路

尝试用分治思想解决树相关的问题：首先将原问题转化为关于左右子树的子问题(同性质的或不同性质的)，然后通过对子问题进行综合得到原问题的解，可以形式化表示为：

f(root)=h(g(root.left),g(root.right))

这类问题有：

  1. 树是否对称
  2. 树的最大深度
  3. 树中节点值之和
  4. 叶节点最短路径
  5. 到叶节点的路径：最短-最长-和，
  6. 相同树、镜像树

图算法可以看做是树算法的扩展(树可以看做是无环连通图)，所不同的是：

  1. 图可能多源
  2. 图可能包含环
  3. 每个节点由多个邻接点

相应的处理方法：

  1. 遍历图中所有节点，以未访问过的节点为地点进行遍历
  2. 标记每个节点是否访问过，递归调用只发生在未访问过的节点
  3. 找到每个节点的邻接点表示法，遍历每个邻接点进行递归调用

标准的DFS

规范的DFS包括两个步骤：调用时保证合法性，通过参数向下传递数据，通过返回值向上传递数据

  1. 整体遍历dfs(G)：
    1. 初始化标记：将所有节点初始化为未访问
    2. 遍历所有节点：对未访问过的节点调用单源dfs
  2. 单源遍历dfs_visit(v)：
    1. 标记节点：将当前节点标记为已访问
    2. 遍历所有邻接点：对未访问过的邻接点递归调用单源dfs

如何与问题结合：在深度遍历过程中解决实际应用问题

  1. 判断题
  2. 最优题
  3. 列出所有题

DP的两种实现方式：

  1. 自下向上的毯式填表法：先求解边界的较小子问题并填表，再依据状态转移方程依次求解较大子问题并填表，当表填满时，即可方便查到最终问题的解。
    1. 求解次数：所有子问题都将被求解一次；
    2. 查询次数：查询次数等于依赖的边数；
  2. 自上向下递归填表法：如果解已在表中，直接从表中读取，否则通过递归求解，并填表。
    1. 求解次数：只会求解相关的子问题的解，每个子问题只会被求解一次；
    2. 查表次数：等于依赖边数；

评价：自上向下的递归填表法，更加容易实现，且求解次数较少；

表的形式：

  1. 如果问题规模可以通过连续的整数来表示，则一般可以使用矩阵来表示；
  2. 如果问题规模不方便用连续整数表示，则可以用字典表示，{(问题规模的参数):对应的解}；

评价：字典更通用，但会用掉更多的空间；

树宽度

层序遍历：

1
2
3
4
5
Q = [root]
while Q:
    left = Q[0].val
    Q = [y for x in Q for y in [x.left,x.right] if y]
return left

变形：

  1. 逐层处理：每次用新的一层节点替换掉队列中的节点，方便统计总共有多少层、计算每层的统计量；如最左侧、最右侧元素、每层元素个数、最大值、平均值

利用左右子树做递归时边界往往有四种情形：

1
2
3
4
5
6
7
8
9
10
11
if not root:
    pass
elif root.left==None and root.right==None:
    pass
elif root.left==None:
    pass
elif root.right==None:
    pass
else:
    pass

保证边界正确、递归正确，整个过程就是正确的。

树的遍历用的最多的是先序遍历和层序遍历，这可以被看做是图的BFS和DFS，在写法上有些不同，因为单源、无环、邻接点固定，所以写起来更简单：

1
2
3
4
5
def dfs(root):
    if root:
        visit(root)
        for child in [root.left,root.right]:
            dfs(child)

edge = [(i,j) for i in range(m) for j in [0,n-1]]
edge += [(i,j) for j in range(n) for i in [0,m-1]]

关于树的算法：第一反应必须是能否用递归解！！左子树、右子树的解和整体解有什么关系？？分情况讨论后能否和子树的解建立关系？？

如果跟层有关用层序遍历！！

矩阵中的DFS

DFS和DP

在求解DFS最优值时，如果出现了重叠子问题，可以通过记录中间结果来加快求解速度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def dfs(i,j):
    if dp[i][j]:
        return dp[i][j]
    else:
        res = 0
        for ii,jj in adj[i,j]:
            if 合法邻接点:
                res = f(res,dfs(ii,jj))
        dp[i][j] = res
        return res

dp = [[]]
for i in range(m):
    for j in range(n):
        if ...:
            dfs(i,j)

解在dp中

解决问题的一般思路：

问题的结构化描述→设计相关数据结构→设计算法

先写思路，貌似思维更清晰，代码书写速度也更快

连通图、强连通图
连通图：在外层遍历统计进入多少次574朋友圈

图的表示法

https://blog.csdn.net/woaidapaopao/article/details/51732947

邻接法：“节点-邻接点”的形式方便直接用于遍历

  1. 自定义

  2. 邻接矩阵

  3. 邻接表

  4. 邻接字典：{节点:邻接点}

  5. 边表/集合/元组：节点编号+边表[(i,j)]
    210,边表中有可能某些节点未出现

4, [[1,0],[2,0],[3,1],[3,2]]

  1. 递归字典

拓扑排序-有环无环

210

  • 节点颜色：白-灰-黑

  • 边的分类：u→v时v的颜色、判断有无环、两节点在生成树中的关系，白边-灰边-黑边

先判断有环无环：灰边理论

  • 变色时间：拓扑排序、合法括号

在无环状态下，按u.f逆序排列

多源层序遍历：

初始Q放多个就行了

DFS如果需要自己构造图，可以通过构造一个哑结点来简化代码，但是也没必要引入逻辑的例外，反而复杂.不如统一为按图原来最直观的样子不做额外处理！！这样的好处是外层循环调用和内层循环调用形式一样，不用特殊处理了！

判断一个矩阵是否为空：if not any(A):

494一类题：满足条件的路径，中间路径作为DFS的参数，每次维护路径，满足条件时处理

DFS超时的处理思路：DP或者剪枝

待整理：

理论：
实践：索引形式、每种题型的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import collections
T = input()

def solve(adj,n):
    color = [0] * n
    base = set(xrange(n))
    
    def helper(i):
        si = base - set(adj[i])
        si.add(i)
        for j in si:
            if j != i and color[j] == 0:
                color[j] = 1
                ssi = base - set(adj[j])
                ssi.add(j)
                if ssi != si:
                    return False
        return True
        
    for i in xrange(n):
        if color[i] == 0:
            color[i] = 1
            if not helper(i):
                return False
    return True

for _ in xrange(T):
    N,M = map(int,raw_input().split())
    adj = collections.defaultdict(list)
    for _ in xrange(M):
        x,y = map(int,raw_input().split())
        adj[x-1].append(y-1)
        adj[y-1].append(x-1)
    
    def solve(adj,n):
        color = [0] * n
        base = set(xrange(n))

        def helper(i):
            si = base - set(adj[i])
            si.add(i)
            for j in si:
                if j != i and color[j] == 0:
                    color[j] = 1
                    ssi = base - set(adj[j])
                    ssi.add(j)
                    if ssi != si:
                        return False
            return True

        for i in xrange(n):
            if color[i] == 0:
                color[i] = 1
                if not helper(i):
                    return False
        return True
    
    if solve(adj,N):
        print 'Yes'
    else:
        print 'No'
坚持原创技术分享，您的支持将鼓励我继续创作！