Python数据结构之图的存储结构详解

第Python数据结构之图的存储结构详解一、图的定义

图是一种比树更复杂的一种数据结构，在图结构中，结点之间的关系是任意的，任意两个元素之间都可能相关，因此，它的应用极广。图中的数据元素通常被称为顶点(Vertex)(Vertex)(Vertex)，VVV是顶点的有穷非空集合，VRVRVR是两个顶点之间的关系的集合(可以为空)，可以表示为图G={V,{VR}}G=\{V,\{VR\}\}G={V,{VR}}。

二、相关术语

2.1无向图

给定图G={V,{E}}G=\{V,\{E\}\}G={V,{E}}，若该图中每条边都是没有方向的，则称其为无向图(Undigraph)(Undigraph)(Undigraph)。对图GGG中顶点vvv和顶点www的关系，可用无序对(v,w)(v,w)(v,w)表示，它是连接vvv和www的一条边(Edge)(Edge)(Edge)。

2.2有向图

给定图G={V,{A}}G=\{V,\{A\}\}G={V,{A}}，若该图中每条边都是有方向的，则称其为有向图(Digraph)(Digraph)(Digraph)。对图GGG中顶点vvv和顶点www的关系，可用有序对v,wv,wv,w表示，它是从vvv到www的一条弧(Arc)(Arc)(Arc)，其中vvv被称为弧尾(Tail)(Tail)(Tail)，www被称为弧头(Head)(Head)(Head)。

弧尾也叫初始点(Initial(Initial(InitialNode)Node)Node)，弧头也叫终端点(Terminal(Terminal(TerminalNode)Node)Node)。

2.3完全图

对于任一无向图，若其顶点的总数目为nnn，边的总数目为e=n(n1)2e=\frac{n(n-1)}{2}e=2n(n1)，则称其为完全图(Completed(Completed(CompletedGraph)Graph)Graph)。

2.4有向完全图

对于任一有向图，若其顶点的总数目为nnn，边的总数目为e=n(n1)e=n(n-1)e=n(n1)，则称其为有向完全图。

2.5稀疏图和稠密图

对于具有nnn个顶点，eee条边或弧的图来说，若eee很小，比如enlognen\lognenlogn，则称其为稀疏图(Sparse(Sparse(SparseGraph)Graph)Graph)，反之称其为稠密图(Dense(Dense(DenseGraph)Graph)Graph)。

2.6权和网

赋予图中边或弧的数值称为权(Weight)(Weight)(Weight)，它可以表示从一个顶点到另一个顶点的距离；带权的图称为网(Network)(Network)(Network)。

2.7稀疏网和稠密网

带权的稀疏图、稠密图称为稀疏网、稠密网。

2.8子图

对于图G={V,{E}}G=\{V,\{E\}\}G={V,{E}}和图G′={V′,{E′}}G'=\{V',\{E'\}\}G′={V′,{E′}}，若V′VV'\subseteqVV′V且E′EE'\subseteqEE′E，则称G′G'G′为GGG的子图(Subgraph)(Subgraph)(Subgraph)。

2.9邻接点

对于无向图G={V,{E}}G=\{V,\{E\}\}G={V,{E}}，若v∈Vv\inVv∈V、w∈Vw\inVw∈V且(v,w)∈E(v,w)\inE(v,w)∈E，则称顶点vvv和顶点www互为邻接点(Adjacent)(Adjacent)(Adjacent)，并称边(v,w)(v,w)(v,w)依附(Incident)(Incident)(Incident)于顶点vvv和顶点www，或称边(v,w)(v,w)(v,w)与顶点vvv和顶点www相关联。

对于有向图G={V,{A}}G=\{V,\{A\}\}G={V,{A}}，若v∈Vv\inVv∈V、w∈Vw\inVw∈V且v,w∈Av,w\inAv,w∈A，则称顶点vvv邻接到顶点www，顶点www邻接自顶点vvv，并称弧v,wv,wv,w与顶点vvv和顶点www相关联。

2.10度、入度与出度

在无向图中，顶点vvv的度(Degree)(Degree)(Degree)等于与该顶点相关联的边的数目，记为TD(v)TD(v)TD(v)。

在有向图中，顶点vvv的度等于该顶点的入度与出度之和，记为TD(v)=ID(v)+OD(v)TD(v)=ID(v)+OD(v)TD(v)=ID(v)+OD(v)，其中顶点vvv的入度(InDegree)(InDegree)(InDegree)为以该顶点为弧头的弧的数目，记为ID(v)ID(v)ID(v)，顶点vvv的出度(OutDegree)(OutDegree)(OutDegree)为以该顶点为弧尾的弧的数目，记为OD(v)OD(v)OD(v)。

2.11路径、简单路径与路径长度

路径(Path)(Path)(Path)是任意两个有关联的顶点之间的边或弧，在图G={V,{VR}}G=\{V,\{VR\}\}G={V,{VR}}中，顶点v1v_1v1到顶点vnv_nvn的路径是一个顶点序列(v1,v2,…,vi,vj,…,vn)(v_1,v_2,\dots,v_i,v_j,\dots,v_n)(v1,v2,…,vi,vj,…,vn)，对于上述序列中的任意相邻的顶点viv_ivi和vjv_jvj，若图GGG是无向图，则有(v,w)∈E(v,w)\inE(v,w)∈E，若图GGG是有向图，则有v,w∈Av,w\inAv,w∈A。

对于给定的一条路径，若该路径对应的序列中的顶点不重复，则称为该路径为简单路径。

路径上边或弧的数目称为路径长度。

2.12回路与简单回路

若某一路径中的第一个顶点和最后一个顶点相同，则称该路径为回路，也称为环(Cycle)(Cycle)(Cycle)。

在某一回路中，若除去第一个顶点和最后一个顶点外，其余顶点均不重复，则称为该回路为简单回路，也称为简单环。

2.13连通图与连通分量

在无向图中，若从顶点vvv到顶点www有路径，则称为vvv到www是连通的，若该图中的任意两个顶点间都是连通的，则称该图为连通图(Connected(Connected(ConnectedGraph)Graph)Graph)。无向图中的极大连通子图称为连通分量(Connected(Connected(ConnectedComponent)Component)Component)。这里的极大就是尽可能地包含更多的顶点。

2.14强连通图与强连通分量

在有向图中，若从顶点vvv到顶点www有路径，从顶点www到顶点vvv也有路径，则称为vvv和www是强连通的，若该图中的任意两个顶点间都是强连通的，则称该图为强连通图。有向图中的极大连通子图称为强连通分量。

2.15生成树、最小生成树与生成森林

具有nnn个顶点的连通图的极小连通子图称为生成树，生成树包含这一连通图的nnn个顶点和n1n-1n1条边。这里的极小是尽可能少地包含边。

通常把各边带权的连通图称为连通网，在连通网的所有生成树中，对每一棵生成树的各边权值求和，其中权值最小的生成树称为该连通网的最小生成树。

非连通图的各连通分量的生成树组成的森林称为生成森林。

3.图的性质

3.1性质1

若图中有nnn个顶点v1,v2,…,vnv_1,v_2,\dots,v_nv1,v2,…,vn，eee条边或弧，其中顶点的度分别为TD(v1),TD(v2),…,TD(vn)TD(v_1),TD(v_2),\dots,TD(v_n)TD(v1),TD(v2),…,TD(vn)，则有

e=12∑i=1nTD(vi)e=\frac{1}{2}\sum_{i=1}^{n}TD(v_i)e=21i=1∑nTD(vi)

3.2性质2

一棵有nnn个顶点的生成树有且仅有n1n-1n1条边。

4.图的存储结构

4.1邻接矩阵

用于无向图、有向图

在存储含有nnn个结点的图G={V,{VR}}G=\{V,\{VR\}\}G={V,{VR}}时，将图中的所有顶点存储在长度为nnn的一维数组中，将图中边或弧的信息存储在n×nn\timesnn×n的二维数组中，我们称这个二维的数组为邻接矩阵。假设图GGG中顶点vvv和顶点www在一维数组中的下标分别为iii、jjj，则该图对应各邻接矩阵定义如下：

若该图为无向图或有向图，则

Arcs[j][j]={1,(v,w)∈E或v,w∈A0,其他Arcs[j][j]=\begin{cases}1,(v,w)\inE或v,w\inA\\\\0,其他\end{cases}Arcs[j][j]=1,0,(v,w)∈E或v,w∈A其他若该图为无向网或有向网，则

Arcs[j][j]={wij,(v,w)∈E或v,w∈A∞,其他Arcs[j][j]=\begin{cases}w_{ij},(v,w)\inE或v,w\inA\\\\\infty,其他\end{cases}Arcs[j][j]=wij,∞,(v,w)∈E或v,w∈A其他其中，wijw_{ij}wij为边或弧对应的权值。

定义图中的顶点：

classVertexMatrix(object):

图的一个顶点

def__init__(self,data):

self.data=data

=None

定义图：

classGraphMatrix(object):

图的邻接矩阵

def__init__(self,kind):

#图的类型:无向图,有向图,无向网,有向网

#kind:Undigraph,Digraph,Undinetwork,Dinetwork,

self.kind=kind

#顶点表

self.vertexs=[]

#边表,即邻接矩阵,是个二维的

self.arcs=[]

#当前顶点数

self.vexnum=0

#当前边(弧)数

self.arcnum=0

无向图及其邻接矩阵、有向网及其邻接矩阵如下：

Arcs=[0101100100011110]Arcs=[∞12∞∞∞3∞∞∞∞4∞∞∞∞]Arcs=\begin{bmatrix}0101\\1001\\0001\\1110\end{bmatrix}Arcs=\begin{bmatrix}\infty12\infty\\\infty\infty3\infty\\\infty\infty\infty4\\\infty\infty\infty\infty\end{bmatrix}Arcs=0101100100011110Arcs=∞∞∞∞1∞∞∞23∞∞∞∞4∞

邻接矩阵的特点如下：

(1)由于在创建邻接矩阵时，输入顶点的顺序不同，其相应的邻接矩阵也是不同的；

(2)对于含有nnn个顶点的图，其邻接矩阵一定是n×nn\timesnn×n的二维数组；

(3)无向图的邻接矩阵具有对称性，可采用压缩存储的方式存储；

(4)对于无向图，若某一顶点vvv在一维数组中的下标为iii，则该顶点的度为邻接矩阵的第i+1i+1i+1行中值为1的元素的总数目；

(5)对于有向图，若某一顶点vvv在一维数组中的下标为iii，则该顶点的出度为邻接矩阵的第i+1i+1i+1行中值为1的元素的总数目，入度为邻接矩阵的第i+1i+1i+1列中值为1的元素的总数目。

构造一个具有nnn个顶点eee条边的无向网的时间复杂度为O(n2+ne)O(n^2+ne)O(n2+ne)，其中对邻接矩阵的初始化使用了O(n2)O(n^2)O(n2)的时间。

4.2邻接表

用于无向图、有向图

使用邻接表存储图时，将图分为两个部分：

第一部分为图中每一个顶点及与该顶点相关联的第一条边或弧，可以这样定义：

classVertexAdjacencyList(object):

图的一个顶点

def__init__(self,data):

self.data=data

#与该顶点相连的第一条边FirstArc

self.FirstArc=None

使用data域来存储图中的每一个顶点，FirstArc域来存储与该顶点相关联的第一条弧或边，通常情况下指向第二部分单链表的第一个结点。

第二部分为用一个结点来存储图中的每一条边或弧，该结点由adjacent域、info域和NextArc域组成，这些结点形成了单链表。这部分结点可以这样定义：

classArcAdjacencyList(object):

图的一个边(弧)

def__init__(self,adjacent):

#邻接点或弧头,与该顶点相连的另一顶点的index

self.adjacent=adjacent

=None

#与该边(弧)依附于相同顶点的下一条边(弧)NextArc

self.NextArc=None

根据上面图的邻接表可以这样定义：

classGraphAdjacencyList(object):

图的邻接表

def__init__(self,kind):

#图的类型:无向图,有向图,无向网,有向网

#kind:Undigraph,Digraph,Undinetwork,Dinetwork,

self.kind=kind

#邻接表

self.vertices=[]

#当前顶点数

self.vexnum=0

#当前边(弧)数

self.arcnum=0

无向图及其邻接表：

有向网及其邻接表、逆邻接表：

邻接表的特点如下：

(1)由于存储边或弧通过不同的连接顺序会形成不同的单链表，所以图的邻接表不是唯一的；

(2)对于具有eee条边的无向图，使用邻接表存储时需要2e2e2e个结点来存储图的边，而对于具有eee条弧的有向图，使用邻接表存储时需要eee个结点来存储图的弧；

(3)对于具有nnn个顶点eee条边或弧的稀疏图而言，若采用邻接矩阵存储，则需要n2n^2n2个存储空间来存储图的边或弧，而采用邻接表存储时，则至多需要2e2e2e个结点存储图的边或弧，所以稀疏图的存储使用邻接表会更节省空间；

(4)对于无向图，顶点的度等于该顶点对应的单链表中结点的总数目；

(5)对于有向图，若某一顶点在数组中的下标为iii，则该顶点的出度为该顶点对应的单链表中结点的总数目，入度为邻接表中adjacent域内值为iii的结点的总数目。

在使用邻接表存储图时，计算图中的某一顶点的出度很容易，但是在计算其入度时，最坏的情况需要遍历整个邻接表。因此，有时为了方便计算顶点的入度，可以为该图建立一个逆邻接表。

在建立邻接表或逆邻接表时，如输入的顶点信息为顶点的编号，则建立邻接表或逆邻接表的时间复杂度为O(n+e)O(n+e)O(n+e)，否则，需要通过查找才能确定顶点在图中的位置，对应的时间复杂度为O(ne)O(ne)O(ne)。

4.3十字链表

用于有向图

十字链表通常用于有向图，可以将它看成邻接表和逆邻接表的结合。同样分为两个部分，即顶点结点部分和弧部分，通常将顶结点存储在数组中，弧结点存储在单链表中。

顶点结点包含data域、FirstIn域和FirstOut域，其中data域存储顶点的值，FirstIn域指向以当前顶点为弧头的第

一条弧和FirstOut域指向以当前顶点为弧尾的第一条弧。

弧结点包含TailVertex域、HeadVertex域、HeadLink域、TailLink域和info域，其中TailVertex域存储当前弧的弧尾在数组中的下标，HeadVertex域存储当前弧的弧头在数组中的下标，HeadLink域指向与当前弧有相同弧头的下一条弧，TailLink域指向与当前弧有相同弧尾的下一条弧，info域存储当前弧的其他信息。

顶点结点定义如下：

classVertexOrthogonalList(object):

有向图的一个顶点

def__init__(self,data):

self.data=data

#以该顶点为弧头的第一条弧FirstIn

self.FirstIn=None

#以该顶点为弧尾的第一条弧FirstOut

self.FirstOut=None

弧结点定义如下：

classArcOrthogonalList(object):

有向图的一条弧

def__init__(self):

#当前弧中弧头在数组中的下标HeadVertex

self.HeadVertex=None

#当前弧中弧尾在数组中的下标TailVertex

self.TailVertex=None

#与当前弧有相同弧头的下一条弧HeadLink

self.HeadLink=None

#与当前弧有相同弧尾的下一条弧TailLink

self.TailLink=None

=None

十字链表表示的有向图定义如下：

classGraphOrthogonalList(object):

有向图的十字链表

def__init__(self):

#十字链表

self.vertices=[]

#当前顶点数

self.vexnum=0

#当前边(弧)数

self.arcnum=0

有向图及其十字链表：

4.4邻接多重表

用于无向图

在使用邻接表存储无向图时，图的每一条边都对应两个结点，由于这两个结点属于两个不同的邻接表，所以在进行删除操作时需要对邻接表的两条单链表进行操作，比较麻烦，所有引出了邻接多重表。邻接