第7章图 数据结构(C++描述)
第7章 图 数据结构（C++描述）
目录 7.1图的基本概念 7.2图的存贮结构 73图的遍历 74生成树和最小生成树 7.5最短路径 7.6拓扑排序 退出
目录 7.6拓扑排序 7.1 图的基本概念 7.2 图的存贮结构 7.3 图的遍历 7.4 生成树和最小生成树 7.5最短路径 退出
71图的基本概念 y711图的定义 图是由顶点集V和顶点间的关系集合E(边的集合)组成 的一种数据结构,可以用二元组定义为:G=(V,E)。 例如,对于图7-1所示的无向图G1和有向图G2,它们的数 据结构可以描述为 =(V1E1),其中 V=a,b, c, d), E(a, b),(a, c),(a, d), (b, d),(c, d)), G,=(V,E,) 其中V2={1,2,3},E2={<1,2>,<13>22,3>,3,1>}。 (a)无向图Gl (b)有向图G2 图7-1无向图和有向图
7.1 图的基本概念 7.1.1 图的定义 图是由顶点集V和顶点间的关系集合E（边的集合）组成 的一种数据结构，可以用二元组定义为：G=（V,E）。 例如，对于图7-1所示的无向图G1和有向图G2，它们的数 据结构可以描述为： G1=(V1 ,E1 ), 其 中 V1={a,b,c,d},E1={(a,b),(a,c),(a,d),(b,d),(c,d)}, 而 G2=(V2 ,E2 ) ， 其中V2={1,2,3}, E2={<1,2>,<1,3>,<2,3>,<3,1>}。 d A A c A a b 1 2 3 (a) 无向图 G1 (b) 有向图 G2 图 7-1 无向图和有向图
飞它…?7.12图的基本术语 有向图和无向图 在图中,若用箭头标明了边是有方向性的,则称这样的 图为有向图,否则称为无向图。如图7-1中,G,为无向图, G,为有向图 在无向图中,一条边(xy)与(yx)表示的结果相同, 入用圆括号表示,在有向图中,一条边父y与x>表示 的结果不相同,故用尖括号表示。〈xy>表示从顶点x发 向顶点y的边,x为始点,y为终点。有向边也称为弧,x 为弧尾,y为弧头,则〈xy>表示为一条弧而《yx表示y 为弧尾,x为弧头的另一条弧。 2.完全图、稠密图、稀疏图 具有n个顶点,n(n-1)2条边的图,称为完全无向图,具有 n个顶点,n(n-1)条弧的有向图,称为完全有向图。完全无 向图和完全有向图都称为完全图
7.1.2 图的基本术语 1. 有向图和无向图 在图中，若用箭头标明了边是有方向性的，则称这样的 图为有向图，否则称为无向图。如图7-1中，G1为无向图， G2为有向图。 在无向图中，一条边（x,y）与（y,x）表示的结果相同， 用圆括号表示，在有向图中，一条边<x,y>与<y,x>表示 的结果不相同，故用尖括号表示。〈x,y>表示从顶点x发 向顶点y的边，x为始点，y为终点。有向边也称为弧，x 为弧尾，y为弧头,则〈x,y>表示为一条弧,而〈y,x>表示y 为弧尾，x为弧头的另一条弧 。 2. 完全图、稠密图、稀疏图 具有n个顶点，n(n-1)/2条边的图，称为完全无向图，具有 n个顶点，n(n-1) 条弧的有向图,称为完全有向图。完全无 向图和完全有向图都称为完全图
它:对于一般无向图,顶点数为n,边数为e,则sesn(n 1)/2 对于一般有向图,顶点数为n,弧数为e,则0≤e≤n(n 当一个图接近完全图时,则称它为稠密图,相反地 当一个图中含有较少的边或弧时,则称它为稀疏图 3.度、入度、出度 在图中,一个顶点依附的边或弧的数目,称为该顶点的 度。在有向图中,一个顶点依附的弧头数目,称为该顶 点的入度。一个顶点依附的弧尾数目,称为该顶点的出 度,某个顶点的入度和出度之和称为该顶点的度。 另外,若图中有n个顶点,e条边或弧,第个顶点的度为d, 则有e=1 ∑
对于一般无向图，顶点数为n，边数为e，则 0≤e ≤n(n- 1)/2。 对于一般有向图，顶点数为n，弧数为e， 则 0≤e≤n(n- 1) 。 当一个图接近完全图时，则称它为稠密图，相反地， 当一个图中含有较少的边或弧时，则称它为稀疏图。 3. 度、入度、出度 在图中，一个顶点依附的边或弧的数目，称为该顶点的 度。在有向图中，一个顶点依附的弧头数目，称为该顶 点的入度。一个顶点依附的弧尾数目，称为该顶点的出 度，某个顶点的入度和出度之和称为该顶点的度。 另外，若图中有n个顶点，e条边或弧，第i个顶点的度为di， 则有e= 2 1 = n i di 1