南京大学：《计算机问题求解》课程教学资源（课件讲稿）图的计算机表示以及遍历

计算机问题求解-论题3-5 -图的计算机表示以及遍历 2014年09月26日

计算机问题求解 – 论题3-5 -图的计算机表示以及遍历 2014 年09 月26 日

自学检查 Breadth-first search is so named because it expands the frontier between discov- ered and undiscovered vertices uniformly across the breadth of the frontier.That is,the algorithm discovers all vertices at distance k from s before discovering any vertices at distance k +1

自学检查

12345 10100 1 2 34☑ 210111 3 0 0101 3 4 01101 5 5 11010 问题1： 你能否根据这两组图解释计算机 中最主要的图表示方式？ 123456 1 01010 0 2 2 00001 0 3 3 000011 4 010000 5 5 00010 0 6 6 00000

问题2： 我们讨论表示方法是否合 适主要根据什么？ 你能否结合上述两种方式 给以说明？ 关键操作的效率VS.存储需求

关键操作的效率 vs. 存储需求

间题3： 通常图中与应用相关的附加 信息有些什么？他们对表示 方法的选择有什么影啊？

问题4： 图的搜素是什么意思？ 为什么它是用图模型解 决问题的基本操作？ 图搜索经常被称为"遍历”(traversal))

图搜索经常被称为“遍历”(traversal)

广度与深度 在一个连通图中，选定一个起点总可以到达所有其它点， 如果我们确保任一顶点只“到达”一次，则“经过”的边不会 构成回路。 广度 优先 深度 搜索所"经过”的 优先 边构成的是原来图 的"生成树”。 Backtracking(▣朔)

 在一个连通图中，选定一个起点总可以到达所有其它点， 如果我们确保任一顶点只“到达”一次，则“经过”的边不会 构成回路。 广度与深度 搜索所“经过”的 边构成的是原来图 的“生成树”。 Backtracking(回朔) 广度 优先 深度 优先

广度优先 Given a graph G=(V,E)and a distinguished source vertex s,breadth-first search systematically explores the edges of G to "discover"every vertex that is reachable from s.It computes the distance (smallest number of edges)from s to each reachable vertex.It also produces a "breadth-first tree"with root s that contains all reachable vertices.For any vertex vreachable froms,the simple path in the breadth-first tree from s tov corresponds to a"shortest path"from s to v in G,that is,a path containing the smallest number of edges.The algorithm works on both directed and undirected graphs. 两个关键的动词

广度优先 两个关键的动词

问题5： 图搜索时用什么办法来跟 踪搜索的进度？

BFS(G,s) (b) 1 0 11 for each vertex u E G.V-{s} 2 u.color WHITE 3 u.d =oo 4 u.π=NIL (d) Q t x v 5 s.color GRAY 122 222 6 s.d=0 7 S.π=NL 8 9=0 9 ENQUEUE(O,s) Q x v u Q v uy 10 223 233 while O≠0 11 DEQUELECO 12 foreach v∈G.Adilul 13 if v.color =WHITE g h 14 v.color GRAY 33 15 v.d u.d+1 16 v.π=4 问题6： 17 ENQUEUE(O,v) 18 u.color BLACK 在何处体现”frontier expansion”? 为什么“扩张”的结果一定是树？