数据结构-图课件.pdf

第七章 图 7.1 基本概念和术语 7.2 图的存储结构 7.3 图的遍历 图的应用 7.4 最小代价生成树 7.5 拓扑排序、关键路径 7.6 最短路径 1 图（Graph ）是一种较线性表和树更为复杂的数据结构。 q线性表: 数据元素之间构成线性关系，每个数据元素只 有一个直接前驱和一个直接后继。 q树: 数据元素之间具有层次关系 ，每一层上的元素可能 和下层多个元素相关，但只能和上层中一个元素相关。 qq ：：图结构中图结构中，，结点之间的关系可以结点之间的关系可以是是任意的任意的 ，，任意任意 两个数据元素之间都可能相关。 q图的应用广泛: 电路网络分析、交通运输、管理与线路的铺设 印刷电路板与集成电路的布线、社会网络、WEB链接图 工程进度的安排、课程表的制订、关系数据库的设计 2 7.1 图的定义和术语 一、图的结构定义: q 是 一个顶点集V 和一个顶点间的关系集合弧集VR （边的集合）构成的数据结构。 可以用二元组定义为： Graph = (V, VR ) 其中，VR ＝{v,w| v,w∈V 且 P(v,w)} 谓词谓词 PP((vv,,ww)) 定义定义了弧了弧vv,,ww的意义的意义或信息或信息。。 q顶点:图中的数据元素称为顶点(Vertex), V是顶点的有穷非空集合; VR是两个顶点之间的关系的集合。 q若v,w∈VR,则v,w 表示从v到w的一条弧 （Arc). 且称v为弧尾(Tail)或为初始点(Initial node) ， 称w为弧头(Head)或为终端点（Terminal node). 3 由于“弧”是有方向的，因此称由顶点集和弧集构成 的图为有向图。弧用尖括号表示。 G = (V , VR ) 1 1 1 A EE BB C D 其中： V ={A, B, C, D, E} 1 VR ={A,B, A,E,B,C, C,D,D,B,D,A, E,C} 1 4 若v,w ∈VR必有w,v ∈VR,则以(v,w) 代替 ，表示两顶点之间有边 （边的顶点对是无序的） 。 此时的图为无向图 （Undigraph)。 例：无向图G2 A B EE C D 其中： V2={A, B, C, D, E} VR2={ （A,B ）, （A,C),(E,C), (E,D),(D,B) } 5 有向图、无向图示例 1 2 A B 3 4 D 5 6 C