课件chap007第七章图.pdf

1. 抽象数据类型图的定义 2. 图的 表示 3. 图的遍历 4. 最小生成树 5. 重 （双）连通图和关节点 6. 两点之间的最短路径问题 7. 拓扑排序 8. 关键路径 图的结构定义: 图是由一个顶点集V 和一个弧集 R构成 的数据结构。 Graph = (V , R ) 其中 ，VR ＝{v,w| v,w ∈V 且 P(v,w)} v,w表示从 v 到 w 的一条弧，并称 w 为 弧头，v 为弧尾。 谓词 P(v,w) 定义了弧 v,w的意义或信息。 由于 “弧”是有方向的 ，因此称由顶点集 和弧集构成的图为有向图。 例如: G = (V , VR ) 1 1 1 其中 A V ={A, B, C, D, E} 1 B E VR ={A,B, A,E, 1 B,C, C,D, D,B, C D D,A, E,C } 若v, w VR 必有w, v VR, 由顶点集和边 则称 (v,w) 为顶点v 和顶点 w 集构成的图称 之间存在一条边。 作无向图。 例如: G =(V ,VR ) 2 2 2 V ={A, B, C, D, E, F} B C 2 VR ={(A,B), (A,E), 2 (B,E), (C,D), (D,F), A D (B,F), (C,F) } F E 名词和术语 网、子图 完全图、稀疏图、稠密图 邻接点、度、入度、出度 路径、路径长度、简单路径、简单回路 连通图、连通分量、 强连通图、强连通分量 生成树、生成森林 15 A 9 弧或边带权的图 11 B 7 21 E 分别称作有向网或 3 无向网。 C 2 F B 设图G=(V,{VR}) 和 A 图 G=(V,{VR}), B 且 VV, VRVR, E 则称 G