《数据结构图的遍历与连通性参考用.pptx》由会员分享，可在线阅读，更多相关《数据结构图的遍历与连通性参考用.pptx（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、邻接矩阵邻接矩阵是用于描述图中顶点之间关系是用于描述图中顶点之间关系(即弧或即弧或边的权边的权)的矩阵。的矩阵。邻接表邻接表类似树的孩子链表。即对图中的每个顶点类似树的孩子链表。即对图中的每个顶点vivi建立一个单链表，表中结点表示依附于该顶建立一个单链表，表中结点表示依附于该顶点点vivi的边或弧。的边或弧。邻接点域邻接点域链域链域数据域数据域数据域数据域链域链域表结点表头结点第1页/共30页V1V3V2V4例：4 3 2 121113442第2页/共30页3.3.有向图的十字链表存储表示有向图的十字链表存储表示两种结点结构：尾域尾域tailvextailvex头域头域headvexhead
2、vex链域链域hlinkhlink链域链域tlinktlink信息域信息域infoinfo数据域数据域datadata链域链域firstinfirstin链域链域firstoutfirstout顶点结点弧结点第3页/共30页v1v2v3v4 0 1 2 3 10/20v3v1 v4v2 /03/13/2302/32例：datadatafirstinfirstinfirstoutfirstouttailvexheadvex hlinktlink/第4页/共30页标志域标志域边顶点边顶点i i边顶点边顶点j j链域链域i i 链域链域j j 信息域信息域数据域数据域边链域边链域4.4.无向图的邻接
3、多重表存储表示无向图的邻接多重表存储表示边结点顶点结点第5页/共30页1 3 4 2 例：1234121324第6页/共30页第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径第7页/共30页7.3 7.3 图的遍历图的遍历 从图中某一顶点出发访遍图中其余顶点，且从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做使每一个顶点仅被访问一次。这一过程就叫做图的遍历图的遍历。通常有两条遍历图的路径：通常有两条遍历图的路径：n深度优先搜索深度优先搜索n广度优先搜索广度优先搜索第8页/共30页1
4、.1.深度优先搜索深度优先搜索(DFS)(DFS)基本思想：从图中某顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点；重复上述过程，直至图中所有顶点都被访问到为止。第9页/共30页 例：从顶点v1出发，DFS下图。顶点访问序列为：v1,v2,v4,v8,v5,v3,v6,v7v1v6v2v5v3v8v4v7第10页/共30页图的DFS算法一般描述int visitedMAXVEX;/访问标志数组void DFSgraph(Graph G,Visi
5、t()/对图G作深度优先遍历 for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;v=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w递归调用DFS 第12页/共30页用邻接表实现图的深度优先搜索v1v6v2v5v3v8v4v7v9v1012345678 2 8 2 8 3 7 3 6 4 5 2 3 2 3 1 6 7 1 4 5910 9/10/第13页/共30页分析：分析：在遍历图时，对图中每个顶点至多调用一在遍历图时，对图中每个顶点至多调用一次次DFSDFS函数，
6、因为一旦某个顶点被标志成已被访函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。所采用的存储结构。第14页/共30页2.2.广度优先搜索广度优先搜索(BFS)(BFS)基本思想：从图中某个顶点V0出发，并在访问此顶点后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选
7、图中一个未曾被访问的顶点作起始点；重复上述过程，直至图中所有顶点都被访问到为止。第15页/共30页 例：从顶点v1出发，BFS下图。顶点访问序列为：v1,v2,v3,v4,v5,v6,v7,v8v1v6v2v5v3v8v4v7第16页/共30页用邻接表实现图的广度优先搜索12345678 2 8 2 8 3 7 3 6 4 5 2 3 2 3 1 6 7 1 4 5v1v6v2v5v3v8v4v7第17页/共30页B BFSFS非递归非递归算法算法void BFSTraverse(Graph G,Status(*Visit)(int void BFSTraverse(Graph G,Statu
8、s(*Visit)(int v)v)/使用辅助队列使用辅助队列Q Q和访问标志数组和访问标志数组visitedv visitedv for(v=0;vG.vexnum;+v)visitedv=for(v=0;vG.vexnum;+v)visitedv=FALSE;FALSE;InitQueue(Q);InitQueue(Q);/置空的辅助队列置空的辅助队列Q Q for(v=0;vG.vexnum;+v)for(v=0;v=0;w=NextAdjVex(G,u,w)(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)）if(!visitedw)if(!visi
9、tedw)/w/w为为u u的尚未访问的邻接顶点的尚未访问的邻接顶点 visitedw=TRUE;Visit(w);visitedw=TRUE;Visit(w);EnQueue(Q,w);EnQueue(Q,w);/if /if /while /while if if /BFSTraverse /BFSTraverse第19页/共30页分析：分析：每个顶点至多进一次队列。遍历图的过程每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程，因此广实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不
10、同之处仅仅在于对顶点访索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。问的顺序不同。第20页/共30页第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径第21页/共30页7.4 7.4 图的连通性问题图的连通性问题1 1）无向图的无向图的连通分量和连通分量和生成树生成树2 2）最小生成树最小生成树3 3）普里姆算法）普里姆算法4 4）克鲁斯卡尔算法）克鲁斯卡尔算法第22页/共30页1.1.无向图的无向图的连通分量和连通分量和生成树生成树基本概念基本概念n连通分量的顶点集连通分量的顶点集：即从该连通分量的某一
11、顶点出发进行搜索所得到：即从该连通分量的某一顶点出发进行搜索所得到的顶点访问序列；的顶点访问序列；n生成树生成树：某连通分量的极小连通子图某连通分量的极小连通子图；n生成森林生成森林：非连通图的各个连通分量的极小连通子图构成的集合：非连通图的各个连通分量的极小连通子图构成的集合。第23页/共30页 设设E(G)E(G)为连通子图为连通子图G G中所有边的集合，则从中所有边的集合，则从图中任一顶点出发遍历图时，必定将图中任一顶点出发遍历图时，必定将E(G)E(G)分成分成两个集合两个集合T(G)T(G)和和B(G)B(G)，其中，其中T(G)T(G)是遍历过程中是遍历过程中历经的边的集合。显然，
12、历经的边的集合。显然，T(G)T(G)和图和图G G中所有顶中所有顶点一起构成连通图点一起构成连通图G G的极小连通子图，按照的极小连通子图，按照7.17.1节的定义，它是连通图的一棵生成树，并且称节的定义，它是连通图的一棵生成树，并且称由深度优先搜索得到的为由深度优先搜索得到的为深度优先生成树深度优先生成树；由；由广度优先搜索得到的为广度优先搜索得到的为广度优先生成树广度优先生成树。第24页/共30页例：求下图的深度优先生成树和广度优先生成树。v1v6v2v5v3v8v4v7第25页/共30页 对非连通图，每个连通分量中的顶点集和对非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干
13、棵生成树，这些遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的连通分量的生成树组成非连通图的生成森林生成森林。例：例：第26页/共30页生成非连通图的深度优先生成森林的算法生成非连通图的深度优先生成森林的算法void DFSForest(Graph G，CSTree&T)/建立无向图G的深度优先生成森林的(左)孩子(右)兄弟链表T。T=NULL；for(v=0；vG.vexnum；+v)visitedv=FALSE；for(v=0；vnextsibling=p;/是其它生成树的根(前一棵的根的“兄弟”)q=p;/q指示当前生成树的根 DFSTree(G,v,p);/建立以
14、p为根的生成树 /DFSForest第27页/共30页void DFSTree(Graph Gvoid DFSTree(Graph G，int vint v，CSTree&T)CSTree&T)/从第从第v v个顶点出发深度优先遍历图个顶点出发深度优先遍历图Q Q，建立以，建立以T T为根的生成树。为根的生成树。visitedv=TRUEvisitedv=TRUE；first=TRUEfirst=TRUE；for(w=FisrtAdjVex(G,v);w=0;w=NextAdjVex(G,v,for(w=FisrtAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)w)if(
15、!visitedw)if(!visitedw)p=(CSTree)malloc(sizeof(CSNode);p=(CSTree)malloc(sizeof(CSNode);/分配孩子结分配孩子结点点 *p=GetVex(G,w)p=GetVex(G,w)，NULLNULL，NULLNULL；if(first)if(first)/w/w是是v v的第一个未被访问的邻接顶点的第一个未被访问的邻接顶点 T Tlchild=plchild=p；first=FALSEfirst=FALSE；/是根的左孩子结点是根的左孩子结点 else else /w/w是是v v的其它未被访问的邻接顶点的其它未被访问
16、的邻接顶点 q qnextsibling=pnextsibling=p；/是上一邻接顶点的右兄弟是上一邻接顶点的右兄弟结点结点 q=p q=p；DFSTree(G,w,q)DFSTree(G,w,q)；/从第从第w w个顶点出发深度优先遍历图个顶点出发深度优先遍历图G G，建立子生，建立子生成树成树q q /if/if /DFSTree/DFSTree第28页/共30页1.1.理解并掌握图的深度优先搜索和广度优先搜理解并掌握图的深度优先搜索和广度优先搜索两种遍历算法及其性能分析；以及两种遍历索两种遍历算法及其性能分析；以及两种遍历所使用的辅助数据结构（栈或队列）在遍历过所使用的辅助数据结构（栈或队列）在遍历过程中所起的作用，能够确定两种遍历所得到的程中所起的作用，能够确定两种遍历所得到的顶点访问序列以及利用图的两种遍历设计算法顶点访问序列以及利用图的两种遍历设计算法解决简单的应用问题。解决简单的应用问题。2.2.理解并掌握生成树的概念，能画出给定的图理解并掌握生成树的概念，能画出给定的图深度优先和广度优先生成树或生成森林；深度优先和广度优先生成树或生成森林；作业作业P49P49：7.217.21小结第29页/共30页感谢您的观看！第30页/共30页