第六章图结构 图状结构是一种比树形结构更复杂的非线性 结构,其特点是图中的每一个结点可以有任意 个前驱和任意个后继。通常使用的图状结构有 四种形式:有向图、无向图、有向网络图和无 向网络图。 6.1基本术语 1.图的定义 数据结构B=(KR)称为图是指:K是结点的 有限集合R是结点偶对的有限集合。(习惯上, 将图中的结点又称为顶点结点偶对又称为边) 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 图状结构是一种比树形结构更复杂的非线性 结构，其特点是图中的每一个结点可以有任意 个前驱和任意个后继。通常使用的图状结构有 四种形式：有向图、无向图、有向网络图和无 向网络图。 6.１ 基本术语 １.图的定义 数据结构B=(K,R)称为图是指：K是结点的 有限集合,R是结点偶对的有限集合。(习惯上， 将图中的结点又称为顶点,结点偶对又称为边) 第六章 图结构
2.有向边与有向图 对于一个图,若图中的顶点偶对是有序的, 二则这样的边称为有向边,由有向边构成的图称为 有向图。 例如:G1=vE)中,V={ABCD}组成 E=,, ,, ,) 组成,就构成了一个有向图。其中边用形 式表示,在图示法中用带箭头的线绘出,其逻 武汉理工大学华夏学院-信息工程 辑结构的图形表示如图6-1a)所示
武汉理工大学华夏学院-信息工程 系 对于一个图，若图中的顶点偶对是有序的， 则这样的边称为有向边，由有向边构成的图称为 有向图。 ２.有向边与有向图 例如：G1=(V,E)中，V={A,B,C,D}组成， E={,,,,,} 组成，就构成了一个有向图。其中边用形 式表示，在图示法中用带箭头的线绘出，其逻 辑结构的图形表示如图6-1 (a)所示
A D B D B C C 图61a)有向图 图61b无向图时 图6-1图的逻辑结构示意图 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 图6－１（ｂ）无向图 图6－１图的逻辑结构示意图 A B A D C 图6－１（a）有向图 B D C
3.无向边与无向图 对于一个图,若图中的顶点偶对是无序的, 则这样的边称为无向边,由无向边构成的图称 为无向图。 例如:G2=(V2,E2),V2={ABCD组成, E2=l(A, B),(A,O, B,O,(A, D), (D,C), (D,B) 组成,就构成了一个无向图。其中边用(X,Y) 形式表示,在图示法中用不带箭头的线绘出。 其逻辑结构的图形表示如图6-1(b)所示。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 对于一个图，若图中的顶点偶对是无序的， 则这样的边称为无向边，由无向边构成的图称 为无向图。 例如： G２=(V２,E２)中，V２={A,B,C,D}组成， E２={(A,B),(A,C),(B,C),(A,D),(D,C),(D,B)} 组成，就构成了一个无向图。其中边用（X,Y） 形式表示，在图示法中用不带箭头的线绘出。 其逻辑结构的图形表示如图6-1（ｂ）所示。 ３．无向边与无向图
4.完全图 若在一个有n个顶点的图中,每一个顶点都 与其余的n-1个顶点有边相连,则这种结构的 图称为完全图。显然,有向完全图应有n(n-1)条 →边,无向完全图有n(n-1)/2条边 5.无向图的顶点的度 在无向图中,若(a,b)为图中的一条边 则称a与b是相邻顶点,边(a,b)与顶点a 和b是相关联的。顶点a相关联的边的条数称为 顶点a的度。例如图6-1(b)的无向图中每 一个顶点的度都是3(它是一个无向完全图)。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 若在一个有ｎ个顶点的图中，每一个顶点都 与其余的ｎ－１个顶点有边相连，则这种结构的 图称为完全图。显然，有向完全图应有n(n-1)条 边，无向完全图有ｎ(ｎ－１)/２条边。 ４．完全图 ５．无向图的顶点的度 在无向图中，若(ａ，ｂ)为图中的一条边， 则称ａ与ｂ是相邻顶点，边（ａ，ｂ）与顶点ａ 和ｂ是相关联的。顶点ａ相关联的边的条数称为 顶点ａ的度。例如图6－１（ｂ）的无向图中每 一个顶点的度都是３（它是一个无向完全图）
6.有向图的顶点的出度、入度和度 在有向图中若为图中的一条边则 称顶点a邻接到顶点b,顶点b邻接于顶点a, 边与顶点a和b是相关联的。 邻接于a的顶点个数称为a顶点的出度;邻接 到b的顶点个数称为顶点b的入度;顶点a的出 度与入度之和称为顶点a的度。 简单地说:某个顶点的入度就是进入该顶点的 边的条数前驱数)某个顶点的出度就是离开该 顶点的边的条数(后继数) 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 在有向图中,若为图中的一条边,则 称顶点ａ邻接到顶点ｂ,顶点ｂ邻接于顶点ａ， 边与顶点ａ和ｂ是相关联的。 邻接于ａ的顶点个数称为ａ顶点的出度；邻接 到ｂ的顶点个数称为顶点b的入度；顶点ａ的出 度与入度之和称为顶点ａ的度。 简单地说：某个顶点的入度就是进入该顶点的 边的条数(前驱数）某个顶点的出度就是离开该 顶点的边的条数（后继数） ６．有向图的顶点的出度、入度和度
例如图6-1(a)的有向图中各顶点的出度、入度和度为 顶点 出度 入度 度 BCcD 0 131 332 7.子图 设有两个图G=(vE和G1=(1E1)如果图 G中的所有边E1都包含在图G的边的集合E中,且 图G1中的所有顶点v1都包含在图G的顶点的集合 V中,则称图G1为图G的子图。图6-2中G为一个 图的逻辑结构,而图GLG2为G的子图,显然任何 一个图的子图可以子图可以有多个 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 顶点 出度 入度 度 A 3 1 4 B 2 1 3 C 0 3 3 D 1 1 2 例如图6－１（ａ）的有向图中各顶点的出度、入度和度为： ７．子图 设有两个图G=(V,E) 和G1=(V1 ,E1 ) 如果图 G1中的所有边E1都包含在图G的边的集合E中，且 图G1中的所有顶点V1都包含在图G的顶点的集合 V中，则称图G1为图 G的子图。图6-2中G为一个 图的逻辑结构，而图G1 ,G2为G的子图，显然任何 一个图的子图可以子图可以有多个
A A A D B D 图6-2(c)子图2 D B 图6-2a)无向图G图6-2(b)子图1 图62无向国的部分子图62(0)7图3 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 A D B C A D B 图6－２（ａ）无向图G 图6－２（ｂ）子图１ C 图6－２（ｃ）子图２ 图6－２无向图的部分子图 图6－２（ｄ）子图３ A D C
8.路径与路径长度 对于一个图来说,从图中的某一个顶点x到 任意一个顶点y的路径是一个顶点序列x,x1 X r··· y但对于无向图而言,该序列应满足: (X1X1)应包含在E集合中而对于有向图该 序列应满足: (X1-1,X;)应包含在E集合中。 在路径上的边的条数称为路径长度。路径 上的第一个顶点与最后一个顶点相同时,称为 该图有回路。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 ８．路径与路径长度 对于一个图来说，从图中的某一个顶点ｘ到 任意一个顶点ｙ的路径是一个顶点序列ｘ,ｘ1, ｘ２,….ｙ.但对于无向图而言，该序列应满足: （XI-1 ,XI）应包含在E集合中;而对于有向图,该 序列应满足： （ｘi－1，ｘｊ）应包含在E集合中。 在路径上的边的条数称为路径长度。路径 上的第一个顶点与最后一个顶点相同时，称为 该图有回路
9.连通图与连通分量 在无向图中若顶点x到顶点y有路径,则称 x与y是连通的;图中的任意两个顶点都是 连通的无向图称为连通图。在无向图中的最 大的连通子图称为无向图的连通分量。 如图6-3所示。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 ９．连通图与连通分量 在无向图中若顶点ｘ到顶点ｙ有路径，则称 ｘ与ｙ是连通的；图中的任意两个顶点都是 连通的无向图称为连通图。在无向图中的最 大的连通子图称为无向图的连通分量。 如图6-3 所示