数据结构第讲图的遍历与连通性精品文稿.ppt
数据结构第讲图的遍历与连通性第1页，本讲稿共30页邻接矩阵邻接矩阵是用于描述图中顶点之间关系是用于描述图中顶点之间关系(即弧或边的即弧或边的权权)的矩阵。的矩阵。邻接表邻接表类似树的孩子链表。即对图中的每个顶点类似树的孩子链表。即对图中的每个顶点vivi建立一建立一个单链表，表中结点表示依附于该顶点个单链表，表中结点表示依附于该顶点vivi的边或弧。的边或弧。邻接点域链域数据域数据域链域表结点表头结点第2页，本讲稿共30页V1V3V2V4例：4 3 2 121113442第3页，本讲稿共30页3.3.有向图的十字链表存储表示有向图的十字链表存储表示两种结点结构：尾域tailvex头域headvex链域hlink链域tlink信息域info数据域data链域firstin链域firstout顶点结点弧结点第4页，本讲稿共30页v1v2v3v4 0 1 2 3 10/20v3v1 v4v2 /03/13/2302/32例：datafirstinfirstouttailvexheadvex hlinktlink/第5页，本讲稿共30页标志域边顶点i边顶点j链域i 链域j 信息域数据域边链域4.4.无向图的邻接多重表存储表示无向图的邻接多重表存储表示边结点顶点结点第6页，本讲稿共30页1 3 4 2 例：1234121324第7页，本讲稿共30页第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径第8页，本讲稿共30页7.3 7.3 图的遍历图的遍历 从图中某一顶点出发访遍图中其余顶点，且使每一个从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做顶点仅被访问一次。这一过程就叫做图的遍历图的遍历。通常有两条遍历图的路径：通常有两条遍历图的路径：n深度优先搜索深度优先搜索n广度优先搜索广度优先搜索第9页，本讲稿共30页1.1.深度优先搜索深度优先搜索(DFS)(DFS)基本思想：从图中某顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点；重复上述过程，直至图中所有顶点都被访问到为止。第10页，本讲稿共30页 例：从顶点v1出发，DFS下图。顶点访问序列为：顶点访问序列为：v v1,v2,v4,v8,v5,v3,v6,v71,v2,v4,v8,v5,v3,v6,v7v1v6v2v5v3v8v4v7第11页，本讲稿共30页图的图的DFS算法一般描述算法一般描述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)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w递归调用DFS 第13页，本讲稿共30页用邻接表实现图的深度优先搜索v1v6v2v5v3v8v4v7v9v1012345678 2 8 2 8 3 7 3 6 4 5 2 3 2 3 1 6 7 1 4 5910 9/10/第14页，本讲稿共30页分析：分析：在遍历图时，对图中每个顶点至多调用一次在遍历图时，对图中每个顶点至多调用一次DFSDFS函数，因为一旦某个顶点被标志成已被访问，就不再函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储邻接点的过程。其耗费的时间则取决于所采用的存储结构。结构。第15页，本讲稿共30页2.2.广度优先搜索广度优先搜索(BFS)(BFS)基本思想：从图中某个顶点V0出发，并在访问此顶点后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点；重复上述过程，直至图中所有顶点都被访问到为止。第16页，本讲稿共30页 例：从顶点v1出发，BFS下图。顶点访问序列为：顶点访问序列为：v v1 1,v,v2 2,v,v3 3,v,v4 4,v,v5 5,v,v6 6,v,v7 7,v,v8 8v1v6v2v5v3v8v4v7第17页，本讲稿共30页用邻接表实现图的广度优先搜索12345678 2 8 2 8 3 7 3 6 4 5 2 3 2 3 1 6 7 1 4 5v1v6v2v5v3v8v4v7第18页，本讲稿共30页B BFSFS非递归非递归算法算法void BFSTraverse(Graph G,Status(*Visit)(int v)void BFSTraverse(Graph G,Status(*Visit)(int v)/使用辅助队列使用辅助队列Q Q和访问标志数组和访问标志数组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=TRUE;Visit(w);visitedw=TRUE;Visit(w);EnQueue(Q,w);EnQueue(Q,w);/if /if /while /while if if /BFSTraverse /BFSTraverse第20页，本讲稿共30页分析：分析：每个顶点至多进一次队列。遍历图的过程实质上是通每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。于对顶点访问的顺序不同。第21页，本讲稿共30页第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径第22页，本讲稿共30页7.4 7.4 图的连通性问题图的连通性问题1 1）无向图的连通分量和生成树）无向图的连通分量和生成树2 2）最小生成树）最小生成树3 3）普里姆算法）普里姆算法4 4）克鲁斯卡尔算法）克鲁斯卡尔算法第23页，本讲稿共30页1.1.无向图的连通分量和生成树无向图的连通分量和生成树基本概念基本概念n连通分量的顶点集连通分量的顶点集：即从该连通分量的某一：即从该连通分量的某一顶点出发进行搜索所得到的顶点访问序列；顶点出发进行搜索所得到的顶点访问序列；n生成树生成树：某连通分量的极小连通子图；：某连通分量的极小连通子图；n生成森林生成森林：非连通图的各个连通分量的极小：非连通图的各个连通分量的极小连通子图构成的集合。连通子图构成的集合。第24页，本讲稿共30页 设设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)和图和图G G中所有顶点一起构成连通图中所有顶点一起构成连通图G G的极小连通子图，的极小连通子图，按照按照7.17.1节的定义，它是连通图的一棵生成树，并且称节的定义，它是连通图的一棵生成树，并且称由深度优先搜索得到的为由深度优先搜索得到的为深度优先生成树深度优先生成树；由广度优；由广度优先搜索得到的为先搜索得到的为广度优先生成树广度优先生成树。第25页，本讲稿共30页例：求下图的深度优先生成树和广度优先生成树。v1v6v2v5v3v8v4v7第26页，本讲稿共30页 对非连通图，每个连通分量中的顶点集和遍历时走对非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的组成非连通图的生成森林生成森林。例：例：第27页，本讲稿共30页生成非连通图的深度优先生成森林的算法生成非连通图的深度优先生成森林的算法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)visitedv=FALSE+v)visitedv=FALSE；for(v=0 for(v=0；vG.vexnumvnextsibling=p;nextsibling=p;/是其它生成树的根是其它生成树的根(前一棵的根的前一棵的根的“兄弟兄弟”)q=p;q=p;/q/q指示当前生成树的根指示当前生成树的根 DFSTree(G,v,p);DFSTree(G,v,p);/建立以建立以p p为根的生成树为根的生成树 /DFSForest/DFSForest第28页，本讲稿共30页void DFSTree(Graph Gvoid DFSTree(Graph G，int vint v，CSTree&T)CSTree&T)/从第从第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);/分配孩子结点分配孩子结点 *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的其它未被访问的邻接顶点的其它未被访问的邻接顶点 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第29页，本讲稿共30页1.1.理解并掌握图的深度优先搜索和广度优先搜索两种遍历理解并掌握图的深度优先搜索和广度优先搜索两种遍历算法及其性能分析；以及两种遍历所使用的辅助数据结构算法及其性能分析；以及两种遍历所使用的辅助数据结构（栈或队列）在遍历过程中所起的作用，能够确定两种遍（栈或队列）在遍历过程中所起的作用，能够确定两种遍历所得到的顶点访问序列以及利用图的两种遍历设计算法历所得到的顶点访问序列以及利用图的两种遍历设计算法解决简单的应用问题。解决简单的应用问题。2.2.理解并掌握生成树的概念，能画出给定的图深度优先理解并掌握生成树的概念，能画出给定的图深度优先和广度优先生成树或生成森林；和广度优先生成树或生成森林；作业作业P49P49：7.217.21小结第30页，本讲稿共30页
