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