151-chap6图-17913.pdf

2015-12-9 江西财经大学 软件与通信工程学院 1 6.1 图的定义和基本术语 6.2 图的存储表示 6.3 图的遍历 6.4 图的应用 6.4.1最小生成树 6.4.2两点之间的最短路径问题 6.4.3拓扑排序 2015-12-9 6.4.4关键路径* 江西财经大学 软件与通信工程学院 2 图与其他数据结构的关系 线性结构：唯一前驱，唯一后继，线性关系 树形结构：唯一前驱，多个后继，层次关系 图形结构：多对多、任意，网状关系 图结构中结点（图中通常称为顶点）的前驱和后 继结点个数不再限制，即结点之间的关系是任意 的。 图应用广泛：网络布设，航线管理，交通管理，语 言学等。 图是更复杂的非线性结构。 2015-12-9 江西财经大学 软件与通信工程学院 3 6.1 图的定义和基本术语 有向图（Directed graph ）  Graph = (V , VR ) V是数据元素(顶点)的非空有限集 VR是V 中二元关系弧的集合 VR ＝{v,w| v,w ∈V } v,w表示从 v 到 w 的一条弧，称 v 为弧 尾，w 为弧头。 V W tail head V,W≠W,V 2015-12-9 江西财经大学 软件与通信工程学院 4 例如: 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 } 2015-12-9 江西财经大学 软件与通信工程学院 5 无向图（Undirected graph ）  由顶点集和边集构成的图称作无向图 若v, w ＝w, v ，则称 (v,w) 为顶点v 和顶点 w 之间存在一条边。 例如: G =(V ,VR ) 2 2 2 B C V ={A, B, C, D, E, F} 2 VR2={(A,B), (A,E),