《《数据结构（C++描述）》-李根强-电子教案 第7章》由会员分享，可在线阅读，更多相关《《数据结构（C++描述）》-李根强-电子教案 第7章（77页珍藏版）》请在金锄头文库上搜索。
1、第7章 图,数据结构（C+描述）,目录,7.6拓扑排序,7.1 图的基本概念,7.2 图的存贮结构,7.3 图的遍历,7.4 生成树和最小生成树,7.5最短路径,退出,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=,。,7.1.2 图的基本术语,1.
2、有向图和无向图,在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。如图7-1中，G1为无向图，G2为有向图。 在无向图中，一条边（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) 条弧的有向图,称为完全有向图。完全无向图和完全有向图都称为完全图。,
3、对于一般无向图，顶点数为n，边数为e，则 0e n(n-1)/2。 对于一般有向图，顶点数为n，弧数为e， 则 0en(n-1) 。 当一个图接近完全图时，则称它为稠密图，相反地，当一个图中含有较少的边或弧时，则称它为稀疏图。,3. 度、入度、出度,在图中，一个顶点依附的边或弧的数目，称为该顶点的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。,另外，若图中有n个顶点，e条边或弧，第i个顶点的度为di，则有e=,4. 子图,若有两个图G1和G2， G1=(V1,E1)， G2=(V2,E2)， 满足如下
4、条件： V2V1 ，E2 E1，即V2为V1的子集，E2为E1的子集，称图G2为图G1的子图。,图和子图的示例具体见图7-2。,5 权,在图的边或弧中给出相关的数，称为权。 权可以代表一个顶点到另一个顶点的距离，耗费等，带权图一般称为网。,带权图的示例具体见图7-3。,6 连通图和强连通图,在无向图中，若从顶点i到顶点j有路径，则称顶点i和顶点j是连通的。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图。,连通图和非连通图示例见图7-4。,在有向图中，若从顶点i到顶点j有路径，则称从顶点i和顶点j是连通的，若图中任意两个顶点都是连通的，则称此有向图为强连通图，否则称为非强连通图
5、。,强连通图和非强连通图示例见图7-5。,7 连通分量和强连通分量,无向图中，极大的连通子图为该图的连通分量。显然，任何连通图的连通分量只有一个，即它本身，而非连通图有多个连通分量。,对于图7-4 中的非连通图，它的连通分量见图7-6。,有向图中，极大的强连通子图为该 图的强连通分量。显然，任何强连通图的强连通分量只有一个，即它本身，而非强连通图有多个强连通分量。,对于图7-5 中的非强连通图，它的强连通分量见图7-7。,8路径、回路,在无向图G中，若存在一个顶点序列Vp ,Vi1，Vi2，Vin，Vq, 使得（Vp,Vi1）,(Vi1,Vi2),，(Vin,Vq)均属于E（G），则称顶点Vp
6、到Vq存在一条路径。若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。起点和终点相同的路径称为回路，简单路径组成的回路称为简单回路。路径上经过的边的数目称为该路径的路径长度。,9 有根图,在一个有向图中，若从顶点V有路径可以到达图中的其它所有顶点，则称此有向图为有根图，顶点V称作图的根。,10 生成树、生成森林,连通图的生成树是一个极小连通子图，它包含图中全部n个顶点和n-1条不构成回路的边。非边通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。,7.2 图的存贮结构,7.2.1 邻接矩阵,1 图的邻接矩阵表示,在邻接矩阵表示中
7、，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。若（i,j）E(G)或i,jE(G),则矩阵中第i行 第j列元素值为1，否则为0 。,图的邻接矩阵定义为： 1 若（i,j）E(G)或i,jE(G) Aij= 0 其它情形,例如, 对图7-8所示的无向图和有向图,它们的邻接矩阵见图7-9。,2 从无向图的邻接矩阵可以得出如下结论,（1）矩阵是对称的; （2）第i行或第i 列1的个数为顶点i 的度; （3）矩阵中1的个数的一半为图中边的数目; （4）很容易判断顶点i 和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。,3 从有向图的邻接矩阵可以得出如下结论,（1） 矩阵不一定是
8、对称的; （2） 第i 行中1的个数为顶点i 的出度; （3） 第i列中1的个数为顶点 i的入度; （4） 矩阵中1的个数为图中弧的数目; （5） 很容易判断顶点i 和顶点j 是否有弧相连.,4 网的邻接矩阵表示,类似地可以定义网的邻接矩阵为： wij 若（i,j）E(G)或i,jE(G) Aij= 0 若i=j 其它情形 网及网的邻接矩阵见图7-10。,5 图的邻接矩阵数据类型描述,图的邻接矩阵数据类型描述如下: const int n= maxn； / 图中顶点数 const int e=maxe ； / 图中边数 struct graph elemtype Vn+1; / 存放顶点信息v
9、1,v2,.vn，不使用v0存储空间 int arcsn+1n+1 / 邻接矩阵 ;,6 建立无向图的邻接矩阵,void creatadj(graph 该算法的时间复杂度为O（n2）。,7.建立有向图的邻接矩阵,void creatadj(graph 该算法的时间复杂度为O（n2）。,8.建立无向网的邻接矩阵,void creatadj(graph 该算法的时间复杂度为O（n2）。,9.建立有向网的邻接矩阵,void creatadj(graph 该算法的时间复杂度为O（n2）。,7.2.2 邻接表,1 图的邻接表表示,将每个结点的边用一个单链表链接起来，若干个结点可以得到若干个单链表，每个单
10、链表都有一个头结点，所有头结点组成一个一维数组，称这样的链表为邻接表。 例如，图7-8所示的无向图G3和有向图G4的邻接表见图7-11所示,2 从无向图的邻接表可以得到如下结论,（1）第i 个链表中结点数目为顶点i的度； （2）所有链表中结点数目的一半为图中边数； （3）占用的存储单元数目为n+2e 。,3 从有向图的邻接表可以得到如下结论,（1）第i 个链表中结点数目为顶点i的出度； （2）所有链表中结点数目为图中弧数； （3）占用的存储单元数目为n+e 。,从有向图的邻接表可知，不能求出顶点的入度。为此，我们必须另外建立有向图的逆邻接表，以便求出每一个顶点的入度。逆邻接表在图7-11(c)
11、中已经给出，从该图中可知。有向图的逆邻接表与邻接表类似，只是它是从入度考虑结点，而不是从出度考虑结点。,4 图的邻接表数据类型描述,图的邻接表数据类型描述如下： const int n =maxn； / maxn表示图中最大顶点数 const int e= maxe ； / maxe图中最大边数 struct link /定义链表类型 elemtype data ; link *next ; struct node /定义邻接表的表头类型 elemtype v; /顶点信息 link *next; an+1;,5.无向图的邻接表建立,void creatlink( ) int i,j,k ;
12、link *s ; for(i=1; iij ; /输入一条边 (i,j) s=new link; /申请一个动态存储单元 sdata=j ; s-next=ai.next ;ai.next=s ; s=new link; s-data=i ; s-next=aj.next ;aj.next=s ;,该算法的时间复杂度为O（n+e）。,6.有向图的邻接表建立,void creatlink( ) int i,j,k ; link *s ; for(i=1; iij ; /输入一条边 s=new link; /申请一个动态存储单元 sdata=j ;s-next=ai.next ; ai.next
13、=s ; 该算法的时间复杂度为O（n+e）。,7.网的邻接表的数据类型描述,网的邻接表的数据类型可描述如下： const int n =maxn； / maxn表示网中最大顶点数 const int e= maxe ； / maxe网中最大边数 struct link /定义链表类型 elemtype data ; float w; /定义网上的权值类型为浮点型 link *next ; struct node /定义邻接表的表头类型 elemtype v; /顶点信息 link *next; an+1;,8 无向网的邻接表建立,void creatlink( ) float w; int i
14、,j,k ; link *s ; for(i=1; iijw ; /输入一条边 (i,j)及该边上的权值 s=new link; /申请一个动态存储单元 sdata=j ;s-w=w; s-next=ai.next ;ai.next=s ;s=new link; s-data=i ;s-w=w;s-next=aj.next ; aj.next=s ; 该算法的时间复杂度为O（n+e）。,9 有向网的邻接表建立,void creatlink( ) float w;int i,j,k ; link *s ; for(i=1; iijw ; /输入一条弧 及该弧上的权值 s=new link; /申
15、请一个动态存储单元 sdata=j ;s-w=w; s-next=ai.next ; ai.next=s ; 该算法的时间复杂度为O（n+e）。,另外，请注意上面的算法中，建立的邻接表不是唯一的,与你从键盘输入边的顺序有关，输入的边的顺序不同，则得到的链表也不同。,7.2.3 邻接多重表,在无向图的邻接表中，每条边（Vi,Vj）由两个结点表示，一个结点在第i个链表中，另一个结点在第j个链表中，当需要对边进行操作时，就需要找到表示同一条边的两个结点，这给操作带来不便，在这种情况下采用邻接多重表较方便。 在邻接多重表中，每条边用一个结点表示，每个结点由五个域组成，其结点结构为 ：,其中mark为标志域，用来标记这条边是否被访问过，i和j
