第六章图结构 图状结构是一种比树形结构更复杂的非线性 结构,其特点是图中的每一个结点可以有任意 个前驱和任意个后继。通常使用的图状结构有 四种形式:有向图、无向图、有向网络图和无 向网络图。 6.1基本术语 1.图的定义 数据结构B=(KR)称为图是指:K是结点的 有限集合R是结点偶对的有限集合。(习惯上, 将图中的结点又称为顶点结点偶对又称为边) 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 图状结构是一种比树形结构更复杂的非线性 结构，其特点是图中的每一个结点可以有任意 个前驱和任意个后继。通常使用的图状结构有 四种形式：有向图、无向图、有向网络图和无 向网络图。 6.１ 基本术语 １.图的定义 数据结构B=(K,R)称为图是指：K是结点的 有限集合,R是结点偶对的有限集合。(习惯上， 将图中的结点又称为顶点,结点偶对又称为边) 第六章 图结构
2.有向边与有向图 对于一个图,若图中的顶点偶对是有序的, 二则这样的边称为有向边,由有向边构成的图称为 有向图。 例如:G1=vE)中,V={ABCD}组成 E=<A, B>,<A C>, <C,B>,<B,D>, <A, D>,<D C>) 组成,就构成了一个有向图。其中边用<XY>形 式表示,在图示法中用带箭头的线绘出,其逻 武汉理工大学华夏学院-信息工程 辑结构的图形表示如图6-1a)所示
武汉理工大学华夏学院-信息工程 系 对于一个图，若图中的顶点偶对是有序的， 则这样的边称为有向边，由有向边构成的图称为 有向图。 ２.有向边与有向图 例如：G1=(V,E)中，V={A,B,C,D}组成， E={<A,B>,<A,C>,<C,B>,<B,D>,<A,D>,<D, C>} 组成，就构成了一个有向图。其中边用<X,Y>形 式表示，在图示法中用带箭头的线绘出，其逻 辑结构的图形表示如图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－１（ｂ）的无向图中每 一个顶点的度都是３（它是一个无向完全图）