图的遍历(深度优先遍历和广度优先遍历_)

1、数据结构与算法 -第二十讲,王伦津 研究员,图的遍历,20、图的遍历深度优先遍历和广度优先遍历,掌握图的深度优先和广度优先遍历的性质和方法，以及基于邻接矩阵和邻接表存储结构的递归和非递归的算法实现,目 录,20.1 概述 20.2 深度优先遍历20.3 深度优先遍历的性质 20.4 广度优先遍历 20.5 广度优先遍历的性质,20、 图的遍历,从这节起，我们介绍图的一些重要操作的实现，包括遍历、拓扑排序、关键路径等。另有一些重要操作，如最短路径问题、最小生成树问题，由于主要难点在于算法，所以我们安排在后面的算法设计章节中介绍。 图的遍历与树的遍历一样具有十分重要的作用，图的许多其他操作（算法）

2、都与遍历相关,20.1 概述,图的遍历的含意是，从图中某结点出发，按某既定方式访问图中各个可访问到的结点，使每个可访问到的结点恰被访问一次。 图的遍历方式有两种：深度优先与广度优先方式，分别对应于树的先根遍历与层序遍历。 树中不存在回路，但图中可能有回路。因此，当沿回路进行扫描时，一个结点可能被扫描到多次，可能导致死循环。为了避免这种情形，在遍历中，应为每个结点设立一个访问标志，每扫描到一个结点，要检查它的访问标志，若标志为“未访问”，则按正常方式对其进行处理（如访问或转到它的邻接点等），否则放过它，扫描下一个结点,访问标志的设置有两种方法： 在描述图结的记录中增设一个访问标志位。这种方法的优

3、点是，访问“访问标志”的方法与访问结点的方法一致。如果访问标志需要与图结构同生命期，则这种方法比较合适。但是，若访问标志要重复使用，就必须先重新初始化访问标志。如果图结点的存储不利于顺序访问，这往往也是个遍历问题！ 另设一个“访问数组”，令它的每个元素对应于一个图结点访问标志。这种方法的访问标志很容易多次初始化,从图中某一结点出发，一趟只能遍历到它所在的极大连通分量中的结点，要想遍历到图中各结点，需进行多趟遍历（每趟遍历一个极大连通分量）。该过程可描述为： for (图中每个结点v) if (v尚未被访问过) 从v出发遍历该图,下面只考虑从一点出发遍历，因此有可能会出现遍历不到的点。即那些初始

4、点无路径可达的点，是遍历不到的,20.2 深度优先遍历,一) 遍历规则 从图中某结点v0出发，深度优先遍历（dfs: depth first search）图的规则为： 访问v0； 对v0的各个出点v01，v02，v0m，每次从它们中按一定方式（也可任选）选取一个未被访问过的结点，从该结点出发按深度优先遍历方式遍历。 显然，因为我们没有规定对出点的遍历次序，所以，图的深度优先遍历结果一般不唯一,例如，对图 201给出的有向图与无向图，一些遍历结果（结点访问次序）为： 左图：从1出发：1，2，4，5；或1，5，2，4 从2出发：2，1，5，4；或2，4，1，5 右图：从a出发：a，b，c，d；或

5、a，b，d，c;,图20 1一个有向图（左）和无向图,1. 一般算法 下面考虑深度优先遍历的递归实现的一般方法（存储结构无关）。 图的深度优先遍历与二叉树的前序遍历相似。不同之处有：二叉树每个结点至多有两个可达邻接点（左右儿子），而图的可达邻接点数目不定； 对二叉树，沿可达邻接点搜索时不会发生回绕，但对图，若不加特别控制，就有可能回绕。 下面是图的深度优先遍历递归算法的一般性描述。如果要另设一个数组作为访问标志，则该数组要在递归过程（函数）之外初始化为“未访问,二）递归实现方法,long dfs(图g，结点v0) /图深度优先遍历递归算法。从结点v0出发，深度优先遍历图g，返回访问到的结点总数

6、 int nnodes; /寄存访问到的结点数目 访问v0; 为v0置已访问标志; nnodes=1; 求出v0的第1个可达邻接点v; while (v存在) if (v未被访问过) nnodes=nnodes+dfs(g,v); 求出v0的下个可达邻接点v; return nnodes;,1 2 3 4 5 1 0 1 0 0 1 2 1 0 0 1 0 3 0 0 0 0 1 4 1 0 0 0 0 5 0 0 0 0 0,所示图的邻接矩阵g,1 1 2 1 3 0 4 1 5 1,图 201有向图,访问标识数组 visited,输出数组 resu,例如从1点深度优先遍历，先把1设置访问标

7、志，并置入输出数组resu，然后从邻接矩阵的第一行，扫描各列，找到最近的邻接点2，将其设置访问标志，并进入输出数组，接着从邻接矩阵的2行扫描，找到第一个构成边的点是1，检查访问标识数组，发现1已经访问过，跳过，找第二个构成边 的点4，设置访问标识，进入输出数组，再从邻接矩阵的第4行扫描，寻找构成边的点，除1外在无其他点，返回2行，继续寻找，也无新点，返回1，找到5，将5置访问标志，进入输出数组，1行再无其他新点，遍历结束，返回遍历元素个数为4,2邻接矩阵实现 这里我们为了突出主题、简化问题，假定图是用一般的邻接矩阵存储，邻接矩阵用简单的二维数组表示（静态），用0和1分别表示无边和有边。图结点用

8、自然数编号。 long dfs1(int gcnst_numnodes, long n, long v0, char *visited,long *resu，long nnodes=1; resutop+=v0; /将访问到的结点依次存于resu visitedv0=1; /为v0置已访问标志 for (i=0; i是边 if (!visitedi) /若结点i未被访问过 nnodes = nnodes+dfs1(g, n, i, visited,resu); /从i起深度优先遍历图 return nnodes;,a 如果不想让visited或top做为函数参数，也可以在函数中将其定义为sta

9、tic型量。但是，这样的程序是不可再入的，即函数再次被调用时，static型的量也不重新初始化，造成错误,上面函数中的参数visited和top实质上是中间变量，只是为了避免在递归调用时重新初始化而放在参数表中，造成使用的不方便，为此，做个包装程序： long dfs1(int gcnst_numnodes, long n, long v0, long *resu ) char *visited; long top=0; visited = new charn; for (long i=0; in; i+) visitedi=0; long num=dfs1( g, n, v0, visite

10、d, resu, top ); delete visited; return num;,对应的邻接表,图 202有向图,1 1 2 1 3 0 4 1 5 1,访问标识数组 visited,输出数组 resu,邻接表边,p,nodes,终点2作为下次的始点，由于1点已访问过，跳过，找到4，记标识，送输出，4有作为新的始点重复上述过程,3邻接表深度优先遍历的实现 template long dfs2(tgraphnodeal *nodes,long n,long v0, char *visited, long *resu,long,resutop+=v0; /将访问到的结点依次存于resu vi

11、sitedv0=1; /置v0为“已访问”标志 p = nodesv0.firstoutedge; /求出v0的第一个出点p while (p!=null) if (!visitedp-endno ) /若p未访问，则从p出发深度优先遍历 nnodes = nnodes+dfs2(nodes, n, p-endno, visited, resu,top); p = p-next; /令p指向v0的下个出点 return nnodes; 与邻接矩阵的情况类似，也可以对该程序“包装”，以隐蔽visited和top,三) 非递归实现方法 1一般方法 下面考虑深度优先遍历的非递归实现的一般方法（存储结

12、构无关）。 图的深度优先遍历的非递归实现，仍然与二叉树的前序遍历非递归实现相似。不同之处有：二叉树每个结点至多有两个可达邻接点（左右儿子），而图的可达邻接点数目不定，因此，当结点重新出现在栈顶时，不能一定出栈，而是要根据它的各出点是否都已被访问过来决定（是则出栈）；对二叉树，沿可达邻接点搜索时不会发生回绕，但对图，若不加特别控制，就有可能回绕,long dfs_nr(图g，结点v0) /图深度优先遍历非递归算法。从结点v0出发，深度优先遍历图g，返回访问到的结点总数 int nnodes; /寄存访问到的结点数目 访问v0; 为v0置已访问标志; v0进栈s； nnodes=1; 求出v0的第

13、1个可达邻接点v,深度优先遍历非递归算法的一般性描述,while (栈s不空) v = 栈s顶部元素； 求v的下个未访问过的出点i； 访问i; 为i置已访问标志; i进栈s； nnodes+; if (v已无未被访问过的出点) 出栈； return nnodes; 上面的伪码描述与具体的数据结构无关。下面的程序分别给出了针对邻接矩阵与邻接表的算法模型,2邻接矩阵实现 long dfs1_nr(int gcnst_numnodes, long n, long v0, long *resu ) /深度优先遍历图(非递归）。图g为邻接矩阵， 结点编号为0n. 返回实际遍历到的结点数目 /resu为一

14、维数组，用于存放所遍历到的结点的 编号，调用本函数前，应为其分配空间 long nnodes, i, v; long top; char *visited; long *s; visited = new charn; for (i=0; in; i+) visitedi=0; s = new longn+1; top=0; nnodes=0; resunnodes+=v0; /将访问到的结点依次存于resu visitedv0=1; /为v0置已访问标志,top+; stop=v0; while (top!=0) v=stop; for (i=0; i是边 if (!visitedi) /若结

15、点i未被访问过 resunnodes+=i; /将访问到的结点依次存于resu visitedi=1; /为i置已访问标志 top+; stop=i; /i进栈 break; if (i=n) top-; /若v已无未访问到的出点，则将其退栈 /while return nnodes;,下面给出初始结点为1时，得进出栈的过程,1进栈 ，1出栈；2进栈，5进栈，5出栈，2出栈，1进栈，4进栈，4出栈，1出栈,遍历结果为 1，5，2，4,20.3深度优先遍历的性质,深度优先遍历有许多重要而有趣的性质，利用它们可以获得有关图的更多的信息。我们这里作一简单介绍,一) 深度优先生成树与单源路径 在深度优

16、先遍历中，如果将每次“前进”（纵深）路过的（将被访问的）结点和边都记录下来，就得到一个子图，该子图为以出发点为根的树，称为深度优先生成树,如果从图的多个结点出发才能遍历到所有结点，则图的深度 优先遍历树有多棵，从而构成森林，称为深度优先生成森林。 显然，由图得到深度优先生成树，相当于对图“层次”化，使图中每个结点都有一个层次号。 此外，从v0出发深度优先遍历树，同时也产生v0到各结点的路径。例如，图 202(a)的出发点为1的深度优先生成树如图 202(b,a) 有向图,b) 深度优先生成树,图 20-2 深度优先遍历性质说明,二) 时间戳 在遍历中，对每个结点v，定义从第一次“发现”（即第一

17、次遇到，开始遍历）它的时刻为它的发现时间，记为s(v)，定义遍历完v的时刻为v的完成时间，记为e(v)。这两种时间都称v的时间戳。一般情况下，用遍历中“路过”（包括回退）的结点数表示时间。图 202(b)中，结点旁边的数字“a/b”表示对应结点的开始时间和完成时间分别为a和b（针对(a)的从1出发的深度优先遍历）。 时间戳的差e(v)-s(v)可用在推算深度优先遍历的进行情况，做为遍历的启发信息，指导遍历算法尽快发现目标,三) 遍历括号 某结点v的深度优先遍历括号定义为： (v x1 x2 xm v) 这里，xi为v的出点中，可从v出发直接访问到的各结点的遍历括号。i=1,m，m0。 例如，图

18、202(b)的结点1的遍历括号为：按时间戳有 (1 (2 (4 4) 2) (5 (3 3) (6 6) 5) 1) 遍历括号实质上是广义表，它完全描述了深度优先遍历的过程及深度优先遍历生成树的结构，可做为深度优先遍历生成树的串行化表达式,20.4广度优先遍历,一) 图的广度优先分层 图的广度优先分层与图的广度优先遍历密切相关。另外，在许多其他问题中，也涉及到图的广度优先分层。图的广度优先分层就是要识别出图中每个结点属于的层次，即给每个结点编一个层次号。但是，图本身是非层次结构，所以，一般也无层次而言。然而，我们若只从某些关系/角度考虑问题，则就可对图分层了,分层时，应先确定一个或几个参考点，

19、将它们的层号指定为起始层（第1层）。下面给出以结点v0为参考点的图的广度优先分层的定义（非过程化），这里用level(v)表示结点v的广度优先分层的层号： n 令level(v0) = 1 n 对任意的vv0，若存在v0到v的通路，则令 level(v)=1+minu level(u) | 是图的边 否则令level(v),可能在不同的路径中会有多个边到达，取其最短者，即层号低的那个,例 203 对图 201，广度优先分层情况为： 右图：从1出发分层： 层号为1的结点：1 层号为2的结点：2，5 层号为3的结点：4 层号为的结点：3 右图：从2出发分层： 层号为1的结点：2 层号为2的结点：1

20、，4 层号为3的结点：5 层号为的结点：3 右图：从a出发分层： 层号为1的结点：a 层号为2的结点：b，d 层号为3的结点：c,二) 图的广度优先遍历方法 从结点v0出发，广度优先遍历（breadth/width first search）图的方法是，按从v0出发，对图的广度优先分层的层次号的大小次序访问结点，即先访问第一层上结点，然后访问第二层上结点，等等，同层上结点可按邻接点次序或任意。 例如，图 201中的两个图的一些广度优先遍历次序如下。 左图：从1出发广度优先遍历结果：1，2，5，4 左图：从2出发广度优先遍历：2，1，4，5 右图：从a出发广度优先遍历：a，b，d，c 从另一角度

21、看，从v出发广度优先遍历，是先访问v，然后，对任意结点u，在访问了u之后，对u的各可达点的访问，按距u的距离（边数）大小次序进行。 显然，若图的结点是无序的（即邻接点无次序关系），则广度优先遍历次序也不是唯一的，但层次关系不颠倒,三) 算法实现 1. 一般方法对于深度优先遍历，用递归方法描述是件自然的事，但广度优先遍历不然，使用递归描述反而会使问题复杂化，所以我们这里只讲非递归描述法 广度优先遍历是一种分层处理，对这种分层处理，使用队列是自然的。我们设立一个队列，任何时刻，均保证它满足下列条件： 队中元素是已访问过的结点的可达邻接点； 队中元素是尚未被访问过的； 队中元素按它们所处的层次的先后

22、排列。 这样，我们就可不断地每次从队中取出一个元素并访问之，然后再将该元素的尚未被访问过的邻接点进队，直至队空,图的广度优先算法伪码描述如下： long bfs(图g, 结点v0） /在图g中从v0出发按广度优先遍历方式遍历g，返回遍历到的结点数目 long nnodes=0; 初始化队q; if （v0存在） v0入q; 置v0为已访问标志; while (q不空) 队q头元素出队并送v; 访问v; nnodes+; /对已访问元素计数,求出v的第一个可达邻接点w; while (w存在) if (w尚未被访问过) w入q;置w为已访问标志; 求v的下个可达邻接点w; return nnod

23、es;,a 请思考，(1)如果上面的程序中不使用队列，而所用栈，那么是否正确？为什么？(2)为什么结点一入队就置已访问标志,上面的算法描述是一般性的，并未涉及到具体的存贮结构,2. 邻接矩阵实现 设图用邻接矩阵表示，则它的广度优先遍历算法如下。 long bfs1_nr(int gcnst_numnodes, long n, long v0, long *nos) /广度优先遍历（邻接矩阵）：从v0出发遍历用邻接矩阵表示的图g（共n个结点） /将访问到的结点的编号存入nos(其必须在外面分配n个long型空间），返回遍历到的结点数目 long nnodes=0; long v, w,i; ch

24、ar *visited; tqueuesqu q(n+1); visited = new charn; for (i=0; i=0 visitedv0=1; while (!q.isempty() v = q.qpop(); nosnnodes= v; /访问结点v nnodes+; for (w=0; wn; w+) /找v的各未访问的出点 if (gvw!=0) if (!visitedw) q.qpush(w); /v的各未访问的出点进栈 visitedw=1; /while delete visited; return nnodes;,1 2 3 4 5 1 0 1 0 0 1 2 1

25、 0 0 1 0 3 0 0 0 0 1 4 1 0 0 0 0 5 0 0 0 0 0,所示图的邻接矩阵g,1 1 2 1 3 0 4 1 5 1,图 201有向图,访问标识数组 visited,输出数组 nos,3邻接表实现 针对邻接表的算法为： template long bfs2_nr(tgraphnodeal*nodes, long n, long v0, long *nos) /广度优先遍历（邻接表）：从v0出发遍历用邻接表表示的图g（共n个结点） /将访问到的结点的编号存入nos(其必须在外面分配n个long型空间），返回遍历到的结点数目 long nnodes=0; tgraphedge *p; char *visited; tqueuessqu q(n+1); v