数据结构-图的遍历.ppt

《数据结构-图的遍历.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图的遍历深度优先搜索广度优先搜索图的遍历小结和作业复习课堂练习复习-图的存储结构BACDFE复习-图的存储结构BACDFE012345ABCDEF14043525011253复习-图的存储结构ABECD复习-图的存储结构ABECD01234ABCDE1430122复习-图的存储结构ABECD0101234ABCDE32034复习-图的存储结构例aecbd1234acdb5e121434323552^^^^^markivexilinkjvexjlink复习-图的存储结构ABCABC012∧0121∧02∧∧20∧∧存储结构的比较邻接矩阵可用于D

2、G、UDG、DN、UDN邻接表可用于DG、UDG、DN、UDN十字链表用于DG和DN邻接多重链表用于UDG和UDN一、应用范围存储结构的比较邻接矩阵:n+n2邻接表用于DG和DN：n+e或者n+2e；用于UDG和UDN：n+2e十字链表:n+e邻接多重链表:n+e二、存储空间存储结构的比较三、对操作的支持1、对顶点的访问LocateVex(G,u);//返回u的位置GetVex(G,v);//返回v的值。PutVex(&G,u,value);//对u赋值value。存储结构的比较2、插入和删除顶点都要对存放顶点数组元素的操作但是对邻接矩阵，还

3、要修改邻接矩阵InsertVex(&G,v);//在图G中增添新顶点v。DeleteVex(&G,v);//删除G中顶点v及其相关的弧。存储结构的比较3、插入和删除弧InsertArc(&G,v,w);DeleteArc(&G,v,w);存储结构的比较邻接矩阵：修改边（以及）邻接表：无向图，修改两个顶点的链表；有向图，修改一个（或两个）顶点的链表十字链表：涉及两个链表多重邻接表：涉及两个链表存储结构的比较4、邻接点FirstAdjVex(G,v);//返回v的“第一个邻接点”。若该顶点//在G中没有邻接点，则返回“空”。N

4、extAdjVex(G,v,w);//返回v的（相对于w的）“下一个邻接//点”。若w是v的最后一个邻接点，则//返回“空”。存储结构的比较邻接矩阵：第v行邻接表：第v个链表十字链表：第v个链表多重邻接表：第v个链表存储结构的比较邻接矩阵：第v行邻接表：第v个链表十字链表：第v个链表多重邻接表：第v个链表4、邻接边邻接点函数的实现012345ABCDEF14043525011253FirstAdjVex(G,v);//返回第1个邻接点的位置，没有邻接点，返回-1。NextAdjVex(G,v,w);//返回w后面的邻接点的位置。邻接点函数的实

5、现intfirstAdjVex(ALGraghG,intv){p=G.vertices[v].firstarc;//v的第1个邻接点if(!p)return-1;//无邻接点returnp->adjvex;}邻接点函数的实现intnextAdjVex(ALGraghG,intv,intw){p=G.vertices[v].firstarc;//v的第1个邻接点while(p&&p->adjvex!=w)p=p->nextarc;if(p)p=p->nextarc;//w之后的下一个邻接点if(p)returnp->adjvex;elseret

6、urn-1;}用C语言描述存储结构1、图的二个参数：顶点个数边数（弧数）Vertex(Vertices)，vexnumEdge(arc)，arcnum，edgenum2、图的第三个参数：图的类型GraphKind={DG,UDG,DN,UDN}图的遍历定义：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。用途：是解决图的连通性、拓扑排序和求关键路径等算法的基础。深度优先搜索广度优先搜索分类：深度优先搜索SG1SG2SG3W1、W2和W3均为V的邻接点，SG1、SG2和SG3分别为含顶点W1、W2和W3的子图

7、。Vw1w3w2深度优先搜索SG1SG2SG3Vw1w3w2访问顶点V;for(W1、W2、W3)若邻接点Wi未被访问，则从它出发进行深度优先搜索历。深度优先搜索-连通图深度遍历序列：V1V2V4V5V3V7V6V8V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8深度优先搜索V1V2V4V5V3V7V6V8V4V6V8V2V5V1V3V7深度优先搜索V1V2V4V3V7V6V8V1V2V4V3V7V6V8深度优先搜索Vw1w8w3w7w6w2w5w4w1w8w3w7w6w2w51、从深度优先搜索遍历连通图的过程类

8、似于树的先根遍历2、对图G深度优先搜索得到的顶点序列不是唯一的？3、搜索过程中经过的边和所有的顶点构成了图的一棵生成树。4、如何判别V的邻接点是否被访问？为每个顶点