《数据结构图的遍历与连通性参考用.ppt》由会员分享，可在线阅读，更多相关《数据结构图的遍历与连通性参考用.ppt（30页珍藏版）》请在三一办公上搜索。
1、7.2 图的存储结构,图的数组(邻接矩阵)存储表示图的邻接表存储表示有向图的十字链表存储表示无向图的邻接多重表存储表示,邻接矩阵是用于描述图中顶点之间关系(即弧或边的权)的矩阵。邻接表类似树的孩子链表。即对图中的每个顶点vi建立一个单链表，表中结点表示依附于该顶点vi的边或弧。,表结点,表头结点,V1,V3,V2,V4,例：,3.有向图的十字链表存储表示,两种结点结构：,顶点结点,弧结点,0 1 2 3,v3,v1,v4,v2,例：,tailvex,headvex,hlink,tlink,/,4.无向图的邻接多重表存储表示,边结点,顶点结点,例：,第7章 图7.1 图的定义和术语7.2 图的存
2、储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径,7.3 图的遍历,从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做图的遍历。通常有两条遍历图的路径：深度优先搜索广度优先搜索,1.深度优先搜索(DFS),基本思想：从图中某顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点；重复上述过程，直至图中所有顶点都被访问到为止。,例：从顶点v1出发，DFS下图。,顶点访问序列为：v1,v2,
3、v4,v8,v5,v3,v6,v7,图的DFS算法一般描述int visitedMAXVEX;/访问标志数组void DFSgraph(Graph G,Visit()/对图G作深度优先遍历 for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用DFS,void DFS(Graph G,int v)/从第v个顶点出发递归地深度优先遍历图G visitedv=TRUE;Visit(v);/访问第v个顶点 for(w=FirstAdjVex(G,v);w
4、=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w递归调用DFS,用邻接表实现图的深度优先搜索,v1,v6,v2,v5,v3,v8,v4,v7,v9,v10,分析：在遍历图时，对图中每个顶点至多调用一次DFS函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。,2.广度优先搜索(BFS),基本思想：从图中某个顶点V0出发，并在访问此顶点后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点
5、，直至图中所有和V0有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点；重复上述过程，直至图中所有顶点都被访问到为止。,例：从顶点v1出发，BFS下图。,顶点访问序列为：v1,v2,v3,v4,v5,v6,v7,v8,用邻接表实现图的广度优先搜索,BFS非递归算法,void BFSTraverse(Graph G,Status(*Visit)(int v)/使用辅助队列Q和访问标志数组visitedv for(v=0;vG.vexnum;+v)visitedv=FALSE;InitQueue(Q);/置空的辅助队列Q for(v=0;vG.vexnu
6、m;+v)if(!visitedv)/v尚未访问 visitedv=TRUE;Visit(v);EnQueue(Q,v);/v入队,while(!QueueEmpty(Q)DeQueue(Q,u);/队头元素出队并置为u for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)）if(!visitedw)/w为u的尚未访问的邻接顶点 visitedw=TRUE;Visit(w);EnQueue(Q,w);/if/while if/BFSTraverse,分析：每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复
7、杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。,第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径,7.4 图的连通性问题,1）无向图的连通分量和生成树2）最小生成树3）普里姆算法4）克鲁斯卡尔算法,1.无向图的连通分量和生成树基本概念连通分量的顶点集：即从该连通分量的某一顶点出发进行搜索所得到的顶点访问序列；生成树：某连通分量的极小连通子图；生成森林：非连通图的各个连通分量的极小连通子图构成的集合。,设E(G)为连通子图G中所有边的集合，则从图中任一顶点出发遍历图时，必定将E(G)分成两
8、个集合T(G)和B(G)，其中T(G)是遍历过程中历经的边的集合。显然，T(G)和图G中所有顶点一起构成连通图G的极小连通子图，按照7.1节的定义，它是连通图的一棵生成树，并且称由深度优先搜索得到的为深度优先生成树；由广度优先搜索得到的为广度优先生成树。,例：求下图的深度优先生成树和广度优先生成树。,对非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。例：,生成非连通图的深度优先生成森林的算法,void DFSForest(Graph G，CSTree/建立以p为根的生成树/DFSForest,void DFSTree(Graph
9、 G，int v，CSTree/分配孩子结点*p=GetVex(G,w)，NULL，NULL；if(first)/w是v的第一个未被访问的邻接顶点 Tlchild=p；first=FALSE；/是根的左孩子结点 else/w是v的其它未被访问的邻接顶点 qnextsibling=p；/是上一邻接顶点的右兄弟结点 q=p；DFSTree(G,w,q)；/从第w个顶点出发深度优先遍历图G，建立子生成树q/if/DFSTree,1.理解并掌握图的深度优先搜索和广度优先搜索两种遍历算法及其性能分析；以及两种遍历所使用的辅助数据结构（栈或队列）在遍历过程中所起的作用，能够确定两种遍历所得到的顶点访问序列以及利用图的两种遍历设计算法解决简单的应用问题。2.理解并掌握生成树的概念，能画出给定的图深度优先和广度优先生成树或生成森林；作业P49：7.21,小结,
