第六章图 在线性表中,数据元素之间仅有线性关系,除第一个元素 外每个数据元素只有一个直接前趋,除最后一个元素外,每个 数据元素只有一个直接后继.在树形结构中,数据元素之间有 明显的层次关系,每一层上的数据元素可能和下一层中多个元 素相关,但只能和上一层中一个元素相关.而在图形结构中, 任意两个数据元素之间都可能相关,即结点之间的关系可以是 任意的.所以图是一种较线性表和树更为复杂的数据结构,其 应用也极为广泛,如在语言学、逻辑学、物理、化学、电讯工 程、计算机科学及数学的某些分支,均可采用图作为研究和分 析问题的工具.在此主要讨论图的一些基本概念和术语,及图 的存储结构和图的若干操作
第 六 章 图 在线性表中, 数据元素之间仅有线性关系, 除第一个元素 外每个数据元素只有一个直接前趋, 除最后一个元素外, 每个 数据元素只有一个直接后继. 在树形结构中, 数据元素之间有 明显的层次关系, 每一层上的数据元素可能和下一层中多个元 素相关, 但只能和上一层中一个元素相关. 而在图形结构中, 任意两个数据元素之间都可能相关, 即结点之间的关系可以是 任意的. 所以图是一种较线性表和树更为复杂的数据结构, 其 应用也极为广泛, 如在语言学﹑逻辑学﹑物理﹑化学﹑电讯工 程﹑计算机科学及数学的某些分支, 均可采用图作为研究和分 析问题的工具. 在此主要讨论图的一些基本概念和术语, 及图 的存储结构和图的若干操作
6.1基本概念 图是一种数据结构,它的形式化定义为:G=(,E) 其中: V={ E dataobject}E=(n,ym(n,)入(,∈D) 在上面定义中,数据元素ν叫做顶点,V是顶点的非空有限 集合;E是两个顶点之间的关系的集合若<v2v>∈E,且 <,><vV>,则<V,V>表示从到v的一条弧 V叫做弧尾或初始顶点,v叫做弧头或终端顶点.并称顶点 V邻接于顶点v,或称顶点v邻接到顶点v,此时的图称为 有向图,如下面各图均为有向图.对于有向图(a)可表成 ①②WG)=如"2} (④ <V,V,><V1,V3> E(G1) <v32V4>,<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
若<v,V>∈E必有<v,>∈E即E是对称的,则以无序对 (v)代替有序对<v,v>和<v,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
若图中<vv>∈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若<V>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