North China Electric Power University I 第六章图 ★基本术语 ★图的存储结构 ★图的遍历 ★最小生成树和最短路径问题 ★A0V网与拓扑排序 ★AOE网与关键路径
第六章 图 ★ 基本术语 ★ 图的存储结构 ★ 图的遍历 North China Electric Power University ★ 最小生成树和最短路径问题 ★ AOV网与拓扑排序 ★ AOE网与关键路径
North China Electric Power University I ★基本术语 图的定义 图是由顶点的非空有穷集合与顶点之间关系 (边或弧)的集合构成的结构,通常表示为 G=(V,E) 其中,V为顶点集合,E为关系(边或弧)的集合 华电计算机系
★基本术语 North China Electric Power University 图是由顶点的非空有穷集合与顶点之间关系 (边或弧)的集合构成的结构, 通常表示为 G = ( V, E) 其中, V 为顶点集合, E 为关系(边或弧)的集合. 一 .图的定义 华电计算机系
North China Electric Power University I 关于一条边或弧的表示方法 (1).用图形: )③③ (2).用符号: (3)用语言: (a).顶点v;与v;是这条边的两个邻接点 b).这条边依附于顶点v和v 华电计算机系
North China Electric Power University (b). 这条边依附于顶点vi 和vj。 (vi , vj ) vi vj vi vj vj vi vj vi 关于一条边或弧的表示方法: (a). 顶点vi 与vj 是这条边的两个邻接点。 (1). 用图形: (2). 用符号: (3). 用语言: 华电计算机系
North China Electric Power University I G1=(V1,E1) G2=(V2E2) 其中 其中 3v4 2 V 1V2,V3,V4 E1={(v1,v2),(v1,v3), 2={<v1,V2>, (v1,4),(V2,v3) v2,v3>,<4,v3> V3.V 华电计算机系
North China Electric Power University 华电计算机系 v1 v2 v3 v4 其中 V1 = { v1, v2, v3, v4 } E1 = { (v1,v2), (v1,v3), (v1,v4), (v2,v3), (v2,v4), (v3,v4) } G1=(V1 , E1 ) v1 v2 v3 v4 其中 V2 = { v1, v2, v3, v4 } E2 = { <v1,v2>, <v2,v1>, <v2,v3>, <v4,v3> } G2=(V2 , E2 )
North China Electric Power University I 图的分类 无向图:对手(vW)EE必有(yWE,并且偶对中顶 点的前后顺序无关。 有向图:若<vy∈E是顶点的有序偶对。 网络):与边有关的数据称为权边上带权的图称为网络。 10 华电计算机系
North China Electric Power University 无向图： 有向图： 与边有关的数据称为权,边上带权的图称为网络。 二.图的分类 对于（vi ,vj)E,必有（vj ,vi )E，并且偶对中顶 点的前后顺序无关。 若<vi ,vj>E是顶点的有序偶对。 华电计算机系 网(络)： v1 v2 v3 v4 v1 v2 v3 v4 v1 v2 v3 v4 10 4 17 8