• 1. 数据结构与算法 ---第二十讲北方民族大学 计算机科学与工程学院 王伦津 研究员图的遍历
  • 2. 20、图的遍历深度优先遍历和广度优先遍历 掌握图的深度优先和广度优先遍历的性质和方法,以及基于邻接矩阵和邻接表存储结构的递归和非递归的算法实现
  • 3. 目 录20.1 概述 20.2 深度优先遍历 20.3 深度优先遍历的性质 20.4 广度优先遍历 20.5 广度优先遍历的性质
  • 4. 20、 图的遍历 从这节起,我们介绍图的一些重要操作的实现,包括遍历、拓扑排序、关键路径等。另有一些重要操作,如最短路径问题、最小生成树问题,由于主要难点在于算法,所以我们安排在后面的算法设计章节中介绍。 图的遍历与树的遍历一样具有十分重要的作用,图的许多其他操作(算法)都与遍历相关。
  • 5. 20.1 概述 图的遍历的含意是,从图中某结点出发,按某既定方式访问图中各个可访问到的结点,使每个可访问到的结点恰被访问一次。  图的遍历方式有两种:深度优先与广度优先方式,分别对应于树的先根遍历与层序遍历。 树中不存在回路,但图中可能有回路。因此,当沿回路进行扫描时,一个结点可能被扫描到多次,可能导致死循环。为了避免这种情形,在遍历中,应为每个结点设立一个访问标志,每扫描到一个结点,要检查它的访问标志,若标志为“未访问”,则按正常方式对其进行处理(如访问或转到它的邻接点等),否则放过它,扫描下一个结点。
  • 6. 访问标志的设置有两种方法: ①在描述图结的记录中增设一个访问标志位。这种方法的优点是,访问“访问标志”的方法与访问结点的方法一致。如果访问标志需要与图结构同生命期,则这种方法比较合适。但是,若访问标志要重复使用,就必须先重新初始化访问标志。如果图结点的存储不利于顺序访问,这往往也是个遍历问题! ②另设一个“访问数组”,令它的每个元素对应于一个图结点访问标志。这种方法的访问标志很容易多次初始化。
  • 7. 从图中某一结点出发,一趟只能遍历到它所在的极大连通分量中的结点,要想遍历到图中各结点,需进行多趟遍历(每趟遍历一个极大连通分量)。该过程可描述为:     for (图中每个结点v) if (v尚未被访问过) 从v出发遍历该图; 下面只考虑从一点出发遍历,因此有可能会出现遍历不到的点。即那些初始点无路径可达的点,是遍历不到的。
  • 8. 20.2 深度优先遍历 (一) 遍历规则 从图中某结点v0出发,深度优先遍历(DFS: Depth First Search)图的规则为: ·访问v0; ·对v0的各个出点v01,v02,…,v0m,每次从它们中按一定方式(也可任选)选取一个未被访问过的结点,从该结点出发按深度优先遍历方式遍历。  显然,因为我们没有规定对出点的遍历次序,所以,图的深度优先遍历结果一般不唯一。
  • 9. 例如,对图 20‑1给出的有向图与无向图,一些遍历结果(结点访问次序)为: 左图:从1出发:1,2,4,5;或1,5,2,4 从2出发:2,1,5,4;或2,4,1,5 右图:从a出发:a,b,c,d;或a,b,d,c; … … 12543abcd图20‑ 1一个有向图(左)和无向图
  • 10. 1. 一般算法 下面考虑深度优先遍历的递归实现的一般方法(存储结构无关)。 图的深度优先遍历与二叉树的前序遍历相似。不同之处有:①二叉树每个结点至多有两个可达邻接点(左右儿子),而图的可达邻接点数目不定; ②对二叉树,沿可达邻接点搜索时不会发生回绕,但对图,若不加特别控制,就有可能回绕。 下面是图的深度优先遍历递归算法的一般性描述。如果要另设一个数组作为访问标志,则该数组要在递归过程(函数)之外初始化为“未访问”。 (二)递归实现方法
  • 11. long DFS(图g,结点v0) { //图深度优先遍历递归算法。从结点v0出发,深度优先遍历图g,返回访问到的结点总数 int nNodes; //寄存访问到的结点数目  访问v0; 为v0置已访问标志; nNodes=1; 求出v0的第1个可达邻接点v; while (v存在) { if (v未被访问过) nNodes=nNodes+DFS(g,v); 求出v0的下个可达邻接点v; } return nNodes; } 
  • 12. 12543 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 所示图的邻接矩阵g1 1 2 1 3 0 4 1 5 1 图 20‑1有向图访问标识数组 visited1245输出数组 resu例如从1点深度优先遍历,先把1设置访问标志,并置入输出数组resu,然后从邻接矩阵的第一行,扫描各列,找到最近的邻接点2,将其设置访问标志,并进入输出数组,接着从邻接矩阵的2行扫描,找到第一个构成边的点是1,检查访问标识数组,发现1已经访问过,跳过,找第二个构成边 的点4,设置访问标识,进入输出数组,再从邻接矩阵的第4行扫描,寻找构成边的点,除1外在无其他点,返回2行,继续寻找,也无新点,返回1,找到5,将5置访问标志,进入输出数组,1行再无其他新点,遍历结束,返回遍历元素个数为4 。
  • 13. 2.邻接矩阵实现 这里我们为了突出主题、简化问题,假定图是用一般的邻接矩阵存储,邻接矩阵用简单的二维数组表示(静态),用0和1分别表示无边和有边。图结点用自然数编号。 long DFS1(int g[][CNST_NumNodes], long n, long v0, char *visited,long *resu,long &top ) {//深度优先遍历图(递归)。图g为邻接矩阵,结点编号为 0~n. 返回实际遍历到的结点数目 //visited是访问标志数组,调用本函数前,应为其分配空间并初始化为全0(未访问) //resu为一维数组,用于存放所遍历到的结点的编号,调用本函数前,应为其分配空间
  • 14. long nNodes, i;  nNodes=1; resu[top++]=v0; //将访问到的结点依次存于resu[] visited[v0]=1; //为v0置已访问标志 for (i=0; i是边 if (!visited[i]) //若结点i未被访问过 nNodes = nNodes+DFS1(g, n, i, visited,resu); //从i起深度优先遍历图 } return nNodes; } 
  • 15. A 如果不想让visited或top做为函数参数,也可以在函数中将其定义为static型量。但是,这样的程序是不可再入的,即函数再次被调用时,static型的量也不重新初始化,造成错误!   上面函数中的参数visited和top实质上是中间变量,只是为了避免在递归调用时重新初始化而放在参数表中,造成使用的不方便,为此,做个包装程序: long DFS1(int g[][CNST_NumNodes], long n, long v0, long *resu ) { char *visited; long top=0; visited = new char[n]; for (long i=0; i
  • 16. 1254312452b5^1d4^5^1^a1c2e3f4^5对应的邻接表图 20‑2有向图1 1 2 1 3 0 4 1 5 1访问标识数组 visited输出数组 resu地址起终权信息链a12bb15∧c21dd24∧e35∧f41∧ 邻接表边PNodes[] 终点2作为下次的始点,由于1点已访问过,跳过,找到4,记标识,送输出,4有作为新的始点重复上述过程
  • 17. 3.邻接表深度优先遍历的实现 template long DFS2(TGraphNodeAL *nodes,long n,long v0, char *visited, long *resu,long &top) {//深度优先遍历用邻接表表示的图。nodes是邻接表的头数组,n为结点个数(编号为0~n)。 //v0为遍历的起点。返回实际遍历到的结点的数目。 //visited是访问标志数组,调用本函数前,应为其分配空间并初始化为全0(未访问) //resu为一维数组,用于存放所遍历到的结点的编号,调用本函数前,应为其分配空间  long nNodes, i; TGraphEdgeAL *p;  nNodes=1;
  • 18. resu[top++]=v0; //将访问到的结点依次存于resu[] visited[v0]=1; //置v0为“已访问”标志 p = nodes[v0].firstOutEdge; //求出v0的第一个出点p while (p!=NULL) { if (!visited[p->endNo] ) //若p未访问,则从p出发深度优先遍历 nNodes = nNodes+DFS2(nodes, n, p->endNo, visited, resu,top); p = p->next; //令p指向v0的下个出点 } return nNodes; } 与邻接矩阵的情况类似,也可以对该程序“包装”,以隐蔽visited和top。
  • 19. (三) 非递归实现方法 1.一般方法 下面考虑深度优先遍历的非递归实现的一般方法(存储结构无关)。 图的深度优先遍历的非递归实现,仍然与二叉树的前序遍历非递归实现相似。不同之处有:①二叉树每个结点至多有两个可达邻接点(左右儿子),而图的可达邻接点数目不定,因此,当结点重新出现在栈顶时,不能一定出栈,而是要根据它的各出点是否都已被访问过来决定(是则出栈);②对二叉树,沿可达邻接点搜索时不会发生回绕,但对图,若不加特别控制,就有可能回绕。
  • 20. long DFS_NR(图g,结点v0) { //图深度优先遍历非递归算法。从结点v0出发,深度优先遍历图g,返回访问到的结点总数 int nNodes; //寄存访问到的结点数目 访问v0; 为v0置已访问标志; v0进栈S; nNodes=1; 求出v0的第1个可达邻接点v; 深度优先遍历非递归算法的一般性描述。
  • 21. while (栈S不空) { v = 栈S顶部元素; 求v的下个未访问过的出点i; 访问i; 为i置已访问标志; i进栈S; nNodes++;   if (v已无未被访问过的出点) 出栈; } return nNodes; }  上面的伪码描述与具体的数据结构无关。下面的程序分别给出了针对邻接矩阵与邻接表的算法模型。
  • 22. 2.邻接矩阵实现 long DFS1_NR(int g[][CNST_NumNodes], long n, long v0, long *resu ) {//深度优先遍历图(非递归)。图g为邻接矩阵, 结点编号为0~n. 返回实际遍历到的结点数目 //resu为一维数组,用于存放所遍历到的结点的 编号,调用本函数前,应为其分配空间 long nNodes, i, v; long top; char *visited; long *s; visited = new char[n]; for (i=0; i
  • 23. top++; s[top]=v0; while (top!=0) { v=s[top]; for (i=0; i是边 if (!visited[i]) //若结点i未被访问过 { resu[nNodes++]=i; //将访问到的结点依次存于resu[] visited[i]=1; //为i置已访问标志 top++; s[top]=i; //i进栈 break; } if (i==n) top--; //若v已无未访问到的出点,则将其退栈 }//while return nNodes; }
  • 24. 下面给出初始结点为1时,得进出栈的过程:15224111进栈 ,1出栈;2进栈,5进栈,5出栈,2出栈,1进栈,4进栈,4出栈,1出栈。遍历结果为 1,5,2,4
  • 25. 20.3深度优先遍历的性质 深度优先遍历有许多重要而有趣的性质,利用它们可以获得有关图的更多的信息。我们这里作一简单介绍。 (一) 深度优先生成树与单源路径 在深度优先遍历中,如果将每次“前进”(纵深)路过的(将被访问的)结点和边都记录下来,就得到一个子图,该子图为以出发点为根的树,称为深度优先生成树。
  • 26. 如果从图的多个结点出发才能遍历到所有结点,则图的深度 优先遍历树有多棵,从而构成森林,称为深度优先生成森林。 显然,由图得到深度优先生成树,相当于对图“层次”化,使图中每个结点都有一个层次号。 此外,从v0出发深度优先遍历树,同时也产生v0到各结点的路径。例如,图 20‑2(a)的出发点为1的深度优先生成树如图 20‑2(b). (a) 有向图(b) 深度优先生成树图 20-2‑ 深度优先遍历性质说明1254361254361/122/53/47/86/119/10
  • 27. (二) 时间戳 在遍历中,对每个结点v,定义从第一次“发现”(即第一次遇到,开始遍历)它的时刻为它的发现时间,记为S(v),定义遍历完v的时刻为v的完成时间,记为E(v)。这两种时间都称v的时间戳。一般情况下,用遍历中“路过”(包括回退)的结点数表示时间。图 20‑2(b)中,结点旁边的数字“a/b”表示对应结点的开始时间和完成时间分别为a和b(针对(a)的从1出发的深度优先遍历)。 时间戳的差E(v)-S(v)可用在推算深度优先遍历的进行情况,做为遍历的启发信息,指导遍历算法尽快发现目标。
  • 28. (三) 遍历括号 某结点v的深度优先遍历括号定义为: (v X1 X2 … Xm v) 这里,Xi为v的出点中,可从v出发直接访问到的各结点的遍历括号。i=1,…,m,m≥0。 例如,图20‑2(b)的结点1的遍历括号为:按时间戳有 (1 (2 (4 4) 2) (5 (3 3) (6 6) 5) 1) 遍历括号实质上是广义表,它完全描述了深度优先遍历的过程及深度优先遍历生成树的结构,可做为深度优先遍历生成树的串行化表达式。
  • 29. 20.4广度优先遍历 (一) 图的广度优先分层 图的广度优先分层与图的广度优先遍历密切相关。另外,在许多其他问题中,也涉及到图的广度优先分层。图的广度优先分层就是要识别出图中每个结点属于的层次,即给每个结点编一个层次号。但是,图本身是非层次结构,所以,一般也无层次而言。然而,我们若只从某些关系/角度考虑问题,则就可对图分层了。
  • 30. 分层时,应先确定一个或几个参考点,将它们的层号指定为起始层(第1层)。下面给出以结点v0为参考点的图的广度优先分层的定义(非过程化),这里用Level(v)表示结点v的广度优先分层的层号: n  令Level(v0) = 1 n  对任意的v≠v0,若存在v0到v的通路,则令 Level(v)=1+MINu{ Level(u) | 是图的边} 否则令Level(v)=∞  可能在不同的路径中会有多个边到达,取其最短者,即层号低的那个。
  • 31. 例 20‑3 对图 20‑1,广度优先分层情况为: 右图:从1出发分层: 层号为1的结点:1 层号为2的结点:2,5 层号为3的结点:4 层号为∞的结点:3 右图:从2出发分层: 层号为1的结点:2 层号为2的结点:1,4 层号为3的结点:5 层号为∞的结点:3  右图:从a出发分层: 层号为1的结点:a 层号为2的结点:b,d 层号为3的结点:c 12543abcd
  • 32. (二) 图的广度优先遍历方法 从结点v0出发,广度优先遍历(Breadth/Width First Search)图的方法是,按从v0出发,对图的广度优先分层的层次号的大小次序访问结点,即先访问第一层上结点,然后访问第二层上结点,…等等,同层上结点可按邻接点次序或任意。 例如,图 20‑1中的两个图的一些广度优先遍历次序如下。 左图:从1出发广度优先遍历结果:1,2,5,4 左图:从2出发广度优先遍历:2,1,4,5 右图:从a出发广度优先遍历:a,b,d,c  从另一角度看,从v出发广度优先遍历,是先访问v,然后,对任意结点u,在访问了u之后,对u的各可达点的访问,按距u的距离(边数)大小次序进行。 显然,若图的结点是无序的(即邻接点无次序关系),则广度优先遍历次序也不是唯一的,但层次关系不颠倒。
  • 33. (三) 算法实现 1. 一般方法对于深度优先遍历,用递归方法描述是件自然的事,但广度优先遍历不然,使用递归描述反而会使问题复杂化,所以我们这里只讲非递归描述法 广度优先遍历是一种分层处理,对这种分层处理,使用队列是自然的。我们设立一个队列,任何时刻,均保证它满足下列条件: ·队中元素是已访问过的结点的可达邻接点; ·队中元素是尚未被访问过的; ·队中元素按它们所处的层次的先后排列。 这样,我们就可不断地每次从队中取出一个元素并访问之,然后再将该元素的尚未被访问过的邻接点进队,直至队空。
  • 34. 图的广度优先算法伪码描述如下: long BFS(图g, 结点v0) { //在图g中从v0出发按广度优先遍历方式遍历g,返回遍历到的结点数目 long nNodes=0; 初始化队Q; if (v0存在) { v0入Q; 置v0为已访问标志; }  while (Q不空) { 队Q头元素出队并送v; 访问v; nNodes++; //对已访问元素计数
  • 35. 求出v的第一个可达邻接点w; while (w存在) { if (w尚未被访问过) { w入Q;置w为已访问标志; } 求v的下个可达邻接点w; } return nNodes; } A 请思考,(1)如果上面的程序中不使用队列,而所用栈,那么是否正确?为什么?(2)为什么结点一入队就置已访问标志? 上面的算法描述是一般性的,并未涉及到具体的存贮结构。
  • 36. 2. 邻接矩阵实现 设图用邻接矩阵表示,则它的广度优先遍历算法如下。 long BFS1_NR(int g[][CNST_NumNodes], long n, long v0, long *nos) {//广度优先遍历(邻接矩阵):从v0出发遍历用邻接矩阵表示的图g(共n个结点) //将访问到的结点的编号存入nos(其必须在外面分配n个long型空间),返回遍历到的结点数目 long nNodes=0; long v, w,i; char *visited; TQueueSqu Q(n+1);  visited = new char[n]; for (i=0; i=0 && v0
  • 37. {Q.QPush(v0); visited[v0]=1;} while (!Q.IsEmpty()) { v = Q.QPop(); nos[nNodes]= v; //访问结点v nNodes++; for (w=0; w
  • 38. 12543 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 所示图的邻接矩阵g1 1 2 1 3 0 4 1 5 1 图 20‑1有向图访问标识数组 visited1254输出数组 nos145425
  • 39. 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);  visited = new char[n]; for (i=0; i=0 && v0<=n) Q.QPush(v0); while (!Q.Empty()) {
  • 40. v = Q.QPop(); nos[nNodes]= v; //访问结点v visited[v]=1; nNodes++; p = g[v]. firstOutEdge; while (p!=NULL) { if (!visited[p->endNo]) { Q.QPush(p->endNo); visited[p->endNo]=1; } p = p->next }//while }//while delete [] visited; return nNodes; }
  • 41. 1254312542b5^1d4^5^1^a1c2e3f4^5对应的邻接表图 20‑2有向图1 1 2 1 3 0 4 1 5 1访问标识数组 visited输出数组 nos地址起终权信息链a12bb15∧c21dd24∧e35∧f41∧ 邻接表边PNodes[] 125544
  • 42. 20.5广度优先遍历的性质 与深度优先遍历类似,广度优先遍历也有许多有用的特性。 (一) 广度优先生成树 在广度优先遍历中,如果将每次“前进”(纵深)路过的(将被访问的)结点和边都记录下来,就得到一个子图,该子图为以出发点为根的树,称为广度优先生成树。这种情况与深度优先遍历类似。 类似地,也可以给广度优先生成树结点定义时间戳。 (二) 最短路径 显然,从v0出发广度优先遍历图,将得到v0到它的各个可达点的路径。我们这里定义路径上的边的数目为路径长度。与深度优先遍历不同,广度优先遍历得到的v0到各点的路径是最短路径(未考虑边权)。
  • 43. 本章小结图的基本特征是图中元素的前驱与后继的个数都没有限制。图是最复杂的非线性结构,它的表达能力也最强,前面介绍的线性结构、树等均是它的特例。 图的存储方式一般有两类:用边的集合表示图和用链接关系表示图。其中,边的集合方式有邻接矩阵,链接方式有邻接表、十字链表和邻接多重表等。 图结构的接口主要有:求某结点的各入点/出点,求某结点的各入边/出边、遍历(深度优先和广度优先)。
  • 44. 思考与练习125436abcd1、给出下列有向图和无向图的深度优先和广度优先遍历结果。2、 叙述增加新顶点和删除某顶点的过程。