计算机问题求解（PPT讲稿）图的计算机表示以及遍历

计算机问题求解-论题3-6 图的计算机表示以及遍历 2018年10月25日

计算机问题求解 – 论题3-6 -图的计算机表示以及遍历 2018年10月25日

12345 3-4Z210111 2345 301010 401101 问题1 你能否根据这两组图解释计算机 中量主要的图表示方式 3000011 4|010000 5000100 00001

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

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

公 图中与应周关期 侗恳有么?他们网求示 方法的逝有么影腐?

问题49 图的搜蒙是什么意恩? 为什么它是用图模型解 决题的基本操作? 图搜索经常被称为“遍历"( traversal)

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

广度优先 Given a graphG=(,E)and a distinguished source vertex s, breadth-first search systematiclly 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 v reachable from s, the simple path on both directed and undirected graphs 两关键动H0W?

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

广度优先 G6定是树址i t reachable from s. It computes the distance (sm number of edges) from s in the breadth-first tree from s to v corresponds to a"shortest path"from s to u 定最短吗?

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

问题5 图楼索时用什么办法来跟 踪拽索的进度? 白=》灰=》黑

白=》灰=》黑

BES(G, S) I for each vertex uE G V-s 234 u color= WHITE 5 s color= gray 问题6 8Q=6 队列的使用,起到了什么作用? 9 ENQUEUE(.)链表 10lile≠ u= dEqueue(Q) 实现了系统地探索”,达成了 12 for each v∈GAdd “发现每一个” if v, color== WHITE v color= grAY 16 ENQUEUE(Q, v) 18 u color= BlACK

链表

BES(G, S) I for each vertex uE G V-s 234 u color= WHITE U. NIL 5 s color= gray 问题7: 7 SI= NIL 8Q=0 T,起到了什么作用? 9 ENQUEuE(Q 10lile≠ I1 W= DEQUEUE(Q 除了s节点的前驱是m外,每个 12 for each v∈GAdd if v, color== WHITE 节点,有且仅有一个“前驱节点” v color= grAY 任意节点v,沿其wm,必定找到 16 条从s到v的路径Pat ENQUEUE(Q, v) 18 u color= BlACK