第六章图 在线性表中,数据元素之间仅有线性关系,除第一个元素 外每个数据元素只有一个直接前趋,除最后一个元素外,每个 数据元素只有一个直接后继.在树形结构中,数据元素之间有 明显的层次关系,每一层上的数据元素可能和下一层中多个元 素相关,但只能和上一层中一个元素相关.而在图形结构中, 任意两个数据元素之间都可能相关,即结点之间的关系可以是 任意的.所以图是一种较线性表和树更为复杂的数据结构,其 应用也极为广泛,如在语言学、逻辑学、物理、化学、电讯工 程、计算机科学及数学的某些分支,均可采用图作为研究和分 析问题的工具.在此主要讨论图的一些基本概念和术语,及图 的存储结构和图的若干操作
第 六 章 图 在线性表中, 数据元素之间仅有线性关系, 除第一个元素 外每个数据元素只有一个直接前趋, 除最后一个元素外, 每个 数据元素只有一个直接后继. 在树形结构中, 数据元素之间有 明显的层次关系, 每一层上的数据元素可能和下一层中多个元 素相关, 但只能和上一层中一个元素相关. 而在图形结构中, 任意两个数据元素之间都可能相关, 即结点之间的关系可以是 任意的. 所以图是一种较线性表和树更为复杂的数据结构, 其 应用也极为广泛, 如在语言学﹑逻辑学﹑物理﹑化学﹑电讯工 程﹑计算机科学及数学的某些分支, 均可采用图作为研究和分 析问题的工具. 在此主要讨论图的一些基本概念和术语, 及图 的存储结构和图的若干操作
6.1基本概念 图是一种数据结构,它的形式化定义为:G=(,E) 其中: V={ E dataobject}E=(n,ym(n,)入(,∈D) 在上面定义中,数据元素ν叫做顶点,V是顶点的非空有限 集合;E是两个顶点之间的关系的集合若∈E,且 ,则表示从到v的一条弧 V叫做弧尾或初始顶点,v叫做弧头或终端顶点.并称顶点 V邻接于顶点v,或称顶点v邻接到顶点v,此时的图称为 有向图,如下面各图均为有向图.对于有向图(a)可表成 ①②WG)=如"2} (④ E(G1) ,<V42V (b)
6 . 1 基本概念 图是一种数据结构, 它的形式化定义为: G = (V,E) 其中: V = v vdataobject , E = vi ,vj p(vi ,vj ) (vi ,vj V) 在上面定义中, 数据元素 v 叫做顶点, V 是顶点的非空有限 集合; E 是两个顶点之间的关系的集合.若 vi ,vj E ,且 vi ,vj vj ,vi , 则 vi ,vj 表示从 i v 到 j v 的一条弧 i v 叫做弧尾或初始顶点, j v 叫做弧头或终端顶点. 并称顶点 j v 邻接于顶点 i v , 或称顶点 i v 邻接到顶点 j v , 此时的图称为 有向图, 如下面各图均为有向图. 1 3 2 4 1 (a)G 1 3 (b) 1 1 2 4 3 4 1 3 对于有向图(a)可表成 V(G1 ) = v1 ,v2 ,v3 ,v4 = 3 4 4 1 1 2 1 3 1 , , , , , , , ( ) v v v v v v v v E G
若∈E必有∈E即E是对称的,则以无序对 (v)代替有序对和,并以(v,)表示v 和v之间的一条边,此时的图叫无向图,如下所示 (b)G2 对于无向图可表成:V(G2)={v,2,2”,ny} E(G)={0n,n)(n,)(2,y)(212(2,2(2, 在无向图中,若边(v2v)∈E,则称顶点v和v互为邻接点, 即V和v相邻接,边(v,V,)依附于顶点和v,或者说(v2v 和顶点v和ν相关联 在图中,顶点数目用n表示,如G的n=4,G2的n=5 用e表示弧或边的数目,如G中弧的数目e=4,G2中边的 数目e=6
若 vi ,vj E 必有 vj ,vi E 即 E 是对称的, 则以无序对 ( , ) i j v v 代替有序对 vi ,vj 和 vj ,vi ,并以 ( , ) i j v v 表示 i v 和 j v 之间的一条边, 此时的图叫无向图, 如下所示. 2 (b)G 1 4 2 5 3 (c) 1 2 5 3 1 4 1 2 5 1 4 3 2 5 对于无向图可表成: V(G2 ) = v1 ,v2 ,v3 ,v4 ,v5 E(G2 ) = (v1 ,v2 ),(v1 ,v4 ),(v2 ,v3 ),(v2 ,v5 ),(v3 ,v4 ),(v3 ,v5 ) 在无向图中, 若边 (vi ,vj )E ,则称顶点 i v 和 j v 互为邻接点, 即 i v 和 j v 相邻接, 边 ( , ) i j v v 依附于顶点 i v 和 j v ,或者说 ( , ) i j v v 和顶点 i v 和 j v 相关联. 在图中, 顶点数目用n表示, 如 G1 的n=4, G2 的n=5. 用e表示弧或边的数目, 如 G1 中弧的数目e=4, G2 中边的 数目e=6
若图中∈E,且v≠ν,说明图中顶点没有到其 自身的弧或边.在下面的讨论中均认为图中顶点没有到其 自身的弧或边.则对于无向图,e的取值范围是0到n(n-1)/2 当e=n(m-1)/2时的无向图叫无向完全图.对于有向图,e的 取值范围是0到n(n-1),当e=n(n-1)时的有向图叫有向完全 图. 对于无向图,顶点v的度是和v相关联的边的数目,记 为TD(v),例如下面无向图中,D(v)=3,对于有向图 以顶点v为头的弧的数目叫v的入度 记为/D(v),对于右边有向图,ⅠD(v)=1 ④③四以顶点V为尾的弧的数目叫的出度 (b)G2(a)G记为OD(v),对于右边有向图OD(v)=2 顶点"的度为D(v)=DD(v)+OD(v,),对于无向图或有向 图,均有 1 STD(Vi 2
若图中 vi ,vj E , 且 i j v v , 说明图中顶点没有到其 自身的弧或边. 在下面的讨论中均认为图中顶点没有到其 自身的弧或边. 则对于无向图,e的取值范围是0到n (n-1)/2 当e= n (n-1)/2时的无向图叫无向完全图. 对于有向图,e的 取值范围是0到n (n-1), 当e= n (n-1)时的有向图叫有向完全 图. 对于无向图,顶点 i v 的度是和 i v 相关联的边的数目,记 为 ( ) i TD v , 例如下面无向图中, 2 (b)G 1 4 2 5 3 TD(v3 ) = 3 ,对于有向图, 1 3 2 4 1 (a)G 以顶点 i v 为头的弧的数目叫 i v 的入度 记为 ( ) i ID v ,对于右边有向图, ID(v1 ) =1 以顶点 i v 为尾的弧的数目叫 i v 的出度 记为 ( ) i OD v ,对于右边有向图, OD(v1 ) = 2 顶点 i v 的度为 ( ) ( ) ( ) i i i TD v = ID v + OD v ,对于无向图或有向 图, 均有 = = n i i e TD v 1 ( ) 2 1
6.2图的存储结构 621邻接矩阵 邻接矩阵是图的一种顺序存储表示,它是利用一个矩 阵来表示图中顶点之间的关系,对于一个具有n个顶点的 图G=(,E)来说,其邻接矩阵是一个n阶方阵,且满足: 1若or(2v是E(G)的弧或边 0若or(v,)不是E(G)中的弧或边 面有向图和无向图的邻接矩阵分别为: V01010 0110 V2|0000 v210101 v0001 v10 V41000 00 G 00
6 . 2 图的存储结构 6.2.1邻接矩阵 邻接矩阵是图的一种顺序存储表示, 它是利用一个矩 阵来表示图中顶点之间的关系, 对于一个具有n个顶点的 图 G = (V,E) 来说,其邻接矩阵是一个n阶方阵, 且满足: = 0 1 A i, j 若 , ( , ) i j i j v v or v v 是 E(G) 的弧或边. 若 , ( , ) i j i j v v or v v 不是 E(G) 中的弧或边. 下面有向图和无向图的邻接矩阵分别为: G2 1 4 2 5 3 1 3 2 4 G1 = 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 A1 1 v 1 v 2 v 2 v 3 v 3 v 4 v 4 v = 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 A2 1 v 1 v 2 v 2 v 3 v 3 v 4 v 4 v 5 v 5 v
由邻接矩阵易于判定任意两个顶点之间是否有边或弧 相连,并容易求得各个顶点的度.对于无向图,顶点v 的度是邻接矩阵中第i行(或第i列)的元素值之和,即 TD(v)=∑少,=∑,d],例如,对于G2及A1 ∑43,小=∑4;3 V01010 0 3 4=01011对于有向图,第/行的元素 n10100值之和为顶点的出度OD(m) 01100第列的元素值之和为顶 点v的入度D(v),例如,对 v10110 于G及A v20000 TD(V=OD(v)+D(v v30001 v4100O 2+1=3
由邻接矩阵易于判定任意两个顶点之间是否有边或弧 相连, 并容易求得各个顶点的度. 对于无向图, 顶点 i v 的度是邻接矩阵中第 i 行(或第 i 列)的元素值之和, 即: = = = = n j n j i TD v A i j A j i 1 1 ( ) , , , 例如,对于 G2 G2 1 4 2 5 3 及 A2 = 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 A2 1 v 1 v 2 v 2 v 3 v 3 v 4 v 4 v 5 v 5 v 3 ( ) 3, ,3 5 1 5 1 3 = = = j= j= T D v A j A j 对于有向图, 第 i 行的元素 值之和为顶点 i v 的出度 ( ) i OD v 第 i 列的元素值之和为顶 点 i v 的入度 ( ) i ID v , 例如,对 于 G1 及 A1 1 3 2 4 G1 = 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 A1 v1 v1 2 v 2 v v3 3 v v4 v4 2 1 3 ( ) ( ) ( ) 1 1 1 = + = TD v = OD v + ID v
622邻接表 邻接表是图的一种链式分配和顺序分配相给合的存储 结构,先以下面的无向图说明邻接表的结构形式 先建立一指针类型向量,以存储m(=5)个表头结 点,向量的下标指示了顶点的序号链表部分 ④a○由n个链表(n为顶点个数,每个顶点对应一个链表 每个链表由一个表头结点和若干个表结点 口区囚 组成,表头结点用来指示第i个顶点 岳所对应的链表表结点由顶点域 和链域组成,顶点域指示了与 四囚 相邻接的顶点的序号,故一个表结 点代表一条依附于的边;链域指示了依附于的另一条 边的表结点,从而第i个链表就表示了依附于顶点v的所 有的边在无向图的邻接表中,顶点v的度即为第i个链 表中的表结点个数(即不包括表头结点)
6.2.2 邻接表 邻接表是图的一种链式分配和顺序分配相给合的存储 结构, 先以下面的无向图说明邻接表的结构形式. G2 1 4 2 5 3 1 2 3 4 5 先建立一指针类型向量, 以存储n(=5)个表头结 点, 向量的下标指示了顶点的序号. 链表部分 由n个链表(n为顶点个数), 每个顶点对应一个链表 • 2 4 每个链表由一个表头结点和若干个表结点 组成, 表头结点用来指示第 i 个顶点 i v 所对应的链表. 表结点由顶点域 和链域组成, 顶点域指示了与 i v 相邻接的顶点的序号, 故一个表结 点代表一条依附于 i v 的边; 链域指示了依附于 i v 的另一条 边的表结点, 从而第 i 个链表就表示了依附于顶点 i v 的所 有的边. • 1 3 5 • 2 4 5 • 1 3 • 2 3 在无向图的邻接表中, 顶点 i v 的度即为第 i 个链 表中的表结点个数(即不包括表头结点)
以下面的有向图说明其邻接表的结构形式.可见其结构 Q②形式与无向图的邻接表是一样的所不同的是 第i个链表表示了从顶点v出发的所有的弧, 因此,第i个链表中的表结点个数(即不包括 测2表头结点是顶点出度,而项点的入 度却需找遍除第个链表外的所有其它 囚 链表,统计出在这些链表中的顶点v的 邻接表 个数即为其的入度.如对于v其出度 为2,其入度为1,故其度为3.显然由 团囚 邻接表确定有向图各个顶点的出度较 4囚 为方便,但确定各个顶点的入度较为 逆邻接表 费事,因此引出逆邻接表.逆邻接表 中第i个链表表示了以顶点为弧头的所有的弧,其 表结点个数(即不包括表头结点)是顶点v的入度
以下面的有向图说明其邻接表的结构形式. 邻接表 1 3 2 4 G1 1 2 3 4 • 2 3 4 • • 1 可见其结构 形式与无向图的邻接表是一样的. 所不同的是 第 i 个链表表示了从顶点 i v 出发的所有的弧, 因此, 第 i 个链表中的表结点个数(即不包括 表头结点)是顶点 i v 出度, 而顶点 i v 的入 度却需找遍除第 i 个链表外的所有其它 链表, 统计出在这些链表中的顶点 i v 的 个数即为其的入度. 如对于 1 v 其出度 为2,其入度为1,故其度为3. 显然由 邻接表确定有向图各个顶点的出度较 为方便, 但确定各个顶点的入度较为 费事, 因此引出逆邻接表. 1 2 3 4 • 4 1 • • 3 • 1 逆邻接表 逆邻接表 中第 i 个链表表示了以顶点 i v 为弧头的所有的弧, 其 表结点个数(即不包括表头结点)是顶点 i v 的入度
6.3图的遍历 从图中某一顶点出发访遍图中其余顶点,且每个顶点 仅被访问一次,这一过程叫图的遍历 由于图中任一顶点都可能和其余的顶点相邻接,故图 的遍历比树的遍历要复杂的多.表现之一,是从某一顶点 出发,沿某条路经搜索后,又回到出发的顶点上,为避免 同一顶点被访问多次,在遍历图的过程中,必须记下每个 已被访问过的顶点.下面介绍两种通常用的遍历图的方法 深度优先搜索法和广度优先搜索法.这两种方法对无向图 和有向图都是适用的 、深度优先搜索法 深度优先搜索遍历图类似于树的前序遍历,其过程是 设初态为图中所有顶点均未被访问过,则从图中某个顶点 V出发,访问此顶点,然后依次从v的未被访问的邻接点
6. 3 图的遍历 从图中某一顶点出发访遍图中其余顶点, 且每个顶点 仅被访问一次, 这一过程叫图的遍历. 由于图中任一顶点都可能和其余的顶点相邻接, 故图 的遍历比树的遍历要复杂的多. 表现之一, 是从某一顶点 出发, 沿某条路经搜索后, 又回到出发的顶点上, 为避免 同一顶点被访问多次, 在遍历图的过程中, 必须记下每个 已被访问过的顶点. 下面介绍两种通常用的遍历图的方法 深度优先搜索法和广度优先搜索法. 这两种方法对无向图 和有向图都是适用的. 一﹑深度优先搜索法 深度优先搜索遍历图类似于树的前序遍历, 其过程是 设初态为图中所有顶点均未被访问过, 则从图中某个顶点 i v 出发, 访问此顶点, 然后依次从 i v 的未被访问的邻接点
出发深度优先遍历图,直到图中所有和有路经相通的顶点 都被访问到;若一次遍历后还有顶点未被访问到,则另选一 个未被访问的顶点作起始点,重复上述过程,直至所有顶点 都被访问到.下面举例说明.选V为初始顶点,则 152:4585155351617 Q由于"2已被访问过,故再任选一未被访 问过的v邻接点,进行深度优先搜索 对图G进行深度优先搜索遍历的结果, 即顶点序列是不唯一的.但从图G的 """"svv",邻接矩阵或邻接表进行深度优先搜索, 100⊥1000则其结果是唯一的例如对左边A阵 v1000010进行深度优先搜索遍历的结果为 A401000001 1512514585553:165 00100010对图G的邻接表进行深度优先搜索的 00100100结果请同学自己完成 vLo0011000
出发深度优先遍历图, 直到图中所有和 vi 有路经相通的顶点 都被访问到; 若一次遍历后还有顶点未被访问到, 则另选一 个未被访问的顶点作起始点, 重复上述过程, 直至所有顶点 G 1 v 2 v 3 v 4 v 5 v 8 v 6 v 7 v 选 1 都被访问到. 下面举例说明. v 为初始顶点, 则 1 v 2 ,v 4 ,v 8 ,v 5 ,v 由于 2 v 已被访问过, 故再任选一未被访 问过的 3 ,v 1 v 邻接点, 进行深度优先搜索 6 ,v 7 ,v 对图 G 进行深度优先搜索遍历的结果, 即顶点序列是不唯一的. 但从图 G 的 邻接矩阵或邻接表进行深度优先搜索, 则其结果是唯一的. 例如对左边A阵 进行深度优先搜索遍历的结果为: = 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 A 1 v 1 v 2 v 2 v 3 v 3 v 4 v 4 v 5 v 5 v 6 v 6 v 7 v 7 v 8 v 8 v 1 v 2 ,v 4 ,v 8 ,v 5 ,v 3 ,v 6 ,v 7 ,v 对图 G 的邻接表进行深度优先搜索的 结果请同学自己完成