图的遍历

1基本图算法陈嘉庆1基本概念和运算图的运算：基本运算：初始化图插入顶点插入边（弧）修改权值删除顶点删除边（弧）求指定顶点的邻接点常用运算：遍历2图的遍历运算3图的遍历图的遍历——访问图中所有顶点一次且仅且一次。深度优先搜索遍历图的两种遍历算法广度优先搜索遍历它们对无向图，有向图都适用为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个标志数组visited[i]作为对顶点的标记，未访问时值为false，访问一次后就改为true。深度优先遍历和广度优先遍历两种方法的时间复杂度都是O(n*n)。4深度优先遍历3图的遍历3.1深度优先搜索遍历（DepthFirstSearch)深度优先遍历与深搜DFS相似，从一个点A出发，将这个点标为已访问visited[i]:=true;，然后再访问所有与之相连，且未被访问过的点。当A的所有邻接点都被访问过后，再退回到A的上一个点（假设是B），再从B的另一个未被访问的邻接点出发，继续遍历。1.基本算法从顶点v0出发深度优先搜索遍历图G的dfs(v0)描述如下：(1)访问v0；(2)依次从v0的未被访问过的邻接点出发深度遍历。6深度优先搜索——递归算法递归算法思想：首先从图G=(V,E)中某一顶点v0出发，访问任意一个和v0邻接的顶点w1，再从w1出发，再访问和w1邻接且未被访问过的任意顶点w2。然后，从w2出发进行如上访问。重复这个过程，直到某一个顶点的所有邻接点都被访问过时，回退到尚有邻接点未被访问过的顶点。再从该顶点出发，重复上述过程，直到所有顶点都被访问过为止。21746358深度优先124863752已经访问返回8所有都访问完毕了3.1深度优先搜索遍历下面以下图为例来讨论dfs算法的执行过程：调用dfs(1)9dfs(8)dfs(9)dfs(4)dfs(3)此箭头表示是从遍历运算dfs(1)中调用dfs(2)，即从顶点1直接转到2此虚箭头表示是在dfs(3)执行完毕后返回到遍历运算dfs(2)中，即从顶点3返回到267125348109dfs(1)dfs(2)dfs(5)dfs(6)dfs(7)dfs(10)在访问顶点3后，由于顶点3的邻接点已全被访问，故dfs（3）执行到此结束，应返回到调用层，即返回到dfs(2)dfs(1)包含如下两部分操作：（1）访问顶点1；（2）依次执行dfs(2)和dfs(8)3.1深度优先搜索遍历将dfs（1）执行过程中所搜索的边连接起来（有标注的边），得到一棵生成树----dfs生成树。106712534810967125348109原图及其搜索示意图dfs(1)生成树3.1深度优先搜索遍历下面讨论dfs算法的设计。为此，先回顾一下dfs(v0)的描述：(1)访问v0；(2)依次从v0的未被访问过的邻接点出发深度遍历。分析：由算法描述可知：①访问顶点v0的基本操作：可用visite(v0)简单表示。②设置访问标志数组visted[]，并约定：某顶点vi未被访问时，visted[i]==FALSE（初值）vi被访问过后，visted[i]==TRUE（初值）③求邻接点可以采用两个函数：firstadj(G,v)：返回v的第一个邻接点（号），或0（不存在时）。nextadj(G,v,w);返回v的第邻接点中处于邻接点w之后的邻接点号,或0（不存在时）11访问v0时，visted[i]=FTRUE;深度优先遍历算法递归算法开始访问V0,置标志求V0邻接点有邻接点w求下一邻接点wV0W访问过结束NYNYDFS开始标志数组初始化Vi=1Vi访问过DFSVi=Vi+1Vi==Vexnums结束NNYYvoiddfs(inti)//图用数组模拟邻接表存储，访问点i{visited[i]=true;//标记为已经访问过for(intj=1;j=num[i];j++)//遍历与i相关联的所有未访问过的顶点if(!visited[g[i][j]])dfs(g[i][j]);}主程序如下:intmain(){……memset(visited,false,sizeof(visited));for(inti=1;i=n;i++)//每一个点都作为起点尝试访问，因为不是从任何一点开始都能遍历整个图的if(!visited[i])dfs(i);……return0;}深度优先搜索——非递归算法非递归算法思想：由访问vi的邻接表转到访问vj的邻接表时，vi进栈。从栈中依次弹出结点v0,访问v0的单链表中未被访问过的的结点，在访问过程中并重复上述的入栈过程。过程如下页图示:3.1深度优先搜索遍历21746358非递归1栈3.1深度优先搜索遍历221746358非递归11栈3.1深度优先搜索遍历4221746358非递归211栈3.1深度优先搜索遍历84221746358非递归4211栈3.1深度优先搜索遍历584221746358非递归84211栈3.1深度优先搜索遍历5的邻接表空，回退8出栈584221746358非递归4211栈3.1深度优先搜索遍历584221746358非递归84211栈63.1深度优先搜索遍历3584221746358非递归684211栈63.1深度优先搜索遍历73584221746358非递归3684211栈63.1深度优先搜索遍历73584221746358非递归1栈67的邻接表空，逐一退栈3.1深度优先搜索遍历3.1深度优先搜索遍历问题：从某顶点出发是否能保证访问到所有顶点？或者说：选择一个起点调用一次dfs算法，能否实现对整个图的遍历？2.遍历整个图的算法dfs算法在应用于非连通图，或者是某些有向图时，某一次调用就不能保证访问到所有顶点。如下图所示。246125346712534810912345以3为起点根本不能遍历整个图这个非连通无向图任何一个点为起点都不能遍历整个图145233.1深度优先搜索遍历3.深度遍历算法的应用问题：（1）如何设计算法以判断给定的无向图是否是连通的？（2）如何设计算法以求解给定的无向图中的边数？（3）设计算法以判断给定的无向图是树。（4）设计算法以判断给定的有向图是以v0为根的有向树。（5）设计算法以判断图中的一个节点是否为关节点。253.1深度优先搜索遍历例1设计算法以求解无向图G的连通分量的个数。分析：对无向图G来说，选择某一顶点v执行dfs(v)，可访问到所在连通分量中的所有顶点因此，选择起点的次数就是图G的连通分量数，这可通过修改遍历整个图的算法dfs_travel来实现：每调用一次dfs算法计数一次。另外，考虑到要求求解连通分量数，因而可以将算法设计为整型函数。263.1深度优先搜索遍历4.深度遍历算法的应用二例2：设计算法，将1--n(=20,或其他数)放在一个环上，使环上任意两个相邻元素的和为质数。分析：可以用图来描述该问题：①用顶点表示一个数②若两个数的和为质数，则对应顶点之间有一条边。例如，若n=10，对应图如右所示。在这一表示下，问题转化为：求图中包含所有顶点的简单回路。如图所示的一个解。（1，2，3，4，7，6，5，8，9，10）27671253489103.1深度优先搜索遍历算法设计中需要注意的：通过在dfs算法的基础上变化而得：（1）路径的记录：需要增加变量或参数以记录路径，因此，不妨设一个数组以记录路径中的顶点序列和一个记录长度的变量。（2）若某些走法行不通，需要重来，为此，要恢复visited[i]标志。（3）需要判断首尾相接。283.1深度优先搜索遍历算法构思如下:(1)设环上已有k个元素（0≤k≤n）。(2)若kn,且不在当前路径上的顶点中存在与B[k]相邻的，则依次从余下的顶点中取出与B[k]相邻的顶点放置在B[k+1]中,转(1)。(3)若kn，而在余下的这些顶点中找不到一个与B[K]相邻的顶点，或者是虽然存在邻接点，但这些结点均已在同等条件下放置过了，因而须从环上去掉B[K]，转(1)。(4)若k=ｎ,有两种情况:(a)B[n]与B[1]相邻接,说明已求得一解,则输出求解结果,然后返回。(b)B[n]与B[1]不邻接，说明前面的放置法不行,即不构成环,因而需要重新放置，即要去掉B[n]和B[n-1]，然而转(1)。为避免遗漏某种放置，从最后往前依次用余下的顶点中的与其前面相邻接的顶点替换。采用递归方式实现如下：其中visited为标志数组，表示各结点是否在当前的路径上。29算法导论（黑书）节选3.1深度优先搜索遍历深度优先搜索所使用的策略像其名字所隐含的：只要可能，就在图中尽量深入。深度优先搜索总是对最近才发现的结点v的出发边进行探索，直到该结点的所有出发边都被发现为止。一旦结点v的所有出发边都被发现，搜索则回溯到v的前驱结点（v是经过该结点才被发现的），来搜索该前驱结点的出发边。该过程一直持续到从源结点可以达到的所有结点都被发现为止。如果还存在尚未发现的结点，则深度优先搜索将从这些未被发现的结点中任选一个作为新的源结点，并重复同样的搜索过程。该算法重复整个过程，直到图中的所有结点都被发现为止。313.1深度优先搜索遍历在对已被发现的结点u的邻接链表进行扫描时，每当发现一个结点v时，深度优先搜索算法将对这个事件进行记录，将v的前驱属性v.p设置为u。与广度优先搜索不同的是，广度优先搜索的前驱子图形成一棵树，而深度优先搜索的前驱子图可能由多棵树组成，因为搜索可能从多个源结点重复进行。设图Gπ=(V,Eπ)，其中Eπ={(v.p,v):v∈V且v.p!=NIL}。深度优先搜索的前驱子图形成一个由多棵深度优先树构成的深度优先森林。森林Eπ中的边称为树边。323.1深度优先搜索遍历像广度优先搜索算法一样，深度优先搜索算法在搜索过程中也是对结点进行涂色来指明结点的状态。每个结点的初始颜色都是白色，在结点被发现后变为灰色，在其邻接链表被扫描完成后变为黑色。该方法可以保证每个结点仅在一棵深度优先树中出现，因此，所有的深度优先树是不相交的（disjoint）。333.1深度优先搜索遍历除了创建一个深度优先搜索森林外，深度优先搜索算法还在每个结点盖上一个时间戳。每个结点v有两个时间戳：第一个时间戳v.d记录结点v第一次被发现的时间（涂上灰色的时候），第二个时间戳v.f记录的是搜索完成对v的邻接链表扫描的时候（涂上黑色的时候）。这些时间戳提供了图结构的重要信息，通常能够帮助推断深度优先搜索算法的行为。343.1深度优先搜索遍历除了创建一个深度优先搜索森林外，深度优先搜索算法还在每个结点盖上一个时间戳。每个结点v有两个时间戳：第一个时间戳v.d记录结点v第一次被发现的时间（涂上灰色的时候），第二个时间戳v.f记录的是搜索完成对v的邻接链表扫描的时候（涂上黑色的时候）。这些时间戳提供了图结构的重要信息，通常能够帮助推断深度优先搜索算法的行为。353.1深度优先搜索遍历下面是深度优先搜索算法在一个有向图上运行的过程363.1深度优先搜索遍历除了创建一个深度优先搜索森林外，深度优先搜索算法还在每个结点盖上一个时间戳。每个结点v有两个时间戳：第一个时间戳v.d记录结点v第一次被发现的时间（涂上灰色的时候），第二个时间戳v.f记录的是搜索完成对v的邻接链表扫描的时候（涂上黑色的时候）。这些时间戳提供了图结构的重要信息，通常能够帮助推断深度优先搜索算法的行为。373.1深度优先搜索遍历除了创建一个深度优先搜索森林外，深度优先搜索算法还在每个结点盖上一个时间戳。每个结点v有两个时间戳：第一个时间戳v.d记录结点v第一次被发现的时间（涂上灰色的时候），第二个时间戳v.f记录的是搜索完成对v的邻接链表扫描的时候（涂上黑色的时候）。这些时间戳提供了图结构的重要信息，通常能够帮助推断深度优先搜索算法的行为。383.1深度优先搜索遍历下面的深度优先搜索算法的伪代码将其发现结点u的时刻记录在属性u.d中，将其完成对结点u处理的时刻记录在属性u.f中。因为|V|个结点中每个结点只能有一个发现事件和一个完成事件，所有这些时间戳都处于1和2|V|之间的整数。很显然，对于每个结点u，我们有：