问题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”? 为什么“扩张”的结果一定是树？