5图第一部分.pdfVIP

图  图的定义  图的存储结构  图的遍历  最小生成树  最短路径  拓扑排序和关键路径 数据结构 图的定义 图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成， 通常表示为G=(V, E) ，其中，G表示一个图，V是图G 中顶点的 集合，E是图G 中边的集合。  在图中数据元素称之为顶点(Vertex)；  在图结构中，不允许没有顶点；  在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系 用边来表示，边集可以是空的。 A B D C 数据结构 2 数据结构 无向图  无向边 （Edge ） 若顶点v 到v 之间的边没有方向，则称这条边为无向边，用无序偶 i j 对(v , v )来表示。 i j  无向图 （Undirected graphs ） 如果图中任意两个顶点之间的边都是无向边，则称该图为无向图 。 无向图G1 A G1 = ( V1, { E1 } ) V1 = { A, B, C, D } ：顶点集合 B D E1 = { (A, B), (B, C), (C, D), (D, A), (A, C) } C 数据结构 3 数据结构 有向图  有向边/弧 （Arc ） 若从顶点v 到v 的边有方向，则称这条边为有向边，也称为弧，用 i j 有序偶对 v , v 来表示，v 称为弧尾(Tail)，v 称为弧头(Head) 。 i j i j  有向图 （Directed graphs ） 如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。 有向图G2 A G2 = ( V2, { E2 } ) V2 = { A, B, C, D } ：顶点集合 B D E2 = { A, D, B, A, C, A, B, C } C 数据结构 4 数据结构 简单图 在图中，若不存在顶点到其自身的边，且同一条边不重复出现， 则称这样的图为简单图。 A A B D B