图结构是一种比树结构更复杂的非线性结构。在线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继;在树型结构中,数据元素之间有明显的层次关系,并且每一层的数据元素可能和下一层中多个元素相关,但只能和上一层中一个元素相关;而在图型结构中,数据元素之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。

一、图的定义

图(Graph)是由非空的顶点集合和一个描述顶点之间关系(边或者弧)的集合组成。其二元组定义为:

G = (V, E)
V = {vi | vi ∈ dataobject}
E = {(vi, vj) | vi, vj ∈ V ∧ P(vi, vj)}

其中,G 表示一个图,V 是图 G 中顶点的集合,E 是图 G 中边的集合,集合 E 中 P(vi, vj)表示顶点 vi 和顶点 vj 之间有一条直接连线。集合 E 可以是空集。若 E 为空,则该图只有顶点而没有边。偶对(vi, vj)表示一条边。

二、图的相关术语

(一)无向图

在一个图中,如果任意两个顶点构成的偶对 (vi, vj) ∈ E 是无序的,即顶点之间的连线是没有方向的,则称该图为无向图(Undigrpah)。如下图所示,G1是一个无向图。

无向图G1
G1 = (V1, E1);
V1 = {v0, v1, v2, v3, v4}
E1 = {(v0, v1), (v0, v3), (v1, v2), (v2, v3), (v2, v4), (v1, v4)}

无向图

(二)有向图

在一个图中,如果任意两个顶点构成的偶对 <vi, vj> ∈ E 是有序的,即顶点之间的连线是有方向的,则称该图为有向图(Digrpah)。如下图所示,G2是一个有向图。

有向图G2
G2 = (V2, E2)
V2 = {v0, v1, v2, v3}
E2 = {<v0, v1>, <v0, v2>, <v2, v3>, <v3, v0>}

有向图

注意,为了区别起见,无向图的边用圆括号表示,有向图的边(或称为弧)用尖括号表示。显然,在无向图中,(vi, vj) = (vj, vi); 但在有向图中,<vi, vj> ≠ <vj, vi>。

(三)顶点、边、弧、弧头、弧尾

图中的数据元素 vi 称为顶点(Vertex);P(vi, vj) 表示在顶点 vi 和顶点 vj 之间有一条直接连线。

如果是在无向图中,则称这条连线为。边用顶点的无序偶对 (v, w) 表示,称顶点 v 和顶点 w 互为邻接点,边 (v, w) 称为与顶点 v 和 w 相关联。

如果是在有向图中,一般称这条连线为(Arc)。弧用顶点的有序偶对 <vi,vj> 来表示,有序偶对的第一个结点 vi 称为始点(或弧尾Tail),在图中就是不带箭头的一端;有序偶对的第二个结点 vj 称为终点(或弧头 Head),在图中就是带箭头的一端。若 <v,w> 是一条弧,则称顶点 v 邻接到 w,顶点 w 邻接自 v,<v,w> 与顶点 v 和 w 相关联。

(四)无向完全图

在一个无向图中,如果任意两个顶点都有一条直接边相连接,则称该图为无向完全图(Undireted Complete Graph)。

可以证明,在一个含有 n 个顶点的无向完全图中,有n(n-1)/2条边。如下图所示,G3 是一个具有 5 个结点的无向完全图。

无向完全图G3
完全无向图

(五)有向完全图

在一个有向图中,如果任意两个顶点之间都有方向互为相反的两条弧相连接,则称该图为有向完全图(Directed Complete Graph)。

在一个含有 n 个顶点的有向完全图中,有 n(n-1)条边。如下图所示,G4是一个具有 3 个结点的有向完全图。

有向完全图G4:
有向完全图

(六)稠密图、稀疏图

若一个图接近完全图,称为稠密图(Dense Graph);边数很少的图(e << n(n-1)时),则称为稀疏图(Sparse Graph)。

(七)度、入度、出度

顶点的度(Degree)是指依附于某顶点 v 的边数,通常记为 D(v)

在有向图中,要区别顶点的入度与出度的概念。顶点 v 的入度(Indegree)是指以顶点 v 为终点的弧的数目,记为 ID(v);顶点 v 出度(Outdegree)是指以顶点 v 为始点的弧的数目,记为 OD(v)

D(v) = ID(v) + OD(v)

例如,在G1中有:

D(v0) = 2
D(v1) = 3
D(v2) = 3
D(v3) = 2
D(v4) = 2

在G2中有:

ID(v0)=1 OD(v0)=2 D(v0)=3
ID(v1)=1 OD(v1)=0 D(v1)=1
ID(v2)=1 OD(v2)=1 D(v2)=2
ID(v3)=1 OD(v3)=1 D(v3)=2

可以证明,对于具有 n 个顶点、e 条边的图,顶点 vi 的度 D(vi) 与顶点的个数 n 以及边的数目 e 满足关系:
图公式

(八)边的权、网图

有时图的边或弧附带数值信息,这种数值称为权(Weight)。

在实际应用中,权值可以有某种含义。比如,在一个反映城市交通线路的图中,边上的权值可以表示该条线路的长度或者等级;对于一个电子线路图,边上的权值可以表示两个端点之间的电阻、电流或电压值;对于反映工程进度的图而言,边上的权值可以表示从前一个工程到后一个工程所需要的时间;等等。每条边或弧都带权的图称为带权图或网络(Network)。如下图所示,G5就是一个无向网图。如果边是有方向的带权图,就是一个有向网图。

无向网图G5:
无向网图

(九)路径、路径长度

在无向图中,顶点 vp 到顶点 vq 之间的路径(Path)是指顶点序列 vp,vi1,vi2,…,vim,vq。其中,(vp,vi1),(vi1,vi2),…,(vim,vq)分别为图中的边。路径上边的数目称为路径长度(Path Length)。

在有向图中,路径也是有向的,它由若干条弧组成。在无向图 G1 中,v0→v3→v2→v4 与 v0→v1→v4 是从顶点 v0 到顶点 v4 的两条路径,路径长度分别为 3 和 2。

(十)回路、简单路径、简单回路

起点和终点相同的路径称为回路或称为环(Cycle)。

序列中顶点不重复出现的路径称为简单路径。在图G1中,前面提到的 v0 到 v4 的两条路径都为简单路径。

除第一个顶点与最后一个顶点之外,其他顶点不重复出现的回路称为简单回路,如图G2所示的 v0→v2→v3→v0

(十一)子图

对于图 G = (V, E)G' =(V',E'),若存在 V' 是 V 的子集,E' 是 E 的子集,则称图 G' 是 G 的一个子图(Subgraph)。下图给出了 G1 和 G2 的两个子图 G'G''

子图 G'G'':
子图

(十二)连通的、连通图、连通分量

在无向图中,如果从一个顶点 vi 到另一个顶点 vj(i≠j)有路径,则称顶点 vi 和 vj连通的

如果图中任意两个顶点都是连通的,则称该图是连通图(Connected Graph)。

无向图的极大连通子图称为连通分量(Connected Component)。基本特征表现为:顶点数达到极大,如果再增加一个顶点就不再连通。下图(a)中的两个连通分量如(b)所示:

无向图G6与G6的两个连通分量:
无向图及其连通分量

(十三)强连通图、强连通分量

对于有向图来说,若图中任意一对顶点 vi 和 vj(i≠j)均有从一个顶点 vi 到另一个顶点 vj 的路径,也有从 vj 到 vi 的路径,则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。图G2中有两个强连通分量,分别是 {v0,v2,v3} 和 {v1},如下图所示:

有向图G2的两个强连通分量:
强连通分量

(十四)生成树、生成森林

连通图的生成树(Spanning Tree),是一个极小的连通子图,它包含图中全部顶点,且以最少的边数使其连通。

一个具有 n 个顶点的连通图,它的生成树是由 n 个顶点和 n-1 条边组成的连通子图。

如果 G 的一个子图 G' 的边数大于 n-1,则 G' 中必定会产生回路。相反,如果 G' 的边数小于 n-1,则 G' 一定不连通。图 G' 中给出了图 G1的一棵生成树。

在非连通图中,由每个连通分量都可得到一个极小连通子图,即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林(Spanning Forest)。

用户头像
登录后发表评论