【数据结构8】Graph



2017年05月18日    Author:Guofei

文章归类: 0x80_数据结构与算法    文章编号: 582

版权声明:本文作者是郭飞。转载随意,但需要标明原文链接,并通知本人
原文链接:https://www.guofei.site/2017/05/18/graph.html


基本定义

如果我们的工作可以诠释成graph,那么我们至少接近解决方案了。如果能诠释成tree,那么已经拥有一个解决方案了 例如,XML文档或目录结构都是tree
例如,机器学习中的决策树也是tree,而神经网络一般是graph

一些定义

【定义】图 Graph:一个图是一个三元组,$(V,E,\phi)$,其中 V是节点(verticle)的集合,E是边(edge)的集合,函数 $\phi$ 是从边集合到节点的无序偶(有序偶)上的函数。

  • $\phi$ 把边 $e_i$ 映射到无序偶 $(v_j, v_k)$,这条边叫做 无向边
  • $\phi$ 把边 $e_i$ 映射到有序偶 $<v_j, v_k>$,这条边叫做 有向边
  • 一个图所有的边都是无向边,叫做 无向图
  • 一个图所有的边都是有向边,叫做 有向图

其它定义

  • 加权图:每条边有某种权值
  • 节点的度(degree):节点v所在边的个数,
  • 节点的邻居(neighbor):相同边连接的节点
  • 从 i 到 j 的路径(path)是指从 i 到达 j 的边的序列。该路径的长度(length)等于所经过的边的数量。
  • 图的 直径(diameter) 是指连接任意两个节点的所有最短路径中最长路径的长度。
  • 测地路径(geodesic path)是指两个节点之间的最短路径。
  • $v_i,v_j$ 之间可以有多条边,它们叫做 平行边
    • 如果一个图含有平行边,这个图叫做 多重图

一些特殊的图:

  • 完全图(complete)。任意两点之间都存在边
    • 定理: 一个完全图有n个节点,那么有 $n(n-1)/2$ 条边
  • 连通图(connected)。任意两点之间都存在路径。
  • 如果可以回到一个给定节点,则该图是有环的(cyclic)。相对地,如果至少有一个节点无法回到,则该图就是无环的(acyclic)

定理

  • 一个图中,节点的度之和,等于边数的两倍。证明:一个边必然对应两个节点,造成两个度
  • 一个图中,度数为奇数的节点必然是偶数个。证明:用上面这条。

对于有向(directed)图:

  • i 的入度(in-degree)是指向 i 的边的数量
  • 出度(out-degree)是远离 i 的边的数量。
  • 【定理】 入度之和等于出度之和

补图和子图

【定义】子图: $H=(W,F)$是$G=(V,E)$的子图,如果$W \subseteq V,F \subseteq E$

【定义】补图: 一个图G,有G所有节点和所有能使G称为完全图的添加边所组成的图,叫做 G 的补图

【定义】相对补图: $G_1=(V_1,E_1)$ 是 $G=(V, E)$ 的子图,如果 有 $G_2=(V_2, E_2)$,其中 $E_2=E-E_1$,$V_2$ 是与 $E_2$ 有关的节点,那么叫做 $G_2$ 是 $G_1$ 相对 $G$ 的补图

图的同构

同构 的定义:给定两个简单图 $G = (V, E), G_1 = (V_1, E_1)$,如果满足以下条件,称为这两个图同构

  1. 存在一一映射 $g:V\to V_1$
  2. 边 $(v_i, v_j) \in E$ 当且仅当 $(g(v_i), g(v_j))\in E_1$ (对于有向图有对应的形式)

定理: 容易证明,同构具有反身性、对称性、传递性

定理:两个简单图同构,当且仅当它们的补图也同构。

定理 两个图同构的必要条件(不是充分条件)

  1. 结点数量相同
  2. 边数相同
  3. 度数相同的结点数目相同

【定义】自补 :如果一个图同构于它的补图,那么称这个图是自补的

路径,环路

  • 路径 是这样的子图,边是连续连接节点构成的
  • 路径终点上添加一条指向起点的边,构成一条环路(cycle)
  • 路径的长度:路径上各边权重的和。如果是无权图,每个边的权重视为1.

【定理】 一个图有 n 个节点,如果 $v_i, v_j$ 之间有路径,那么存在一个路径,其长度不多于 n-1

连通

  • 【定义】连通 无向图中,如果两个节点 $v_i, v_j$ 之间有路径,称它们是连通的。
  • 【定义】连通子图
  • 【定义】连通图 如果一个图只有一个连通子图,称为连通图
  • 【定义】连通分量 最大连通子图的个数
    • 【定理】 如果一个图含有n个顶点和k条边,那么至少它有n-k个连通分量。(证明:对k做归纳法)

【定义】点割集 无向图 $G = (V, E)$ 是连通图,若一个点集 $V_1$,使得图 G 删除 $V_1$ 所有节点后,所得的子图是不连通的,而删掉任意 $V_1$ 的真子集后,所得子图仍然是连通图。称 $V_1$ 是点割集。如果 $V_1$ 中只有一个元素,称这个点是 割点 - 点割集可以有多个,定义数量最少的那个点割集,其数量为 点连通度 $k(G)$. 它其实是把一个连通图变成不连通图,至少要删掉多少个点

【定义】边割集 定义类似上面的点割集。类似也有定义 边连通度

【定理】 一个无向图 G 中的节点 v 是割点的充分必要条件是存在两个节点 $u, w$ 使得 $u, w$ 的每一条路都通过 v

割边
这样的边:如果删除,连通分量的个数将增加1

TH:一条边是割边当且仅当它不属于任何一个环

【定义】有向图的连通情况

  • 对于所有节点对,至少某一个方向可达,称为 单侧连通
  • 对于所有节点对,都双向可达,称为 强连通

【定理】 一个有向图是强连通的,当且仅当 G 中有一个这样的回路,它至少包含每个节点一次。

图的矩阵表示

森林Forest

  • 不包含环的图叫做无环图
  • 无向的无环图叫做森林
  • 连通的森林叫做
  • Forest可以由一个或多个tree构成

图的表示

图的 list表示法

list-set表示

v1, v2, v3, v4, v5, v6, v7, v8 = range(8)
N = [
    {v2, v3, v4, v5, v6}, # v1
    {v3, v5},             # v2
    {v4},                 # v3
    {v5},                 # v4
    {v6},                 # v5
    {v3, v7, v8},         # v6
    {v6, v8},             # v7
    {v6, v7},             # v8
]

set与dict都是用hash方法实现的,因此访问时间是 $\Theta(1)$,最坏时间是 $\Theta(n)$

用法:

v2 in N[v1]  # Neighborhood membership
len(N[f])  # Degree

list表示

a, b, c, d, e, f, g, h = range(8)
N = [
    [b, c, d, e, f],  # a
    [c, e],           # b
    [d],              # c
    [e],              # d
    [f],              # e
    [c, g, h],        # f
    [f, h],           # g
    [f, g],           # h
]

list-dict表示:用于加权图

a,b,c,d,e,f,g,h=range(8)
N=[
    {b:2,c:1,d:3,e:9,f:4}, #a
    {c:4,e:3},       #b
    {d:8},       #c
    {e:8},           #d
    {f:7},      #e
    {c:2,g:2,h:2},  #f
    {f:1,h:6},    #g
    {f:9,g:8},   #h
]

一些用法:

b in N[a] # Neighborhood membership
len(N[f]) # Degree
N[a][b]# Edge weight for (a,b)

dict-dict表示:加权图

a, b, c, d, e, f, g, h = range(8)
G = {
    a: {b: 2, c: 1, d: 3, e: 9, f: 4},
    b: {c: 4, e: 3},
    c: {d: 8},
    d: {e: 8},
    e: {f: 7},
    f: {c: 2, g: 2, h: 2},
    g: {f: 1, h: 6},
    h: {f: 9, g: 8},
}

用法

[(G[u][v], u, v) for u in G for v in G[u]]

图的邻接矩阵表示

a, b, c, d, e, f, g, h = range(8)
A = [[0, 1, 1, 1, 1, 0, 1, 1],
       [1, 0, 1, 0, 1, 0, 1, 1],
       [0, 0, 0, 1, 1, 1, 1, 0],
       [1, 0, 0, 0, 1, 0, 0, 0],
       [0, 1, 1, 0, 0, 0, 1, 1],
       [1, 0, 1, 0, 0, 0, 0, 0],
       [1, 1, 0, 0, 0, 1, 0, 1],
       [1, 0, 1, 0, 1, 1, 1, 0]]
A[a][b] # Neighborhood membership
sum(A[f]) # Degree

性质

  • 对于无向图来说,邻接矩阵是对称矩阵。

路径数量问题(结论对有向图、无向图都一样)

  • 矩阵幂 $F = A^2$ 中的某个元素 $f_{ij}$ 指的是节点 i 到节点 j 的长度为 2 的路径的数量。(证明:用矩阵积的定义)
  • 矩阵幂 $G = N^i$ 中的某个元素 $g_{ij}$ 指的是节点 i 到节点 j 的长度为 i 的路径的数量

为了考察节点之间的 可达性,注意到这个事实:

  • 定理 如果图 G 中有 n 个节点,那么如果 i,j 之间有通路,那么肯定有一条通路,其长度 $l\leq n$
  • 这个定理保证了,我们在考察节点可达性时,最多考虑 n 次幂即可。

定义可达矩阵 B,其中 $b_{ij} = 1$ 表示两个节点可达,$b_{ij} = 0$ 表示两个节点不可达。

  • 就有这个结论 $B = bool(A + A^2 + … + A^n)$
  • 上面的运算复杂度太高,其实我们只关心节点可达性,就定义一个相应的布尔幂即可(布尔幂就不多写了)

邻接矩阵:加权图

inf = float('inf')
a, b, c, d, e, f, g, h = range(8)
N = [[0, 111, 88, 96, 116, 102, 71, 176],
     [inf, 0, 32, 19, inf, inf, 64, 210],
     [110, 35, 0, 144, 108, 106, 35, 126],
     [inf, inf, inf, 0, 15, 38, 119, inf],
     [inf, inf, 58, 105, 0, inf, 19, inf],
     [148, inf, 143, inf, 44, 0, 154, 163],
     [49, 174, 68, 48, 258, 76, 0, inf],
     [99, 143, 85, 159, 2, 44, 74, 0]]
N[a][b] #<inf # Neighborhood membership
sum([1 for i in N[e] if i<inf])-1 # Degree

取Degree的时间复杂度是$\Theta(n)$

图的点边矩阵表示

对于无向图来说,点边矩阵是这样的

e1e2e3e4e5
v110010
v211001
v301100
v400111

例如,v2e5 和 v4e5 位置都是 1 ,这表示 v2v4 之间有一条标,这条边是 e5

一些性质

  • 每一列只有 2 个 1
  • 每一行的和是节点的度
  • 如果某一行全0,这个节点是孤立节点
  • 对于2个平行边来说,对应的两个列相同

对于无向图来说,点边矩阵是这样的

e1e2e3e4e5
v110010
v2-11001
v30-1100
v400-1-1-1

例如, v1e1 位置为 1,v2e1 位置是 -1,这表示 v1到v2 有一条有向边,这条边是 e1

有类似的性质。

节点合并 图上的两个节点i, j 合并,对应的点边矩阵做如下操作,ij 这两行相加取模2 (这个结论对有向图、无向图都成立)

定理 一个连通图 G 有 r 个节点,那么对应的点边矩阵的秩是 r-1

  • 点边矩阵每一行都有2个1,加到最后一列

图上的算法

图的遍历

图的深度优先搜索:用stack,

图的广度有显示搜索:用 queue

生成树

代码见于另一个博客

最短距离-Dijkstra

Dijkstra 算法是一种贪心算法。用来计算某个点到其它所有点的距离(不是路径)

算法步骤:

  1. D[k]=A[F,k],是一个 N 维度数组,代表 F 到 k 的最短距离
  2. S={F,} 代表已经找到最短路径的定点的集合
  3. V-S 中找到一个顶点x,使得 $D(x)$ 最小,然后把x放入 S 中
  4. 重新计算最优距离 D(I)=min(D(I),D(x)+A(x,I))
  5. 回到3,直到 V-S 为空

用 numpy 的版本

import numpy as np


def build_graph_matrix(path_cost, num_vertex):
    graph_matrix = np.ones((num_vertex, num_vertex)) * np.inf
    # 返回图对应的矩阵
    for i in range(num_vertex):
        graph_matrix[i][i] = 0  # 对角线设为0

    for start_point, end_point, distance in path_cost:
        graph_matrix[start_point][end_point] = distance
    return graph_matrix


def shortest_path(vertex1, graph_matrix):
    num_vertex = graph_matrix.shape[0]  # 顶点数量
    distances = graph_matrix[vertex1].copy()  # 用来记录 vertex1 到每个顶点的最短路径
    shortest_vertex = 0  # 记录最短距离的顶点
    goal = np.zeros(num_vertex)  # 用来记录该顶点是否被选取
    goal[vertex1] = 1

    for i in range(num_vertex):
        shortest_distance = np.inf
        for j in range(num_vertex):
            if goal[j] == 0 and shortest_distance > distances[j]:
                shortest_distance = distances[j]
                shortest_vertex = j
        goal[shortest_vertex] = 1
        # 更新 vertex1 到各顶点的最短距离:
        for j in range(num_vertex):
            if goal[j] == 0 and \
                    distances[shortest_vertex] + graph_matrix[shortest_vertex][j] \
                    < distances[j]:
                distances[j] = distances[shortest_vertex] \
                               + graph_matrix[shortest_vertex][j]

    return distances


# %%
path_cost = [[0, 1, 29],
             [1, 2, 30],
             [1, 3, 35],
             [2, 4, 28],
             [2, 5, 87],
             [3, 4, 42],
             [3, 5, 75],
             [4, 5, 97]
             ]

num_vertex = 6  # 顶点数量

graph_matrix = build_graph_matrix(path_cost, num_vertex)
distances = shortest_path(0, graph_matrix)  # 搜索最短路径
print('-----------------------------------')
print('顶点1到各顶点最短距离的最终结果')
print('-----------------------------------')
for j in range(num_vertex):
    print('顶点 0到顶点%2d的最短距离=%3d' % (j, distances[j]))
print('-----------------------------------')

不用 numpy 的版本

INFINITE = 99999  # 无穷大


def build_graph_matrix(path_cost, num_vertex):
    # 返回图对应的矩阵
    graph_matrix = [[INFINITE] * num_vertex for _ in range(num_vertex)]
    for i in range(num_vertex):
        graph_matrix[i][i] = 0  # 对角线设为0

    for start_point, end_point, distance in path_cost:
        graph_matrix[start_point][end_point] = distance
    return graph_matrix


def shortest_path(vertex1, graph_matrix):
    num_vertex = len(graph_matrix)  # 顶点数量
    distances = graph_matrix[vertex1].copy()  # 用来记录 vertex1 到每个顶点的最短路径
    shortest_vertex = 0  # 记录最短距离的顶点
    goal = [0] * num_vertex  # 用来记录该顶点是否被选取,

    goal[vertex1] = 1

    for i in range(num_vertex):
        shortest_distance = INFINITE
        for j in range(num_vertex):
            if goal[j] == 0 and shortest_distance > distances[j]:
                shortest_distance = distances[j]
                shortest_vertex = j

        goal[shortest_vertex] = 1
        # 更新 vertex1 到各顶点的最短距离
        for j in range(num_vertex):
            if goal[j] == 0 and \
                    distances[shortest_vertex] + graph_matrix[shortest_vertex][j] \
                    < distances[j]:
                distances[j] = distances[shortest_vertex] \
                               + graph_matrix[shortest_vertex][j]

    return distances


# %%
path_cost = [[0, 1, 29],
             [1, 2, 30],
             [1, 3, 35],
             [2, 4, 28],
             [2, 5, 87],
             [3, 4, 42],
             [3, 5, 75],
             [4, 5, 97]
             ]

num_vertex = 6  # 顶点数量

graph_matrix = build_graph_matrix(path_cost, num_vertex)
distances = shortest_path(0, graph_matrix)  # 搜索最短路径
print('-----------------------------------')
print('顶点1到各顶点最短距离的最终结果')
print('-----------------------------------')
for j in range(num_vertex):
    print('顶点 0到顶点%2d的最短距离=%3d' % (j, distances[j]))
print('-----------------------------------')

输出结果

顶点 1到顶点 1的最短距离=  0
顶点 1到顶点 2的最短距离= 29
顶点 1到顶点 3的最短距离= 59
顶点 1到顶点 4的最短距离= 64
顶点 1到顶点 5的最短距离= 87
顶点 1到顶点 6的最短距离=139

最短距离-Floyd 算法

如果想找到所有点之间,两两点之间的最短距离, Floyd 算法更为有效。Floyd 算法和 Dijstra 算法的底层逻辑一样。

  1. D[i,j]=M[i,j] ,其中 D[i,j] 代表i到j的最短距离,M是图对应的距离矩阵
  2. 遍历k,求出 D[i,j] = min(D[i,j], D[i,k]+D[k,j])
  3. 重复第 2 步n次,n是顶点个数。
SIZE = 7
NUMBER = 6
INFINITE = 99999  # 无穷大

Graph_Matrix = [[0] * SIZE for row in range(SIZE)]  # 图的数组
distance = [[0] * SIZE for row in range(SIZE)]  # 路径长度数组


# 建立图
def BuildGraph_Matrix(Path_Cost):
    for i in range(1, SIZE):
        for j in range(1, SIZE):
            if i == j:
                Graph_Matrix[i][j] = 0  # 对角线设为0
            else:
                Graph_Matrix[i][j] = INFINITE
    # 存入图的边
    i = 0
    while i < SIZE:
        Start_Point = Path_Cost[i][0]
        End_Point = Path_Cost[i][1]
        Graph_Matrix[Start_Point][End_Point] = Path_Cost[i][2]
        i += 1


# 打印出图

def shortestPath(vertex_total):
    # 初始化图的长度数组
    for i in range(1, vertex_total + 1):
        for j in range(i, vertex_total + 1):
            distance[i][j] = Graph_Matrix[i][j]
            distance[j][i] = Graph_Matrix[i][j]

    # 使用Floyd算法找出所有顶点两两之间的最短距离
    for k in range(1, vertex_total + 1):
        for i in range(1, vertex_total + 1):
            for j in range(1, vertex_total + 1):
                if distance[i][k] + distance[k][j] < distance[i][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]


Path_Cost = [[1, 2, 20], [2, 3, 30], [2, 4, 25], \
             [3, 5, 28], [4, 5, 32], [4, 6, 95], [5, 6, 67]]
BuildGraph_Matrix(Path_Cost)
print('===============================================')
print('      所有顶点两两之间的最短距离: ')
print('===============================================')
shortestPath(NUMBER)  # 计算所有顶点间的最短路径
# 求得两两顶点间的最短路径长度数组后,将其打印出来
print('      顶点1  顶点2  顶点3  顶点4  顶点5  顶点6')
for i in range(1, NUMBER + 1):
    print('顶点%d' % i, end='')
    for j in range(1, NUMBER + 1):
        print('%6d ' % distance[i][j], end='')
    print()
print('===============================================')
print()

输出

-----------------------------------
顶点1到各顶点最短距离的最终结果
-----------------------------------
顶点 0到顶点 0的最短距离=  0
顶点 0到顶点 1的最短距离= 29
顶点 0到顶点 2的最短距离= 59
顶点 0到顶点 3的最短距离= 64
顶点 0到顶点 4的最短距离= 87
顶点 0到顶点 5的最短距离=139
-----------------------------------

###= AOV 网络与拓扑排序

把一个网状的任务依赖顺序,变成一个线性的排序


您的支持将鼓励我继续创作!