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

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

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

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"discover every vertex that is reachable from 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 vrechable froms,the simple path in the breadth-first tree froms tocorresponds to a"shortest path"froms tov in G,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： 图搜索时用什么办法来跟 踪搜索的进度？ 白=》灰=》黑

白=》灰=》黑

BFS(G.s) 1 for each vertex u G.V-{s 2 u.color WHITE 3 4 5 s.color GRAY 6 问题6： 7 8 =0 队列的使用，起到了什么作用？ 9 ENQUEUE(O,s) 链表 10 while O≠g 11 =DEQUEUE(O) 实现了”系统地探索”，达成了 12 for each v∈G.Adju “发现每一个” 13 if v.color =WHITE 14 v.color GRAY 15 16 17 ENQUEUE(O,V) 18 u.color BLACK

链表

BFS(G,s) 1 for each vertex u G.V-{s 2 u.color WHITE 3 4 M.π=NIL 5 S.color GRAY 6 问题7： 7 S.π=NIL 8 2=0 u.T,起到了什么作用？ 9 ENQUEUE(O,s) 10 while O≠g 11 =DEQUEUE(O) 除了s节点的前驱是nil外，每个 12 for each v∈G.Adju 节点，有且仅有一个“前驱节点” 13 if v.color =WHITE 14 v.color GRAY 15 任意节点V,沿其V.T,必定找到 16 V.π=M 一条从s到v的路径Path 17 ENQUEUE(O,v) 18 u.color BLACK