算法课件Lecture2章节
57页1、Lecture 2 Elementary Graph Algorithms,Breadth-First Search Algorithm And Depth-First Search Algorithm, 2005 SDU 2,Breadth-first search (outline),The single source shortest-paths problem for unweighted graph The Breadth-first search algorithm The running time of BFS algorithm The correctness proof Note: We only introduce BFS for undirected graphs. But it also works for directed graphs.,Archetype for Prims minimum-spanning-tree algorithm Archetype for Dijkstras shortest-paths algorithm, 2005 SDU 3
2、,Shortest paths,Example: 3 simple paths from source s to b: , , of length 1, 2, 3, respectively. So the shortest path from s to b is . The shortest paths from s to other vertices a, e, d, c are: , , , . There are two shortest paths from s to d., 2005 SDU 4,The shortest-paths problem,Distance dv: The length of the shortest path from s to v. For example dc=2. Define ds=0. The problem: Input: A graph G = (V, E) and a source vertex sV Output: A shortest path from s to each vertex v V and the distanc
3、e dv., 2005 SDU 5,What does the BFS do?,Given a graph G = (V, E), the BFS returns: The shortest distance dv from s to v The predecessor or parent v, which is used to derive a shortest path from s to vertex v.( see back ) BFS actually returns a shortest path tree in which the unique simple path from s to node v is a shortest path from s to v in the original graph. In addition to the two arrays dv and v, BFS also uses another array colorv, which has three possible values: WHITE: represented “undis
4、covered” vertices; GRAY: represented “discovered” but not “processed” vertices; BLACK: represented “processed” vertices., 2005 SDU 6,The Breadth-First Search,The idea of the BFS: Each time, search as many vertices as possible. Visit the vertices as follows: Visit all vertices at distance 1 Visit all vertices at distance 2 Visit all vertices at distance 3 Initially, s is made GRAY, others are colored WHITE. When a gray vertex is processed, its color is changed to black, and the color of all white
《算法课件Lecture2章节》由会员E****分享,可在线阅读,更多相关《算法课件Lecture2章节》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-03-21 39页
2024-03-21 41页
2024-03-21 40页
2024-03-21 34页
2024-03-21 33页
2024-03-21 35页
2024-03-21 21页
2024-03-21 45页
2024-03-21 33页
2024-02-20 85页