计算机算法基础 第2版 课件 第8章 图的周游算法.pptx

1第8章 图的周游算法什么是图的周游 2图的表示 3广度优先有哪些信誉好的足球投注网站及应用 5? 无向图的二着色问题 124. 深度优先有哪些信誉好的足球投注网站及应用 17拓扑排序 32无回路有向图中最长路径问题及应用 36有向图的强连通分支的分解 43无向图的双连通分支的分解 52

2许多应用问题用图来描述，因而产生许多与图有关的算法问题。例如图的着色问题，最短路径问题等。对一个图的每个点及每条边按某种顺序进行逐一访冋的算法称为图的周游算法，是最重要的图的算法。图的周游本身不是目的，而是为解决应用问题提供快速有效的访问框架和顺序。在解决具体问题时，往往需要在周游时加入其他的操作从而得到结果。介绍两个周游算法，它们有线性复杂度，所以是最优的。如能用周游算法直接解决应用问题，算法往往是最优的。1.什么是图的周游算法

3邻接表示例153241432565541533212412123544466642212354552.图的表示 无向图 有向图

4 邻接矩阵示例1532414325612354101010101010101110100101112345123540101100000010000110100000001000000006123456 无向图 有向图

5广度优先有哪些信誉好的足球投注网站(BFS)策略初始，取图中一点s开始，访问s。第1步，逐一访问Adj(s)中所有点，v1，v2，…，vk。第2步，依次访问Adj(v1)，Adj(v2)，…，Adj(vk)中的点。访问Adj(u)中顶点v时，如果v还未被访问过，称首次访问，否则是后续访问。首次访问建立父子关系，?(v)=u。第3步，逐一访问前一步被首次访问的点的前向邻居。重复第3步直到某一步没有首次被访问的点为止。显然，第k步中被首次访问的点到点s的(最短)距离是k条边。如果从s开始的一轮BFS不能访问到图中所有点，则取一个未访问过的点，再做一轮BFS，直到所有点都被访问到。3.广度优先有哪些信誉好的足球投注网站及应用

6BFS算法简介用白、灰、黑三种颜色表示每个顶点被访问的三个阶段：即还未被访问，刚被访问，和它的所有前向邻居都已被访问。每个顶点v附两个变量，即s到v的(不加权)距离d(v)，和v的父亲指针?(v)。初始置d(v)=?，?(v)=nil，但置d(s)=0。用队列来顺序存储被首次访问的点。一开始是点s。每次循环取出队首u，并逐个访问Adj(u)中每个点v。如果v是白色，则是首次访问，置?(v)=u，d(v)=d(u)+1，把v变灰色后入队。Adj(u)中点全部访问后，u变黑色。BFS本身在后续访问时不做任何操作，但解具体问题时，可能需要一些操作。

7BFS(G(V,E),s)foreachvertexu?V–{s} //初始化开始 color(u)?White；d(u)??；?(u)?nilendforcolor(s)?Gray；d(s)?0；Q?? //先把队列清空Enqueue(Q,s) //将s进队，初始化完成whileQ?? u?Dequeue(Q) //取出队列首项 foreachv?Adj(u) ifcolor(v)=White then color(v)?Gray d(v)?d(u)+1 ?(v)?u Enqueue(Q,v) endif endfor color(u)?BlackendwhileEnd

8?

9例：

10

11

12无向图的二着色问题(BSF应用举例)：把一个无向图着色就是给每个顶点一个颜色(一个号码)使得每两个相邻点的颜色不同。一个图如果可以用k个颜色来着色，则称它可k-着色。当k?3时，判断一个图能否k-着色是NP-完全问题。2-着色问题有多项式算法。BFS可解。

13图2-着色的算法简介假设被着色的图G是个连通图。用红(Red)、蓝(Blue)两色为图着色。原BFS中灰色不用，红、蓝色表示顶点已不是白色了。原BFS中黑色不用，红点或蓝点出队后不可能再入队。距离d(u)与本题无关，省略。起始点s的颜色着为红色，即color(s)=Red.Adj(u)中点v