数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源10图的深度优先搜索
6页,图的遍历,图的遍历: 从图中某一顶点出发遍历图中其余顶点,且使每一顶点仅被访问一次 算法设计需要考虑三个问题: 算法的参数要指定访问的第一个顶点; 要考虑遍历路径可能出现的死循环问题; 要使一个顶点的所有邻接顶点按照某种次序被访问。,53 图的遍历,遍历图的基本方法: 深度优先搜索DFS( Depth First Search ) 广度优先搜索BFS ( Breadth First Search ) 图的任一顶点都可能和其余顶点相邻接,且可能存在回路,因此在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点,为了避免重复访问, 可设置一个标志顶点是否被访问过的辅助数组visited ,它的初始状态为 0,在图的遍历过程中,一旦某一个顶点vi 被访问,就立即让 visited i 置为 1,防止它被多次访问,连通图的深度优先搜索遍历DFS (Depth First Search),基本思想 先访问图中某一起始顶点v ,然后由v 出发,访问它的任一邻接顶点 w1 ;再从w1 出发,访问与w1 邻接但还没有访问过的顶点w2 ;然后再从w2 出发,进行类似的访问, 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u 为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。,深度优先搜索遍历过程示例,5,8,深度优先搜索遍历序列为 v0、 v1、 v3、 v7、 v4、 v2、 v5、 v6,/邻接矩阵表示图的深度优先搜索算法 /从第i个顶点出发 int visitedNAX_VEX=0; void Dfs_m( Mgraph *G,int i) printf(“%3c“,G-vexsi); /*访问顶点vi*/ visitedi=1; for (j=0;jarcsij=1) ,问题:请大家思考 从第i个顶点出发深度优先遍历以邻接表表示的图的算法。 (这句话可以在微课的时候以动画形式飞入,不一定放在ppt上面),
《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源10图的深度优先搜索》由会员E****分享,可在线阅读,更多相关《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源10图的深度优先搜索》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页