数据结构 -深度优先搜索.ppt

《数据结构 -深度优先搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、-+/a*b-efcd先序遍历：中序遍历：-+a*b-cd/ef-+a*b-cd/ef回顾：树的遍历7.3图的遍历7.3.1深度优先搜索7.3.2广度优先搜索第七章图图的数据结构如何定义？图的遍历算法的特点是什么？图的遍历算法可否用线性结构算法来实现？若可以实现，采用哪种线性结构？问题7.3.1深度优先搜索一、原理：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点,重复上述过程，直至图中所有顶点都被

2、访问为止。假设成立的条件是什么？V0V4V3V1V2V0V2V3V1V5V4G1例：G2V1V2V4V5V3V7V6V8例：深度遍历：V1V2V4V8V5V3V6V7二、深度优先遍历过程1234567思考：遍历序列是否唯一？？V4V1V2V5V3V7V6V8深度遍历：V1V3V7V6V2V5V8V4V4V1^V5V7V6^V1V8^V2V8V2^V5V4^V7V3^V6V3^firstarcvexdataV8V7V6V5V4V3V2V1V2^adjvexnextarcV3一一对应①②③④⑤⑥⑦数据类型如何定义？？

3、三、数据类型的定义表节点的定义TypedefstructArcNode{datatypeadjvexStructArcNode*nextarc}ArcNode头节点的定义Typedefstructvnode{vetertypevexdataArcNode*firstarc}VnodeArrayvex[]ofvnode算法特点？？四、算法流程开始数组初始化vЄ点集从第v个节点递归遍历已访问过终止是是否否访问v节点置状态位返回上一轮递归已访问过WЄ点集是否是v邻接点W是否否五、递归算法见p169：算法7.4、7.5算法要点:1、设置标志位vis

4、ited[v]，并初始化为False2、主循环从第一个节点开始遍历，每遍历一个节点进行标志位的判定，即Vistited[v]为true3、循环语句for（w=FirstAdjVex（G，v）；WЄVxw=Nextadjvex（G，v，W）；）练习图G如下：V0V2V3V1V5V41、画出邻接表表示的存储结构图2、根据存储结构图写出深度优先遍历序列V1V2V4V5V3V7V6V8例：六、非递归算法（线性结构应用）1234567^…...栈底SSep进栈操作的实现：voidPush_LS(LinkStack&S,SElemTypee){p=(L

5、inkStack)malloc(sizeof(SNode));p–>data=e;p–>next=S;S=p;}StatusPop_LS(LinkStack&S,SElemType&e){if(S==NULL)returnERROR;e=S->data;p=S;S=S->next;free(p);}S^…...栈底Sp退栈操作的实现：作业图G如下：V0V2V3V1V5V41、画出邻接表表示的存储结构图2、根据存储结构图写出深度优先遍历序列3、写出递归算法的断点位置4、用栈的原理写出非递归算法，并画出数据元素进栈出栈的顺序