2

【数据结构7】Graph

 3 years ago
source link: https://www.guofei.site/2017/05/18/graph.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

【数据结构7】Graph

2017年05月18日

Author: Guofei

文章归类: 8-数据结构与算法 ，文章编号: 507

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

Edit

Graph

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

Graph

  • graph：G=(V,E)G=(V,E)，其中V是节点(verticle)，E是边(edge)。如果E是有方向的，叫做有向图
  • 加权图：每条边有某种权值
  • 有向（directed）图。
    • i 的入度（in-degree）是指向 i 的边的数量
    • 出度（out-degree）是远离 i 的边的数量。
  • 节点的度(degree)：节点v所在边的个数，
  • 节点的邻居(neighbor)：相同边连接的节点
  • 从 i 到 j 的路径（path）是指从 i 到达 j 的边的序列。该路径的长度（length）等于所经过的边的数量。
  • 图的 直径（diameter） 是指连接任意两个节点的所有最短路径中最长路径的长度。
  • 测地路径（geodesic path）是指两个节点之间的最短路径。

一些特殊的图：

  • 连通图（connected）。任意两点之间都存在路径。
  • 完全图（complete）。任意两点之间都存在边
  • 如果可以回到一个给定节点，则该图是有环的（cyclic）。相对地，如果至少有一个节点无法回到，则该图就是无环的（acyclic）

子图

H=(W,F)H=(W,F)是G=(V,E)G=(V,E)的子图，如果W⊆V,F⊆EW⊆V,F⊆E

路径，环路

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

连通分量

连通分量 定义为最大连通子图。（感觉这个表述有歧义，每个图可以有多个连通分量，连通分量之间没有共同顶点）

TH：一个图含有n个顶点和k条边，那么至少有n-k个连通分量。
（证明：对k做归纳法）

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

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

森林Forest

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

图的同构

同构 的定义 简单图G到简单图H的 同构，指的是存在一个双射f:V(G)→V(H)f:V(G)→V(H)，使得 uv∈E(G)uv∈E(G) 当且仅当 f(u)f(v)∈E(H)f(u)f(v)∈E(H)

容易证明，同构具有反身性、对称性、传递性

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

自补 的定义 如果一个图同构于它的补图，那么称这个图是自补的

算法

生成树

连通无向图G的生成树T是这么定义的：
G=(V,E),T=(V,E1),E1⊆EG=(V,E),T=(V,E1),E1⊆E
(当然，如果G不是连通图，那么也不存在生成树)

最小生成树

T是G的生成树，如果G是加权图，w(T)=∑e∈E1w(e)w(T)=∑e∈E1w(e)
那么，使得w(T)w(T)最小的T，叫做最小生成树

一个定理

假设T是一个有n个节点的无向图，那么以下6个命题等价

  • T是一个树
  • T是无环图，且有n-1个边
  • T是连通图，且有n-1个边
  • 任意两个节点之间有且只有一条路径
  • T是无环图，且任意添加一条边都会产生环路
  • T是连通图，但任意删除一条边都会把T变成两个连通分量

代码表示

list表示法

list-set表示

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
]

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

b in N[a] # 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)
N=[[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]]

N[a][b] # Neighborhood membership
sum(N[f]) # Degree

邻接矩阵：加权图

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的时间复杂度是Θ(n)Θ(n)

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

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK