图的特性
图(Graph)是一种比线性表和树更为复杂的数据结构。 线性结构:是研究数据元素之间的一对一关系。在这种结构中,除第一个和最后一个元素外,任何一个元素都有唯一的一个直接前驱和直接后继。 树结构:是研究数据元素之间的一对多的关系。在这种结构中,每个元素对下(层)可以有0个或多个元素相联系,对上(层)只有唯一的一个元素相关,数据元素之间有明显的层次关系。 图结构:是研究数据元素之间的多对多的关系。在这种结构中,任意两个元素之间可能存在关系。即结点之间的关系可以是任意的,图中任意元素之间都可能相关。 图的应用极为广泛,已渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。
图的基本概念
图、顶点、弧
一个图(G)
定义为一个偶对(V,E)
,记为G=(V,E)
。其中: V
是顶点(Vertex)的非空有限集合,记为V(G)
;E
是无序集V&V
的一个子集,记为E(G)
,其元素是图的弧(Arc)。
将顶点集合为空的图称为空图。其形式化定义为:
G=(V ,E)
V={v|vdata object}
E={<v,w>| v,wV∧p(v,w)}
P(v,w)
表示从顶点v
到顶点w
有一条直接通路。
弧(Arc) :表示两个顶点v
和w
之间存在一个关系,用顶点偶对<v,w>
表示。通常根据图的顶点偶对将图分为有向图和无向图。
有向图、无向图
有向图(Digraph): 若图G
的关系集合E(G)
中,顶点偶对<v,w>
的v
和w
之间是有序的,称图G
是有向图。
在有向图中,若 <v,w>
E(G)
,表示从顶点v
到顶点w
有一条弧。 其中:v
称为弧尾(tail)或始点(initial node),w
称为弧头(head)或终点(terminal node)。
无向图(Undigraph): 若图G
的关系集合E(G)
中,顶点偶对<v,w>
的v
和w
之间是无序的,称图G
是无向图。
在无向图中,若<v,w>属于E(G)
,有<w,v>属于E(G)
,即E(G)
是对称,则用无序对(v,w)
表示v
和w
之间的一条边(Edge),因此(v,w)
和(w,v)
代表的是同一条边。
完全有向图、完全无向图
完全无向图:对于无向图,若图中顶点数为n
,用e
表示边的数目,则e属于[0,n(n-1)/2]
。具有n(n-1)/2
条边的无向图称为完全无向图。
完全无向图另外的定义是:
对于无向图G=(V,E)
,若任意的vi,vj属于V
,当vi≠vj
时,有(vi ,vj)属于E
,即图中任意两个不同的顶点间都有一条无向边,这样的无向图称为完全无向图。
完全有向图:对于有向图,若图中顶点数为n
,用e
表示弧的数目,则e属于[0,n(n-1)]
。具有n(n-1)
条边的有向图称为完全有向图。
完全有向图另外的定义是:
对于有向图G=(V,E)
,若任意的vi,vj属于V
,当vi ≠vj
时,有<vi ,vj>属于E∧<vj , vi >属于E
,即图中任意两个不同的顶点间都有一条弧,这样的有向图称为完全有向图。
稀疏图、稠密图
有很少边或弧的图(e<n㏒n
)的图称为稀疏图,反之称为稠密图。
权
权(Weight):与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。
子图、生成子图
子图和生成子图:设有图G=(V,E)
和G’=(V’,E’)
,若V’含于V
且E’含于E
,则称图G’
是G
的子图;若V’=V
且E’含于E
,则称图G’
是G
的一个生成子图。
顶点的邻接(Adjacent):对于无向图G=(V,E)
,若边(v,w)属于E
,则称顶点v
和w
互为邻接点,即v
和w
相邻接。边(v,w)
依附(incident)于顶点v
和w
。
对于有向图G=(V ,E)
,若有向弧<v,w>属于E
,则称顶点v
“邻接到”顶点w
,顶点w
“邻接自”顶点v
,弧<v,w>
与顶点v
和w
“相关联” 。
顶点的度、入度、出度
对于无向图G=(V,E)
,任意的vi属于V
,图G
中依附于vi
的边的数目称为顶点vi
的度(degree),记为TD(vi)
。
显然,在无向图中,所有顶点度的和是图中边的2
倍。 即 ∑TD(vi)=2e i=1, 2, …, n
,e
为图的边数。
对有向图G=(V,E)
,若任意的vi属于V
,图G
中以vi
作为起点的有向边(弧)的数目称为顶点vi
的出度(Outdegree),记为OD(vi)
;以vi
作为终点的有向边(弧)的数目称为顶点vi
的入度(Indegree),记为ID(vi)
。顶点vi
的出度与入度之和称为vi
的度,记为TD(vi)
。即TD(vi)=OD(vi)+ID(vi)
路径(Path)、路径长度、回路(Cycle)
对无向图G=(V,E)
,若从顶点vi
经过若干条边能到达vj
,称顶点vi
和vj
是连通的,又称顶点vi
到vj
有路径。
对有向图G=(V,E)
,从顶点vi
到vj
有有向路径,指的是从顶点vi
经过若干条有向边(弧)能到达vj
。
或路径是图G
中连接两顶点之间所经过的顶点序列。即
Path=vi0vi1…vim ,vij属于V且(vij-1, vij)属于E j=1,2, …,m
或
Path=vi0vi1 …vim ,vij属于V且<vij-1, vij>属于E j=1,2, …,m
路径上边或有向边(弧)的数目称为该路径的长度。
在一条路径中,若没有重复相同的顶点,该路径称为简单路径;
第一个顶点和最后一个顶点相同的路径称为回路(环);
在一个回路中,若除第一个与最后一个顶点外,其余顶点不重复出现的回路称为简单回路(简单环)。
连通图、图的连通分量
对无向图G=(V,E)
,若任意的vi ,vj属于V
,vi
和vj
都是连通的,则称图G
是连通图,否则称为非连通图。若G
是非连通图,则极大的连通子图称为G
的连通分量。
对有向图G=(V,E)
,若任意的vi ,vj属于V
,都有以vi
为起点, vj
为终点以及以vj
为起点,vi
为终点的有向路径,称图G
是强连通图,否则称为非强连通图。若G
是非强连通图,则极大的强连通子图称为G的强连通分量。
“极大”的含义:指的是对子图再增加图G
中的其它顶点,子图就不再连通。
生成树、生成森林
一个连通图(无向图)的生成树是一个极小连通子图,它含有图中全部n
个顶点和只有足以构成一棵树的n-1
条边,称为图的生成树。
关于无向图的生成树的几个结论:
- 一棵有
n
个顶点的生成树有且仅有n-1
条边; - 如果一个图有
n
个顶点和小于n-1
条边,则是非连通图; - 如果多于
n-1
条边,则一定有环; - 有
n-1
条边的图不一定是生成树。
有向图的生成森林是这样一个子图,由若干棵有向树组成,含有图中全部顶点。
有向树是只有一个顶点的入度为0
,其余顶点的入度均为1
的有向图,
网
每个边(或弧)都附加一个权值的图,称为带权图。带权的连通图(包括弱连通的有向图)称为网或网络。网络是工程上常用的一个概念,用来表示一个工程或某种流程。
图的存储结构
图的存储结构比较复杂,其复杂性主要表现在:
- 任意顶点之间可能存在联系,无法以数据元素在存储区中的物理位置来表示元素之间的关系。
- 图中顶点的度不一样,有的可能相差很大,若按度数最大的顶点设计结构,则会浪费很多存储单元,反之按每个顶点自己的度设计不同的结构,又会影响操作。
图的常用的存储结构有:邻接矩阵、邻接链表、十字链表、邻接多重表和边表。
邻接矩阵(数组)表示法
基本思想:对于有n
个顶点的图,用一维数组vexs[n]
存储顶点信息,用二维数组A[n][n]
存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中,以顶点在vexs
数组中的下标代表顶点,邻接矩阵中的元素A[i][j]
存放的是顶点i
到顶点j
之间关系的信息。
无向图的邻接矩阵(数组)表示
无权图的邻接矩阵
无向无权图G=(V,E)
有n(n≧1)
个顶点,其邻接矩阵是n
阶对称方阵,其元素的定义如下:
带权图的邻接矩阵
其元素的定义如下:
无向图邻接矩阵的特性
如下:
- 邻接矩阵是对称方阵;
- 对于顶点
vi
,其度数是第i
行的非0
元素的个数; - 无向图的边数是上(或下)三角形矩阵中非
0
元素个数。
有向图的数组表示
无权图的邻接矩阵
若有向无权图G=(V,E)
有n(n≧1)
个顶点,则其邻接矩阵是n
阶对称方阵,元素定义如下:
带权图的邻接矩阵
有向带权图G=(V,E)
的邻接矩阵其元素的定义如下:
有向图邻接矩阵的特性
如下:
- 对于顶点
vi
,第i
行的非0
元素的个数是其出度OD(vi)
;第i
列的非0
元素的个数是其入度ID(vi)
。 - 邻接矩阵中非
0
元素的个数就是图的弧的数目。
图的邻接矩阵的存储结构
图的邻接矩阵的实现比较容易,定义两个数组分别存储顶点信息(数据元素)和边或弧的信息(数据元素之间的关系) 。其存储结构形式定义如下:
#define INFINITY MAX_VAL /* 最大值∞ */
/* 根据图的权值类型,分别定义为最大整数或实数 */
#define MAX_VEX 30 /* 最大顶点数目 */
typedef enum {DG, AG, WDG,WAG} GraphKind ;
/* {有向图,无向图,带权有向图,带权无向图} */
typedef struct ArcType
{ VexType vex1, vex2 ; /* 弧或边所依附的两个顶点 */
ArcValType ArcVal ; /* 弧或边的权值 */
ArcInfoType ArcInfo ; /* 弧或边的其它信息 */
} ArcType ; /* 弧或边的结构定义 */
typedef struct
{ GraphKind kind ; /* 图的种类标志 */
int vexnum , arcnum ; /* 图的当前顶点数和弧数 */
VexType vexs[MAX_VEX] ; /* 顶点向量 */
AdjType adj[MAX_VEX][MAX_VEX];
} MGraph ; /* 图的结构定义 */
利用上述定义的数据结构,可以方便地实现图的各种操作。
邻接链表法
基本思想:对图的每个顶点建立一个单链表,存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。
第i
个单链表表示依附于顶点Vi
的边(对有向图是以顶点Vi
为头或尾的弧)。
邻接链表的存储结构
链表中的结点称为表结点,每个结点由三个域组成,其中邻接点域(adjvex
)指示与顶点Vi
邻接的顶点在图中的位置(顶点编号),链域(nextarc
)指向下一个与顶点Vi
邻接的表结点,数据域(info
)存储和边或弧相关的信息,如权值等。对于无权图,如果没有与边相关的其他信息,可省略此域。
每个链表设一个表头结点(称为顶点结点),由两个域组成,链域(firstarc
)指向链表中的第一个结点,数据域(data
) 存储顶点名或其他信息。
在图的邻接链表表示中,所有顶点结点用一个向量 以顺序结构形式存储,可以随机访问任意顶点的链表,该向量称为表头向量,向量的下标指示顶点的序号。 用邻接链表存储图时,对无向图,其邻接链表是唯一的,对有向图,其邻接链表有两种形式:正邻接链表(出度直观);逆邻接链表(入度直观)。
#define MAX_VEX 30 /* 最大顶点数 */
typedef int InfoType;
typedef enum { DG, AG, WDG,WAG } GraphKind ;
typedef struct LinkNode
{ int adjvex ; // 邻接点在头结点数组中的位置(下标)
InfoType info ; // 与边或弧相关的信息, 如权值
struct LinkNode *nextarc ; // 指向下一个表结点
} LinkNode ; /* 表结点类型定义 */
typedef struct VexNode
{ VexType data; // 顶点信息
int indegree ; // 顶点的度, 有向图是入度或出度或没有
LinkNode *firstarc ; // 指向第一个表结点
} VexNode ; /* 顶点结点类型定义 */
typedef struct ArcType
{ VexType vex1, vex2 ; /* 弧或边所依附的两个顶点 */
InfoType info ; // 与边或弧相关的信息, 如权值
} ArcType ; /* 弧或边的结构定义 */
typedef struct
{ GraphKind kind ; /* 图的种类标志 */
int vexnum ;
VexNode AdjList[MAX_VEX] ;
} ALGraph ; /* 图的结构定义 */
利用上述的存储结构描述,可方便地实现图的基本操作。
邻接表法的特点
- 表头向量中每个分量就是一个单链表的头结点,分量个数就是图中的顶点数目;
- 在边或弧稀疏的条件下,用邻接表表示比用邻接矩阵表示节省存储空间;
- 在无向图,顶点
Vi
的度是第i
个链表的结点数; - 对有向图可以建立正邻接表或逆邻接表。正邻接表是以顶点
Vi
为出度(即为弧的起点)而建立的邻接表;逆邻接表是以顶点Vi
为入度(即为弧的终点)而建立的邻接表; - 在有向图中,第
i
个链表中的结点数是顶点Vi
的出 (或入)度;求入 (或出)度,须遍历整个邻接表; - 在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点;
十字链表法
十字链表(Orthogonal List)是有向图的另一种链式存储结构,是将有向图的正邻接表和逆邻接表结合起来得到的一种链表。
十字链表的存储结构
在这种结构中,每条弧的弧头结点和弧尾结点都存放在链表中,并将弧结点分别组织到以弧尾结点为头(顶点)结点和以弧头结点为头(顶点)结点的链表中。 每个域的作用如下:
data
域:存储和顶点相关的信息;- 指针域
firstin
:指向以该顶点为弧头的第一条弧所对应的弧结点; - 指针域
firstout
:指向以该顶点为弧尾的第一条弧所对应的弧结点; - 尾域
tailvex
:指示弧尾顶点在图中的位置; - 头域
headvex
:指示弧头顶点在图中的位置; - 指针域
hlink
:指向弧头相同的下一条弧; - 指针域
tlink
:指向弧尾相同的下一条弧; Info
域:指向该弧的相关信息;
#define INFINITY MAX_VAL /* 最大值∞ */
#define MAX_VEX 30 // 最大顶点数
typedef struct ArcNode
{ int tailvex , headvex ; // 尾结点和头结点在图中的位置
InfoType info ; // 与弧相关的信息, 如权值
struct ArcNode *hlink , *tlink ;
} ArcNode ; /* 弧结点类型定义 */
typedef struct VexNode
{ VexType data; // 顶点信息
ArcNode *firstin , *firstout ;
} VexNode ; /* 顶点结点类型定义 */
typedef struct
{ int vexnum ;
VexNode xlist[MAX_VEX] ;
} OLGraph ; /* 图的类型定义 */
十字链表法的特点
从这种存储结构图可以看出,从一个顶点结点的firstout
出发,沿表结点的tlink
指针构成了正邻接表的链表结构,而从一个顶点结点的firstin
出发,沿表结点的hlink
指针构成了逆邻接表的链表结构。
邻接多重表
邻接多重表(Adjacency Multilist)是无向图的另一种链式存储结构。
邻接表是无向图的一种有效的存储结构,在无向图的邻接表中,一条边(v,w)
的两个表结点分别初选在以v
和w
为头结点的链表中,很容易求得顶点和边的信息,但在涉及到边的操作会带来不便。
邻接多重表的存储结构
邻接多重表的结构和十字链表类似,每条边用一个结点表示;邻接多重表中的顶点结点结构与邻接表中的完全相同,而表结点包括六个域:
Data
域:存储和顶点相关的信息;- 指针域
firstedge
:指向依附于该顶点的第一条边所对应的表结点; - 标志域
mark
:用以标识该条边是否被访问过; ivex
和jvex
域:分别保存该边所依附的两个顶点在图中的位置;info
域:保存该边的相关信息;- 指针域
ilink
:指向下一条依附于顶点ivex
的边; - 指针域
jlink
:指向下一条依附于顶点jvex
的边;
#define INFINITY MAX_VAL /* 最大值∞ */
#define MAX_VEX 30 /* 最大顶点数 */
typedef emnu { unvisited , visited } Visitting ;
typedef struct EdgeNode
{ Visitting mark ; // 访问标记
int ivex , jvex ; // 该边依附的两个结点在图中的位置
InfoType info ; // 与边相关的信息, 如权值
struct EdgeNode *ilink , *jlink ;
// 分别指向依附于这两个顶点的下一条边
} EdgeNode ; /* 弧边结点类型定义 */
typedef struct VexNode
{ VexType data; // 顶点信息
ArcNode *firsedge ; // 指向依附于该顶点的第一条边
} VexNode ; /* 顶点结点类型定义 */
typedef struct
{ int vexnum ;
VexNode mullist[MAX_VEX] ;
} AMGraph ;
邻接多重表与邻接表的区别
邻接表的同一条边用两个表结点表示,而邻接多重表只用一个表结点表示;除标志域外,邻接多重表与邻接表表达的信息是相同的,因此,操作的实现也基本相似。
图的边表
在某些应用中,有时主要考察图中各个边的权值以及所依附的两个顶点,即图的结构主要由边来表示,称为边表存储结构。
图的边表的存储结构
在边表结构中,边采用顺序存储,每个边元素由三部分组成:边所依附的两个顶点和边的权值;图的顶点用另一个顺序结构的顶点表存储。
#define INFINITY MAX_VAL /* 最大值∞ */
#define MAX_VEX 30 /* 最大顶点数 */
#define MAX_EDGE 100 /* 最大边数 */
typedef struct ENode
{ int ivex , jvex ; /* 边所依附的两个顶点 */
WeightType weight ; /* 边的权值 */
} ENode ; /* 边表元素类型定义 */
typedef struct
{ int vexnum , edgenum ; /* 顶点数和边数 */
VexType vexlist[MAX_VEX] ; /* 顶点表 */
ENode edgelist[MAX_EDGE] ; /* 边表 */
} ELGraph ;
总结
图的存储结构依据图具体的应用会有不同的表现形式,有时候在一个问题的解决方案中需要用到的不止一种存储结构,熟练掌握图的数据结构是有效实现图算法的基础。
总结自:《数据结构(C语言版)》 清华大学出版社 严蔚敏、吴伟民编著