数据结构图的遍历与连通性参考用.ppt

《数据结构图的遍历与连通性参考用.ppt》由会员分享，可在线阅读，更多相关《数据结构图的遍历与连通性参考用.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、7.2 7.2 图的存储结构图的存储结构n图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示n图的邻接表存储表示图的邻接表存储表示n有向图的十字链表存储表示有向图的十字链表存储表示n无向图的邻接多重表存储表示无向图的邻接多重表存储表示邻接矩阵邻接矩阵是用于描述图中顶点之间关系是用于描述图中顶点之间关系(即弧或边即弧或边的权的权)的矩阵。的矩阵。邻接表邻接表类似树的孩子链表。即对图中的每个顶点类似树的孩子链表。即对图中的每个顶点vivi建立一个单链表，表中结点表示依附于该顶点建立一个单链表，表中结点表示依附于该顶点vivi的的边或弧。边或弧。邻接点域邻接点域链域链域数据域数据域数据域数据域链域

2、链域表结点表结点表头结点表头结点V1V3V2V4例：例：4 3 2 1211134423.3.有向图的十字链表存储表示有向图的十字链表存储表示两种结点结构：两种结点结构：尾域尾域tailvextailvex头域头域headvexheadvex链域链域hlinkhlink链域链域tlinktlink信息域信息域infoinfo数据域数据域datadata链域链域firstinfirstin链域链域firstoutfirstout顶点结点顶点结点弧结点弧结点v v1 1v v2 2v v3 3v v4 4 0 1 2 3 10/20v3v1 v4v2 /03/13/2302/32例：例：datad

3、atafirstinfirstinfirstoutfirstouttailvexheadvex hlinktlink/标志域标志域边顶点边顶点i i边顶点边顶点j j链域链域i i 链域链域j j 信息域信息域数据域数据域边链域边链域4.4.无向图的邻接多重表存储表示无向图的邻接多重表存储表示边结点边结点顶点结点顶点结点1 3 4 2 例：例：1234121324第第7 7章章 图图7.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储结构图的存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性问题图的连通性问题7.5 7.5 有向无环图及其应用有向无环图及其应用7

4、.6 7.6 最短路径最短路径7.3 7.3 图的遍历图的遍历 从图中某一顶点出发访遍图中其余顶点，且使从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做每一个顶点仅被访问一次。这一过程就叫做图的图的遍历遍历。通常有两条遍历图的路径：通常有两条遍历图的路径：n深度优先搜索深度优先搜索n广度优先搜索广度优先搜索1.1.深度优先搜索深度优先搜索(DFS)(DFS)基本思想：基本思想：从图中某顶点从图中某顶点V V0 0出发，访问此顶点，然后依次出发，访问此顶点，然后依次从从V V0 0的各个未被访问的邻接点出发的各个未被访问的邻接点出发深度优先搜索深度优先搜索遍遍历图，

5、直至图中所有和历图，直至图中所有和V V0 0有路径相通的顶点都被访有路径相通的顶点都被访问到；问到；若此时图中尚有顶点未被访问，则另选图中一若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点；个未曾被访问的顶点作起始点；重复上述过程，直至图中所有顶点都被访问到重复上述过程，直至图中所有顶点都被访问到为止。为止。例：例：从顶点从顶点v1v1出发，出发，DFSDFS下图。下图。顶点访问序列为：顶点访问序列为：v1,v2,v4,v8,v5,v3,v6,v7v1,v2,v4,v8,v5,v3,v6,v7v1v1v6v6v2v2v5v5v3v3v8v8v4v4v7v7图的图的DFS算法

6、一般描述算法一般描述int visitedMAXVEX;int visitedMAXVEX;/访问标志数组访问标志数组void DFSgraph(Graph G,Visit()void DFSgraph(Graph G,Visit()/对图对图G G作深度优先遍历作深度优先遍历 for(v=0;vG.vexnum;+v)visitedv=FALSE;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化访问标志数组初始化 for(v=0;vG.vexnum;+v)for(v=0;v=0;w=NextAdjVex(G,v,w)for(w=FirstAdjVe

7、x(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);if(!visitedw)DFS(G,w);/对对v v的尚未访问的邻接顶点的尚未访问的邻接顶点w w递归调用递归调用DFSDFS 用邻接表实现图的深度优先搜索用邻接表实现图的深度优先搜索v1v1v6v6v2v2v5v5v3v3v8v8v4v4v7v7v9v9v10v1012345678 2 8 2 8 3 7 3 6 4 5 2 3 2 3 1 6 7 1 4 5910 9/10/分析：分析：在遍历图时，对图中每个顶点至多调用一次在遍历图时，对图中每个顶点至多调用一次DFSDFS函数，因为

8、一旦某个顶点被标志成已被访问，函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。用的存储结构。2.2.广度优先搜索广度优先搜索(BFS)(BFS)基本思想：基本思想：从图中某个顶点从图中某个顶点V V0 0出发，并在访问此顶点后依出发，并在访问此顶点后依次访问次访问V V0 0的所有未被访问过的邻接点，之后按这些的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接

9、点，直顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和至图中所有和V V0 0有路径相通的顶点都被访问到；有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点；个未曾被访问的顶点作起始点；重复上述过程，直至图中所有顶点都被访问到重复上述过程，直至图中所有顶点都被访问到为止。为止。例：例：从顶点从顶点v v1 1出发，出发，BFSBFS下图。下图。顶点访问序列为：顶点访问序列为：v v1 1,v,v2 2,v,v3 3,v,v4 4,v,v5 5,v,v6 6,v,v7 7,v,v8 8v v1 1v v6

10、 6v v2 2v v5 5v v3 3v v8 8v v4 4v v7 7用邻接表实现图的广度优先搜索用邻接表实现图的广度优先搜索12345678 2 8 2 8 3 7 3 6 4 5 2 3 2 3 1 6 7 1 4 5v v1 1v v6 6v v2 2v v5 5v v3 3v v8 8v v4 4v v7 7B BFSFS非递归算法非递归算法void BFSTraverse(Graph G,Status(*Visit)(int v)void BFSTraverse(Graph G,Status(*Visit)(int v)/使用辅助队列使用辅助队列Q Q和访问标志数组和访问标志数

11、组visitedv visitedv for(v=0;vG.vexnum;+v)visitedv=FALSE;for(v=0;vG.vexnum;+v)visitedv=FALSE;InitQueue(Q);InitQueue(Q);/置空的辅助队列置空的辅助队列Q Q for(v=0;vG.vexnum;+v)for(v=0;v=0;w=NextAdjVex(G,u,w)for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)）if(!visitedw)if(!visitedw)/w/w为为u u的尚未访问的邻接顶点的尚未访问的邻接顶点 visitedw=

12、TRUE;Visit(w);visitedw=TRUE;Visit(w);EnQueue(Q,w);EnQueue(Q,w);/if /if /while /while if if /BFSTraverse /BFSTraverse分析：分析：每个顶点至多进一次队列。遍历图的过程实质每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。两者不同之处仅仅在于对顶点访问的顺序不同。第第7 7章章

13、图图7.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储结构图的存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性问题图的连通性问题7.5 7.5 有向无环图及其应用有向无环图及其应用7.6 7.6 最短路径最短路径7.4 7.4 图的连通性问题图的连通性问题1 1）无向图的连通分量和生成树无向图的连通分量和生成树2 2）最小生成树）最小生成树3 3）普里姆算法）普里姆算法4 4）克鲁斯卡尔算法）克鲁斯卡尔算法1.1.无向图的连通分量和生成树无向图的连通分量和生成树基本概念基本概念n连通分量的顶点集连通分量的顶点集：即从该连通分量的某一：即从该连通分量的某一顶点

14、出发进行搜索所得到的顶点访问序列；顶点出发进行搜索所得到的顶点访问序列；n生成树生成树：某连通分量的极小连通子图某连通分量的极小连通子图；n生成森林生成森林：非连通图的各个连通分量的极小：非连通图的各个连通分量的极小连通子图构成的集合连通子图构成的集合。设设E(G)E(G)为连通子图为连通子图G G中所有边的集合，则从图中所有边的集合，则从图中任一顶点出发遍历图时，必定将中任一顶点出发遍历图时，必定将E(G)E(G)分成两个分成两个集合集合T(G)T(G)和和B(G)B(G)，其中，其中T(G)T(G)是遍历过程中历经的是遍历过程中历经的边的集合。显然，边的集合。显然，T(G)T(G)和图和图

15、G G中所有顶点一起构成中所有顶点一起构成连通图连通图G G的极小连通子图，按照的极小连通子图，按照7.17.1节的定义，它节的定义，它是连通图的一棵生成树，并且称由深度优先搜索是连通图的一棵生成树，并且称由深度优先搜索得到的为得到的为深度优先生成树深度优先生成树；由广度优先搜索得到；由广度优先搜索得到的为的为广度优先生成树广度优先生成树。例：求下图的深度优先生成树和广度优先生成树。例：求下图的深度优先生成树和广度优先生成树。v v1 1v v6 6v v2 2v v5 5v v3 3v v8 8v v4 4v v7 7 对非连通图，每个连通分量中的顶点集和遍对非连通图，每个连通分量中的顶点集

16、和遍历时走过的边一起构成若干棵生成树，这些连通历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的分量的生成树组成非连通图的生成森林生成森林。例：例：生成非连通图的深度优先生成森林的算法生成非连通图的深度优先生成森林的算法void DFSForest(Graph Gvoid DFSForest(Graph G，CSTree&T)CSTree&T)/建立无向图建立无向图G G的深度优先生成森林的的深度优先生成森林的(左左)孩子孩子(右右)兄弟链表兄弟链表T T。T=NULL T=NULL；for(v=0 for(v=0；vG.vexnum vG.vexnum；+v)visited

17、v=FALSE+v)visitedv=FALSE；for(v=0 for(v=0；vG.vexnumvnextsibling=p;else qnextsibling=p;/是其它生成树的根是其它生成树的根(前一棵的根的前一棵的根的“兄弟兄弟”)”)q=p;q=p;/q/q指示当前生成树的根指示当前生成树的根 DFSTree(G,v,p);DFSTree(G,v,p);/建立以建立以p p为根的生成树为根的生成树 /DFSForest/DFSForestvoid DFSTree(Graph Gvoid DFSTree(Graph G，int vint v，CSTree&T)CSTree&T)/从

18、第从第v v个顶点出发深度优先遍历图个顶点出发深度优先遍历图Q Q，建立以，建立以T T为根的生成树。为根的生成树。visitedv=TRUE visitedv=TRUE；first=TRUE first=TRUE；for(w=FisrtAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)for(w=FisrtAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)if(!visitedw)p=(CSTree)malloc(sizeof(CSNode);p=(CSTree)malloc(sizeof(CSNode);/分配孩子结点分配孩

19、子结点 *p=GetVex(G,w)*p=GetVex(G,w)，NULLNULL，NULLNULL；if(first)if(first)/w/w是是v v的第一个未被访问的邻接顶点的第一个未被访问的邻接顶点 Tlchild=p Tlchild=p；first=FALSEfirst=FALSE；/是根的左孩子结点是根的左孩子结点 else else /w/w是是v v的其它未被访问的邻接顶点的其它未被访问的邻接顶点 qnextsibling=p qnextsibling=p；/是上一邻接顶点的右兄弟结点是上一邻接顶点的右兄弟结点 q=p q=p；DFSTree(G,w,q)DFSTree(G,

20、w,q)；/从第从第w w个顶点出发深度优先遍历图个顶点出发深度优先遍历图G G，建立子生成树，建立子生成树q q /if/if /DFSTree/DFSTree1.1.理解并掌握图的深度优先搜索和广度优先搜索理解并掌握图的深度优先搜索和广度优先搜索两种遍历算法及其性能分析；以及两种遍历所使两种遍历算法及其性能分析；以及两种遍历所使用的辅助数据结构（栈或队列）在遍历过程中所用的辅助数据结构（栈或队列）在遍历过程中所起的作用，能够确定两种遍历所得到的顶点访问起的作用，能够确定两种遍历所得到的顶点访问序列以及利用图的两种遍历设计算法解决简单的序列以及利用图的两种遍历设计算法解决简单的应用问题。应用问题。2.2.理解并掌握生成树的概念，能画出给定的图深理解并掌握生成树的概念，能画出给定的图深度优先和广度优先生成树或生成森林；度优先和广度优先生成树或生成森林；作业作业P49P49：7.217.21小结小结