数据结构第讲图的遍历与连通性精品文稿.ppt
《数据结构第讲图的遍历与连通性精品文稿.ppt》由会员分享,可在线阅读,更多相关《数据结构第讲图的遍历与连通性精品文稿.ppt(30页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、数据结构第讲图的遍历与连通性第1页,本讲稿共30页邻接矩阵邻接矩阵是用于描述图中顶点之间关系是用于描述图中顶点之间关系(即弧或边的即弧或边的权权)的矩阵。的矩阵。邻接表邻接表类似树的孩子链表。即对图中的每个顶点类似树的孩子链表。即对图中的每个顶点vivi建立一建立一个单链表,表中结点表示依附于该顶点个单链表,表中结点表示依附于该顶点vivi的边或弧。的边或弧。邻接点域链域数据域数据域链域表结点表头结点第2页,本讲稿共30页V1V3V2V4例:4 3 2 121113442第3页,本讲稿共30页3.3.有向图的十字链表存储表示有向图的十字链表存储表示两种结点结构:尾域tailvex头域headv
2、ex链域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 图的
3、存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径第8页,本讲稿共30页7.3 7.3 图的遍历图的遍历 从图中某一顶点出发访遍图中其余顶点,且使每一个从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次。这一过程就叫做顶点仅被访问一次。这一过程就叫做图的遍历图的遍历。通常有两条遍历图的路径:通常有两条遍历图的路径:n深度优先搜索深度优先搜索n广度优先搜索广度优先搜索第9页,本讲稿共30页1.1.深度优先搜索深度优先搜索(DFS)(DFS)基本思想:从图中某顶点V0出发,访问此顶点,然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图,直至
4、图中所有和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
5、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
6、 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)基本思
7、想:从图中某个顶点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、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;InitQu
9、eue(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 /BFSTr
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第讲图 遍历 连通性 精品 文稿
限制150内