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

计算机问题求解一论题3-7 -图的计算机表示以及遍历 2022年10月26日

计算机问题求解 – 论题3-7 -图的计算机表示以及遍历 2022年10月26日

12345 1 0100 1 2 34☑ 21 0111 3 01010 3 4 011 01 5 11010 问题1： 你能否根据这两组图解释计算机 中最主要的图表示方式？ 123456 4☑ 1 010100 2 2000010 3 5☑ 3 000011 4 4010000 5 5 000100 6 6 000001

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

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

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

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

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

广度优先 Given a graphG=(V.E)and a distinguished source vertex s,breadth-first search systematically explores the edges of Gto"discoverevery 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 vertexrechable froms,the simple path in the breadth-first tree froms to corresponds to ashortest path"froms tov n,that is,a path containing the smallest number of edges.The algorithm works on both directed and undirected graphs 两组关键的动词 How?

广度优先 两组关键的动词 How？

广度优先 Given a graph G=(V,E)and a disting 一定是棵树 adth-first search systematically explores the edges of 吗？ ex that is reachable from s.It computes the distance (sm number of edges)from s to each reachable vertex.It also produces a"breadth-first tree"with roots that contains all reachable vertices.For any vertex v reachable from s,the simple path in the breadth-first tree from s to v corresponds to a"shortest path"from s tov in G,that is,a path containing the smallest number of edges.algorithm works on both directed and undirected graphs. 定最短吗？ 显然？

广度优先 一定是棵树 吗？ 一定最短吗？ 显然？

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

白➔灰➔黑

a (b) 在将算法思想实现为程序时，需要提供 0 哪些数据结构进行过程控制？中间结果 保存？最终结果展示？ (c) x (d) t x v 节点的颜色 2 122 2 222 优先)队列控制 (e) x v u ( y ny 223 233 距离的记录 (g) Q (h) 0 33 3 生成树中父子关系

在将算法思想实现为程序时，需要提供 哪些数据结构进行过程控制？中间结果 保存？最终结果展示？ 节点的颜色 （优先）队列控制 距离的记录 生成树中父子关系

BFS(G.s) 1 for each vertex u G.V-fs 2 u.color WHITE BFS算法框架： 3 u.d=oo 4 u.π=NIL 1)图节点V-s初始化 5 s.color GRAY 2)s节点初始化 6 s.d=0 3)遍历控制初始化（队列） 7s.π=NL 4)遍历 8 9=0 9 ENQUEUE(O.S) 4.1)提取队列头节点 10 while O≠g 4.2)遍历该节点的邻接点 11 =DEQUEUE(O) 4.2.1)处理白节点的颜色、距离、父子关系 12 for each v∈G.Adi[w 4.2.1)白节点入队 13 if v.color =WHITE 4.3)修改该节点颜色 14 v.color GRAY 15 v.d =u.d+1 16 v.π=W 实现了”系统地探索”，达成了 17 ENQUEUE(O,v) “发现每一个” 18 u.color BLACK

BFS算法框架： 1）图节点V-s初始化 2）s节点初始化 3）遍历控制初始化（队列） 4）遍历 4.1）提取队列头节点 4.2）遍历该节点的邻接点 4.2.1）处理白节点的颜色、距离、父子关系 4.2.1）白节点入队 4.3）修改该节点颜色