图的遍历深度优先遍历和广度优先遍历(2)幻灯片.ppt

图的遍历深度优先遍历和广度优先遍历第1页，共44页，编辑于2022年，星期五20、图的遍历深度优先遍历和广度优、图的遍历深度优先遍历和广度优先遍历先遍历掌握图的深度优先和广度优先遍历的性掌握图的深度优先和广度优先遍历的性质和方法，以及基于邻接矩阵和邻接表质和方法，以及基于邻接矩阵和邻接表存储结构的递归和非递归的算法实现存储结构的递归和非递归的算法实现第2页，共44页，编辑于2022年，星期五目目录录20.1概述概述20.2深度优先遍历深度优先遍历20.3深度优先遍历的性质深度优先遍历的性质20.4广度优先遍历广度优先遍历20.5广度优先遍历的性质广度优先遍历的性质第3页，共44页，编辑于2022年，星期五2020、图的遍历图的遍历 从从这这节节起起，我我们们介介绍绍图图的的一一些些重重要要操操作作的的实实现现，包包括括遍遍历历、拓拓扑扑排排序序、关关键键路路径径等等。另另有有一一些些重重要要操操作作，如如最最短短路路径径问问题题、最最小小生生成成树树问问题题，由由于于主主要要难难点点在在于于算算法法，所所以以我我们们安安排排在在后后面面的的算算法法设设计计章章节中介绍。节中介绍。图图的的遍遍历历与与树树的的遍遍历历一一样样具具有有十十分分重重要要的的作作用用，图图的的许多其他操作（算法）都与遍历相关。许多其他操作（算法）都与遍历相关。第4页，共44页，编辑于2022年，星期五20.1 20.1 概述概述 图的遍历的含意是，图的遍历的含意是，从图中某结点出发，按某既定方式访问图中从图中某结点出发，按某既定方式访问图中各个可访问到的结点，使每个可访问到的结点恰被访问一次。各个可访问到的结点，使每个可访问到的结点恰被访问一次。图的遍历方式有两种：深度优先与广度优先方式，分别对应于树的图的遍历方式有两种：深度优先与广度优先方式，分别对应于树的先根遍历与层序遍历。先根遍历与层序遍历。树中不存在回路，但图中可能有回路。因此，当沿回路进树中不存在回路，但图中可能有回路。因此，当沿回路进行扫描时，一个结点可能被扫描到多次，可能导致死循环。为行扫描时，一个结点可能被扫描到多次，可能导致死循环。为了避免这种情形，在遍历中，应为每个结点设立一个访问标志，了避免这种情形，在遍历中，应为每个结点设立一个访问标志，每扫描到一个结点，要检查它的访问标志，若标志为每扫描到一个结点，要检查它的访问标志，若标志为“未访问未访问”，则按正常方式对其进行处理（如访问或转到它的邻接点等），则按正常方式对其进行处理（如访问或转到它的邻接点等），否则放过它，扫描下一个结点。，否则放过它，扫描下一个结点。第5页，共44页，编辑于2022年，星期五 访问标志的设置有两种方法：访问标志的设置有两种方法：在描述图结的记录中增设一个访问标志位。这在描述图结的记录中增设一个访问标志位。这种方法的优点是，访问种方法的优点是，访问“访问标志访问标志”的方法与访问的方法与访问结点的方法一致。如果访问标志需要与图结构同生结点的方法一致。如果访问标志需要与图结构同生命期，则这种方法比较合适。但是，若访问标志要命期，则这种方法比较合适。但是，若访问标志要重复使用，就必须先重新初始化访问标志。如果图重复使用，就必须先重新初始化访问标志。如果图结点的存储不利于顺序访问，这往往也是个遍历问结点的存储不利于顺序访问，这往往也是个遍历问题！题！另设一个另设一个“访问数组访问数组”，令它的每个元素对应于一个，令它的每个元素对应于一个图结点访问标志。这种方法的访问标志很容易多次初始化图结点访问标志。这种方法的访问标志很容易多次初始化。第6页，共44页，编辑于2022年，星期五从图中某一结点出发，一趟只能遍历到它所在的极大从图中某一结点出发，一趟只能遍历到它所在的极大连通分量中的结点，要想遍历到图中各结点，需进行连通分量中的结点，要想遍历到图中各结点，需进行多趟遍历（每趟遍历一个极大连通分量）。该过程可多趟遍历（每趟遍历一个极大连通分量）。该过程可描述为：描述为：for(图中每个结点图中每个结点v)if(v尚未被访问过尚未被访问过)从从v出发遍历该图出发遍历该图;下面只考虑从一点出发遍历，因此有可能会出现下面只考虑从一点出发遍历，因此有可能会出现遍历不到的点。即那些初始点无路径可达的点，遍历不到的点。即那些初始点无路径可达的点，是遍历不到的。是遍历不到的。第7页，共44页，编辑于2022年，星期五20.2 20.2 深度优先遍历深度优先遍历(一一)遍历规则遍历规则从图中某结点从图中某结点v0出发，出发，深度优先遍历（深度优先遍历（DFS:DepthFirstSearch）图的规则为：图的规则为：访问访问v0；对对v0的各个出点的各个出点v01，v02，v0m，每次从它们中，每次从它们中按一定方式（也可任选）选取一个未被访问过的结点，按一定方式（也可任选）选取一个未被访问过的结点，从该结点出发按深度优先遍历方式遍历。从该结点出发按深度优先遍历方式遍历。显然，因为我们没有规定对出点的遍历次序，所以，图显然，因为我们没有规定对出点的遍历次序，所以，图的深度优先遍历结果一般不唯一的深度优先遍历结果一般不唯一。第8页，共44页，编辑于2022年，星期五 例例如如，对对图图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;12543 3abcd图图20 1一个有向图（左）和无向图一个有向图（左）和无向图第9页，共44页，编辑于2022年，星期五1.一般算法 下面考虑深度优先遍历的递归实现的一般方法（存储结构无下面考虑深度优先遍历的递归实现的一般方法（存储结构无关）。关）。图的深度优先遍历与二叉树的前序遍历相似。不同之处有：图的深度优先遍历与二叉树的前序遍历相似。不同之处有：二叉树每个结点至多有两个可达邻接点（左右儿子），二叉树每个结点至多有两个可达邻接点（左右儿子），而图的可达邻接点数目不定；而图的可达邻接点数目不定；对二叉树，沿可达邻接点搜索时不会发生回绕，但对图，若对二叉树，沿可达邻接点搜索时不会发生回绕，但对图，若不加特别控制，就有可能回绕。不加特别控制，就有可能回绕。下面是图的深度优先遍历递归算法的一般性描述。如果要另下面是图的深度优先遍历递归算法的一般性描述。如果要另设一个数组作为访问标志，则该数组要在递归过程（函数）设一个数组作为访问标志，则该数组要在递归过程（函数）之外初始化为之外初始化为“未访问未访问”。（二）递归实现方法（二）递归实现方法第10页，共44页，编辑于2022年，星期五longDFS(图图g，结点，结点v0)/图深度优先遍历递归算法。从结点图深度优先遍历递归算法。从结点v0出发，深度优先遍历出发，深度优先遍历图图g，返回访问到的结点总数，返回访问到的结点总数intnNodes;/寄存访问到的结点数目寄存访问到的结点数目访问访问v0;为为v0置已访问标志置已访问标志;nNodes=1;求出求出v0的第的第1个可达邻接点个可达邻接点v;while(v存在存在)if(v未被访问过未被访问过)nNodes=nNodes+DFS(g,v);求出求出v0的下个可达邻接点的下个可达邻接点v;returnnNodes;第11页，共44页，编辑于2022年，星期五12543 3 1 2 3 4 5 1 2 3 4 5 1 0 1 0 0 1 1 0 1 0 0 1 2 1 0 0 1 0 2 1 0 0 1 0 3 0 0 0 0 1 3 0 0 0 0 1 4 1 0 0 0 0 4 1 0 0 0 0 5 0 0 0 0 0 5 0 0 0 0 0所示图的邻接矩阵所示图的邻接矩阵所示图的邻接矩阵所示图的邻接矩阵g g1121304151图图图图 2020 1 1有向图访问标识数组访问标识数组visited1245输出数组输出数组resu例如从例如从1点深度优先遍历，先把点深度优先遍历，先把1设置访问标志，并置入输出数组设置访问标志，并置入输出数组resu，然后从邻接矩阵的第一行，然后从邻接矩阵的第一行，扫描各列，找到最近的邻接点扫描各列，找到最近的邻接点2，将其设置访问标志，并进入输出数组，接着从邻接矩阵，将其设置访问标志，并进入输出数组，接着从邻接矩阵的的2行扫描，找到第一个构成边的点是行扫描，找到第一个构成边的点是1，检查访问标识数组，发现，检查访问标识数组，发现1已经访问过，跳过，找第二个构已经访问过，跳过，找第二个构成边成边的点的点4，设置访问标识，进入输出数组，再从邻接矩阵的第，设置访问标识，进入输出数组，再从邻接矩阵的第4行扫描，寻找构成边的点，行扫描，寻找构成边的点，除除1外在无其他点，返回外在无其他点，返回2行，继续寻找，也无新点，返回行，继续寻找，也无新点，返回1，找到，找到5，将，将5置访问标志，进入输出数组，置访问标志，进入输出数组，1行再无其他新点，遍历结束，返回遍历元素个数为行再无其他新点，遍历结束，返回遍历元素个数为4。第12页，共44页，编辑于2022年，星期五 2 2邻接矩阵实现邻接矩阵实现 这里我们为了突出主题、简化问题，假定图是用一般的邻接矩阵存储，这里我们为了突出主题、简化问题，假定图是用一般的邻接矩阵存储，邻接矩阵用简单的二维数组表示（静态），用邻接矩阵用简单的二维数组表示（静态），用0和和1分别表示无边和有边。分别表示无边和有边。图结点用自然数编号。图结点用自然数编号。longDFS1(intgCNST_NumNodes,longn,longv0,char*visited,long*resu，long&top)/深度优先遍历图（递归）。图深度优先遍历图（递归）。图g为邻接矩阵，结点编号为为邻接矩阵，结点编号为 0n.返回实际遍历到的结点数目返回实际遍历到的结点数目/visited是访问标志数组，调用本函数前，应为其分配空间并初是访问标志数组，调用本函数前，应为其分配空间并初始化为全始化为全0(未访问未访问)/resu为一维数组，用于存放所遍历到的结点的编号，调用本函为一维数组，用于存放所遍历到的结点的编号，调用本函数前，应为其分配空间数前，应为其分配空间第13页，共44页，编辑于2022年，星期五longnNodes,i;nNodes=1;resutop+=v0;/将访问到的结点依次存于将访问到的结点依次存于resuvisitedv0=1;/为为v0置已访问标志置已访问标志for(i=0;in;i+)/依次从依次从v0的各个出点出发，深度优先遍历图的各个出点出发，深度优先遍历图if(gv0i!=0)/若若是边是边if(!visitedi)/若结点若结点i未被访问过未被访问过nNodes=nNodes+DFS1(g,n,i,visited,resu);/从从i起深度优先遍历图起深度优先遍历图returnnNodes;第14页，共44页，编辑于2022年，星期五 AA如如果果不不想想让让visited或或top做做为为函函数数参参数数，也也可可以以在在函函数数中中将将其其定定义义为为static型型量量。但但是是，这这样样的的程程序序是是不不可可再再入入的的，即即函函数数再再次次被被调调用用时时，static型型的的量量也也不不重重新新初始化，造成错误！初始化，造成错误！上面函数中的参数上面函数中的参数visited和和top实质上是中间变量，只是为了避免在实质上是中间变量，只是为了避免在递归调用时重新初始化而放在参数表中，造成使用的不方便，为此，做递归调用时重新初始化而放在参数表中，造成使用的不方便，为此，做个包装程序：个包装程序：longDFS1(intgCNST_NumNodes,longn,longv0,long*resu)char*visited;longtop=0;visited=newcharn;for(longi=0;in;i+)visitedi=0;longnum=DFS1(g,n,v0,visited,resu,top);deletevisited;returnnum;第15页，共44页，编辑于2022年，星期五12543 312452b51d451a1c2e3f45对应的邻接表对应的邻接表图图20 2有向图1121304151访问标识数组访问标识数组visited输出数组输出数组resu地址起 终权信息链a1 2bb1 5c2 1dd2 4e3 5f4 1邻接表边PNodes终点终点2作为下次的始点，由作为下次的始点，由于于1点已访问过，跳过，找点已访问过，跳过，找到到4，记标识，送输出，记标识，送输出，4有有作为新的始点重复上述过程作为新的始点重复上述过程第16页，共44页，编辑于2022年，星期五 3邻接表深度优先遍历的实现深度优先遍历的实现 templatelongDFS2(TGraphNodeAL*nodes,longn,longv0,char*visited,long*resu,long&top)/深度优先遍历用邻接表表示的图。深度优先遍历用邻接表表示的图。nodes是邻接表的头数组，是邻接表的头数组，n为结点个数为结点个数（编号为（编号为0n）。）。/v0为遍历的起点。返回实际遍历到的结点的数目。为遍历的起点。返回实际遍历到的结点的数目。/visited是访问标志数组，调用本函数前，应为其分配空间并初始化为是访问标志数组，调用本函数前，应为其分配空间并初始化为全全0(未访问未访问)/resu为一维数组，用于存放所遍历到的结点的编号，调用本函数前，应为一维数组，用于存放所遍历到的结点的编号，调用本函数前，应为其分配空间为其分配空间longnNodes,i;TGraphEdgeAL*p;nNodes=1;第17页，共44页，编辑于2022年，星期五resutop+=v0;/将访问到的结点依次存于将访问到的结点依次存于resuvisitedv0=1;/置置v0为为“已访问已访问”标志标志p=nodesv0.firstOutEdge;/求出求出v0的第一个出点的第一个出点pwhile(p!=NULL)if(!visitedp-endNo)/若若p未访问，则从未访问，则从p出发深度优先遍历出发深度优先遍历nNodes=nNodes+DFS2(nodes,n,p-endNo,visited,resu,top);p=p-next;/令令p指向指向v0的下个出点的下个出点returnnNodes;与邻接矩阵的情况类似，也可以对该程序与邻接矩阵的情况类似，也可以对该程序“包装包装”，以隐蔽，以隐蔽visited和和top。第18页，共44页，编辑于2022年，星期五(三三)非递归实现方法非递归实现方法1一般方法一般方法下下面面考考虑虑深深度度优优先先遍遍历历的的非非递递归归实实现现的的一一般般方方法法（存存储储结结构构无无关）。关）。图图的的深深度度优优先先遍遍历历的的非非递递归归实实现现，仍仍然然与与二二叉叉树树的的前前序序遍遍历历非非递递归归实实现现相相似似。不不同同之之处处有有：二二叉叉树树每每个个结结点点至至多多有有两两个个可可达达邻邻接接点点（左左右右儿儿子子），而而图图的的可可达达邻邻接接点点数数目目不不定定，因因此此，当当结结点点重重新新出出现现在在栈栈顶顶时时，不不能能一一定定出出栈栈，而而是是要要根根据据它它的的各各出出点点是是否否都都已已被被访访问问过过来来决决定定（是是则则出出栈栈）；对对二二叉叉树树，沿沿可可达达邻邻接接点点搜搜索索时时不不会会发发生生回回绕绕，但但对对图图，若若不不加特别控制，就有可能回绕。加特别控制，就有可能回绕。第19页，共44页，编辑于2022年，星期五longDFS_NR(图图g，结点，结点v0)/图深度优先遍历非递归算法。从结点图深度优先遍历非递归算法。从结点v0出发，深度优先遍历出发，深度优先遍历图图g，返回访问到的结点总数，返回访问到的结点总数intnNodes;/寄存访问到的结点数目寄存访问到的结点数目访问访问v0;为为v0置已访问标志置已访问标志;v0进栈进栈S；nNodes=1;求出求出v0的第的第1个可达邻接点个可达邻接点v;深度优先遍历非递归算法的一般性描述。深度优先遍历非递归算法的一般性描述。第20页，共44页，编辑于2022年，星期五while(栈栈S不空不空)v=栈栈S顶部元素；顶部元素；求求v的下个未访问过的出点的下个未访问过的出点i；访问访问i;为为i置已访问标志置已访问标志;i进栈进栈S；nNodes+;if(v已无未被访问过的出点已无未被访问过的出点)出栈；出栈；returnnNodes;上面的伪码描述与具体的数据结构无关。下面的程序分别给出上面的伪码描述与具体的数据结构无关。下面的程序分别给出了针对邻接矩阵与邻接表的算法模型。了针对邻接矩阵与邻接表的算法模型。第21页，共44页，编辑于2022年，星期五2邻接矩阵实现邻接矩阵实现longDFS1_NR(intgCNST_NumNodes,longn,longv0,long*resu)/深度优先遍历图深度优先遍历图(非递归）。图非递归）。图g为邻接矩阵，为邻接矩阵，结点编号为结点编号为0n.返回实际遍历到的结点数目返回实际遍历到的结点数目/resu为一维数组，用于存放所遍历到的结点的为一维数组，用于存放所遍历到的结点的 编号，调用本函数前，应为其分配空间编号，调用本函数前，应为其分配空间longnNodes,i,v;longtop;char*visited;long*s;visited=newcharn;for(i=0;in;i+)visitedi=0;s=newlongn+1;top=0;nNodes=0;resunNodes+=v0;/将访问到的结点依次存于将访问到的结点依次存于resuvisitedv0=1;/为为v0置已访问标志置已访问标志第22页，共44页，编辑于2022年，星期五 top+;stop=v0;while(top!=0)v=stop;for(i=0;in;i+)/寻找寻找v的下个未访问的邻接点的下个未访问的邻接点if(gvi!=0)/若若是边是边if(!visitedi)/若结点若结点i未被访问过未被访问过resunNodes+=i;/将访问到的结点依次存于将访问到的结点依次存于resuvisitedi=1;/为为i置已访问标志置已访问标志top+;stop=i;/i进栈进栈break;if(i=n)top-;/若若v已无未访问到的出点，则将其退栈已无未访问到的出点，则将其退栈/whilereturnnNodes;第23页，共44页，编辑于2022年，星期五下面给出初始结点为下面给出初始结点为1时，得进出栈的过程：时，得进出栈的过程：15224111进栈进栈，1出栈；出栈；2进栈，进栈，5进栈，进栈，5出栈，出栈，2出栈，出栈，1进栈，进栈，4进栈，进栈，4出栈，出栈，1出栈。出栈。遍历结果为遍历结果为1，5，2，4第24页，共44页，编辑于2022年，星期五20.320.3深度优先遍历的性质深度优先遍历的性质 深深度度优优先先遍遍历历有有许许多多重重要要而而有有趣趣的的性性质质，利利用用它它们们可可以以获获得得有有关关图图的的更更多多的的信信息息。我我们这里作一简单介绍。们这里作一简单介绍。(一一)深度优先生成树与单源路径深度优先生成树与单源路径在深度优先遍历中，如果将每次在深度优先遍历中，如果将每次“前进前进”（纵深）路过的（纵深）路过的（将被访问的）结点和边都记录下来，就得到一个子图，该（将被访问的）结点和边都记录下来，就得到一个子图，该子图为以出发点为根的树，称为深度优先生成树。子图为以出发点为根的树，称为深度优先生成树。第25页，共44页，编辑于2022年，星期五 如果从图的多个结点出发才能遍历到所有结点，则图的深度如果从图的多个结点出发才能遍历到所有结点，则图的深度 优先遍历树有多棵，从而构成森林，称为优先遍历树有多棵，从而构成森林，称为深度优先生成森林深度优先生成森林。显显然然，由由图图得得到到深深度度优优先先生生成成树树，相相当当于于对对图图“层层次次”化化，使使图图中每个结点都有一个层次号。中每个结点都有一个层次号。此此外外，从从v0出出发发深深度度优优先先遍遍历历树树，同同时时也也产产生生v0到到各各结结点点的的路路径径。例例如如，图图20 2(a)的出发点为的出发点为1的深度优先生成树如图的深度优先生成树如图20 2(b).(a)有向图有向图(b)深度优先生成树深度优先生成树图图20-2 深度优先遍历性质说明深度优先遍历性质说明1254361254361/122/53/47/86/119/10第26页，共44页，编辑于2022年，星期五(二二)时间戳时间戳 在在遍遍历历中中，对对每每个个结结点点v，定定义义从从第第一一次次“发发现现”（即即第第一一次次遇遇到到，开开始始遍遍历历）它它的的时时刻刻为为它它的的发发现现时时间间，记记为为S(v)，定定义义遍遍历历完完v的的时时刻刻为为v的的完完成成时时间间，记记为为E(v)。这这两两种种时时间间都都称称v的的时时间间戳戳。一一般般情情况况下下，用用遍遍历历中中“路路过过”（包包括括回回退退）的的结结点点数数表表示示时时间间。图图20 2(b)中中，结结点点旁旁边边的的数数字字“a/b”表表示示对对应应结结点点的的开开始始时时间间和和完完成成时时间间分别为分别为a和和b（针对（针对(a)的从的从1出发的深度优先遍历）。出发的深度优先遍历）。时时间间戳戳的的差差E(v)-S(v)可可用用在在推推算算深深度度优优先先遍遍历历的的进进行行情况，做为遍历的启发信息，指导遍历算法尽快发现目标。情况，做为遍历的启发信息，指导遍历算法尽快发现目标。第27页，共44页，编辑于2022年，星期五(三三)遍历括号遍历括号某结点某结点v的深度优先遍历括号定义为：的深度优先遍历括号定义为：(vX1X2Xmv)这里，这里，Xi为为v的出点中，可从的出点中，可从v出发直接访问到的各结出发直接访问到的各结点的遍历括号。点的遍历括号。i=1,m，m0。例如，图例如，图20 2(b)的结点的结点1的遍历括号为：按时间戳有的遍历括号为：按时间戳有(1(2(44)2)(5(33)(66)5)1)遍历括号实质上是广义表，它完全描述了深度优先遍历遍历括号实质上是广义表，它完全描述了深度优先遍历的过程及深度优先遍历生成树的结构，可做为深度优先遍的过程及深度优先遍历生成树的结构，可做为深度优先遍历生成树的串行化表达式。历生成树的串行化表达式。第28页，共44页，编辑于2022年，星期五20.420.4广度优先遍历广度优先遍历(一一)图的广度优先分层图的广度优先分层 图的广度优先分层与图的广度优先遍历密切相关。图的广度优先分层与图的广度优先遍历密切相关。另外，在许多其他问题中，也涉及到图的广度优先另外，在许多其他问题中，也涉及到图的广度优先分层。图的广度优先分层就是要识别出图中每个结分层。图的广度优先分层就是要识别出图中每个结点属于的层次，即给每个结点编一个层次号。但是，点属于的层次，即给每个结点编一个层次号。但是，图本身是非层次结构，所以，一般也无层次而言。图本身是非层次结构，所以，一般也无层次而言。然而，我们若只从某些关系然而，我们若只从某些关系/角度考虑问题，则就可角度考虑问题，则就可对图分层了。对图分层了。第29页，共44页，编辑于2022年，星期五 分层时，分层时，应先确定一个或几个参考点，将它们的层号指定应先确定一个或几个参考点，将它们的层号指定为起始层（第为起始层（第1层）层）。下面给出以结点。下面给出以结点v0为参考点的图的为参考点的图的广度优先分层广度优先分层的定义（非过程化），这里用的定义（非过程化），这里用Level(v)表表示结点示结点v的广度优先分层的的广度优先分层的层号层号：n n令令Level(v0)=1n n对任意的对任意的vv0，若存在，若存在v0到到v的通路，则令的通路，则令 Level(v)=1+MINuLevel(u)|是图的边是图的边否则令否则令Level(v)=可能在不同的路径中会有多个边到达，取其最短者，即层号低的可能在不同的路径中会有多个边到达，取其最短者，即层号低的那个。那个。第30页，共44页，编辑于2022年，星期五例例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的结点：的结点：c12543 3abcd第31页，共44页，编辑于2022年，星期五(二二)图的广度优先遍历方法图的广度优先遍历方法 从从结结点点v0出出发发，广广度度优优先先遍遍历历（Breadth/WidthFirstSearch）图图的的方方法法是是，按按从从v0出出发发，对对图图的的广广度度优优先先分分层层的的层层次次号号的的大大小小次次序序访访问问结结点点，即即先先访访问问第第一一层层上上结结点点，然然后后访访问问第第二二层层上上结结点点，等等等等，同层上结点可按邻接点次序或任意。同层上结点可按邻接点次序或任意。例如，图例如，图20 1中的两个图的一些广度优先遍历次序如下。中的两个图的一些广度优先遍历次序如下。左图：从左图：从1出发广度优先遍历结果：出发广度优先遍历结果：1，2，5，4左图：从左图：从2出发广度优先遍历：出发广度优先遍历：2，1，4，5右图：从右图：从a出发广度优先遍历：出发广度优先遍历：a，b，d，c从从另另一一角角度度看看，从从v出出发发广广度度优优先先遍遍历历，是是先先访访问问v，然然后后，对对任任意意结结点点u，在在访访问问了了u之之后后，对对u的的各各可可达达点点的的访访问问，按按距距u的的距距离离（边数）大小次序进行。（边数）大小次序进行。显然，若图的结点是无序的（即邻接点无次序关系），则广度显然，若图的结点是无序的（即邻接点无次序关系），则广度优先遍历次序也不是唯一的，但层次关系不颠倒。优先遍历次序也不是唯一的，但层次关系不颠倒。第32页，共44页，编辑于2022年，星期五(三)算法实现1.一一般般方方法法对对于于深深度度优优先先遍遍历历，用用递递归归方方法法描描述述是是件件自自然然的的事事，但但广广度度优优先先遍遍历历不不然然，使使用用递递归归描描述述反反而而会会使使问问题题复复杂杂化化，所所以以我我们们这这里里只只讲讲非非递递归描述法归描述法广度优先遍历是一种分层处理，对这种分层处理，使用队列是广度优先遍历是一种分层处理，对这种分层处理，使用队列是自然的自然的。我们设立一个队列，任何时刻，均保证它满足下列条件：。我们设立一个队列，任何时刻，均保证它满足下列条件：队中元素是已访问过的结点的可达邻接点；队中元素是已访问过的结点的可达邻接点；队中元素是尚未被访问过的；队中元素是尚未被访问过的；队中元素按它们所处的层次的先后排列。队中元素按它们所处的层次的先后排列。这样，我们就可不断地每次从队中取出一个元素并访问之，然后再这样，我们就可不断地每次从队中取出一个元素并访问之，然后再将该元素的尚未被访问过的邻接点进队，直至队空。将该元素的尚未被访问过的邻接点进队，直至队空。第33页，共44页，编辑于2022年，星期五 图的广度优先算法伪码描述如下：图的广度优先算法伪码描述如下：long BFS(long BFS(图图g,g,结点结点v0v0）/在图在图g g中从中从v0v0出发按广度优先遍历方式遍历出发按广度优先遍历方式遍历g g，返回遍历到，返回遍历到的结点数目的结点数目 long nNodes=0;long nNodes=0;初始化队初始化队Q;Q;if if（v0v0存在）存在）v0 v0入入Q;Q;置置v0v0为已访问标志为已访问标志;while(Q while(Q不空不空)队队Q Q头元素出队并送头元素出队并送v;v;访问访问v;v;nNodes+;/nNodes+;/对已访问元素计数对已访问元素计数 第34页，共44页，编辑于2022年，星期五 求出求出v v的第一个可达邻接点的第一个可达邻接点w;w;while(w while(w存在存在)if(w if(w尚未被访问过尚未被访问过)w w入入Q;Q;置置w w为已访问标志为已访问标志;求求v v的下个可达邻接点的下个可达邻接点w;w;return nNodes;return nNodes;AA 请请思思考考，(1)(1)如如果果上上面面的的程程序序中中不不使使用用队队列列，而而所所用用栈栈，那那么么是是否否正正确确？为为什么？什么？(2)(2)为什么结点一入队就置已访问标志？为什么结点一入队就置已访问标志？上面的算法描述是一般性的，并未涉及到具体的存贮结构。上面的算法描述是一般性的，并未涉及到具体的存贮结构。第35页，共44页，编辑于2022年，星期五2.邻接矩阵实现邻接矩阵实现设图用邻接矩阵表示，则它的广度优先遍历算法如下。设图用邻接矩阵表示，则它的广度优先遍历算法如下。long BFS1_NR(int gCNST_NumNodes,long n,long v0,long long BFS1_NR(int gCNST_NumNodes,long n,long v0,long*nos)*nos)/广度优先遍历（邻接矩阵）：从广度优先遍历（邻接矩阵）：从v0v0出发遍历用邻接矩阵表示的图出发遍历用邻接矩阵表示的图g g（共（共n n个结点）个结点）/将访问到的结点的编号存入将访问到的结点的编号存入nos(nos(其必须在外面分配其必须在外面分配n n个个longlong型空间）型空间），返回遍历到的结点数目，返回遍历到的结点数目 long nNodes=0;long nNodes=0;long v,w,i;long v,w,i;char*visited;char*visited;TQueueSqu Q(n+1);TQueueSqu Q(n+1);visited=new charn;visited=new charn;for(i=0;in;i+)visitedi=0;/for(i=0;i=0&v0=0&v0n)第36页，共44页，编辑于2022年，星期五 Q.QPush(v0);visitedv0=1;Q.QPush(v0);visitedv0=1;while(!Q.IsEmpty()while(!Q.IsEmpty()v=Q.QPop();v=Q.QPop();nosnNodes=v;/nosnNodes=v;/访问结点访问结点v v nNodes+;nNodes+;for(w=0;wn;w+)/for(w=0;wn;w+)/找找v v的各未访问的出点的各未访问的出点 if(gvw!=0)if(gvw!=0)if(!visitedw)if(!visitedw)Q.QPush(w);/v Q.QPush(w);/v的各未访问的出点进栈的各未访问的出点进栈 visitedw=1;visitedw=1;/while/while delete visited;delete visited;return nNodes;return nNodes;第37页，共44页，编辑于2022年，星期五12543 3 12345101001210010300001410000500000所示图的邻接矩阵所示图的邻接矩阵g1121304151图图图图 2020 1 1有向图访问标识数组访问标识数组visited1254输出数组输出数组nos145425第38页，共44页，编辑于2022年，星期五 3邻接表实现 针对邻接表的算法为：templatelongBFS2_NR(TGraphNodeAL*nodes,longn,longv0,long*nos)/广度优先遍历（邻接表）：从v0出发遍历用邻接表表示的图g（共n个结点）/将访问到的结点的编号存入nos(其必须在外面分配n个long型空间），返回遍历到的结点数目longnNodes=0;TGraphEdge*p;char*visited;TQueuesSquQ(n+1);visited=newcharn;for(i=0;i=0&v0endNo)Q.QPush(p-endNo);visitedp-endNo=1;p=p-next/while/whiledeletevisited;returnnNodes;第40页，共44页，编辑于2022年，星期五12543 312542b51d451a1c2e3f45对应的邻接表对应的邻接表图图20 2有向图1121304151访问标识数组访问标识数组visited输出数组输出数组nos地址起 终权信息链a1 2bb1 5c2 1dd2 4e3 5f4 1邻接表边PNodes12 55 44第41页，共44页，编辑于2022年，星期五20.520.5广度优先遍历的性质广度优先遍历的性质 与深度优先遍历类似，广度优先遍历也有许多有用的特性。与深度优先遍历类似，广度优先遍历也有许多有用的特性。(一一)广度优先生成树广度优先生成树 在在广广度度优优先先遍遍历历中中，如如果果将将每每次次“前前进进”（纵纵深深）路路过过的的（将将被被访访问问的的）结结点点和和边边都都记记录录下下来来，就就得得到到一一个个子子图图，该该子子图图为为以以出出发发点为根的树，称为点为根的树，称为广度优先生成树广度优先生成树。这种情况与深度优先遍历类似。这种情况与深度优先遍历类似。类似地，也可以给广度优先生成树结点定义时间戳。类似地，也可以给广度优先生成树结点定义时间戳。(二二)最短路径最短路径显显然然，从从v0出出发发广广度度优优先先遍遍历历图图，将将得得到到v0到到它它的的各各个个可可达达点点的的路路径径。我我们们这这里里定定义义路路径径上上的的边边的的数数目目为为路路径径长长度度。与与深深度度优优先先遍遍历历不不同同，广广度度优优先先遍遍历历得得到到的的v0到到各各点点的的路路径径是是最最短短路路径径（未考虑边权）。（未考虑边权）。第42页，共44页，编辑于2022年，星期五本章小结本章小结图的基本特征是图中元素的前驱与后继的个数都没有限制。图的基本特征是图中元素的前驱与后继的个数都没有限制。图的基本特征是图中元素的前驱与后继的个数都没有限制。图的基本特征是图中元素的前驱与后继的个数都没有限制。图是最复杂的非线性结构，它的表达能力也最强，前面介图是最复杂的非线性结构，它的表达能力也最强，前面介图是最复杂的非线性结构，它的表达能力也最强，前面介图是最复杂的非线性结构，它的表达能力也最强，前面介绍的线性结构、树等均是它的特例。绍的线性结构、树等均是它的特例。绍的线性结构、树等均是它的特例。绍的线性结构、树等均是它的特例。图的存储方式一般有两类：用边的集合表示图和用链接图的存储方式一般有两类：用边的集合表示图和用链接图的存储方式一般有两类：用边的集合表示图和用链接图的存储方式一般有两类：用边的集合表示图和用链接关系表示图。其中，边的集合方式有邻接矩阵，链接方关系表示图。其中，边的集合方式有邻接矩阵，链接方关系表示图。其中，边的集合方式有邻接矩阵，链接方关系表示图。其中，边的集合方式有邻接矩阵，链接方式有邻接表、十字链表和邻接多重表等。式有邻接表、十字链表和邻接多重表等。式有邻接表、十字链表和邻接多重表等。式有邻接表、十字链表和邻接多重表等。图结构的接口主要有：求某结点的各入点图结构的接口主要有：求某结点的各入点图结构的接口主要有