第10周图（上）第3讲-图的遍历.pdf

《第10周图（上）第3讲-图的遍历.pdf》由会员分享，可在线阅读，更多相关《第10周图（上）第3讲-图的遍历.pdf（21页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、从给定图中任意指定的顶点（称为初始点）出发，按照从给定图中任意指定的顶点（称为初始点）出发，按照某种搜某种搜 索方法索方法沿着图的边访问图中的沿着图的边访问图中的所有顶点所有顶点，使，使每个顶点仅被访问一次每个顶点仅被访问一次， 这个过程称为这个过程称为图的遍历图的遍历。 图图的遍历得到的顶点序列称为的遍历得到的顶点序列称为图遍历序列图遍历序列。 8.3.1 图的遍历的概念图的遍历的概念 图中顶点之间是多对多的关系，而从一图中顶点之间是多对多的关系，而从一个顶点出发一次只能个顶点出发一次只能 找另外找另外一个相邻顶点一个相邻顶点。 1 302 4 例如例如： 从顶点从顶点1出发，访问顶点出发，

2、访问顶点1， 再再访问顶点访问顶点2，4， 再再访问顶点访问顶点2，3，0， 不同的搜索方法不同的搜索方法 初始点初始点 根据根据搜索方法的不同，图的遍历方法有两种搜索方法的不同，图的遍历方法有两种： 深度优先遍历（深度优先遍历（DFS）。）。 广度优先遍历（广度优先遍历（BFS）。）。 8.3.2 深度深度优先遍历算法优先遍历算法 v w 深度深度优先遍历优先遍历过程过程： 深度优先遍历的过程深度优先遍历的过程体现出后进先出体现出后进先出的特点：用栈或的特点：用栈或递归方式递归方式实现。实现。 算法设计算法设计思路思路： 320 1 4 初始点初始点 DFS：12 4 用用栈保存访问过的顶点

3、栈保存访问过的顶点 栈栈 1 2 如何确定一个顶点是否如何确定一个顶点是否访问过访问过? 设置设置一个一个visited 全局全局数组数组， visitedi=0表示顶点表示顶点i没有访问；没有访问； visitedi=1表示顶点表示顶点i已经访问过。已经访问过。 ivisitedi void DFS(ALGraph *G，int v) ArcNode *p; int w; visitedv=1;/置已访问标记置已访问标记 printf(%d ，v);/输出被访问顶点的编号输出被访问顶点的编号 p=G-adjlistv.firstarc;/p指向顶点指向顶点v的第一条边的边头节点的第一条边的边

4、头节点 while (p!=NULL) w=p-adjvex; if (visitedw=0) DFS(G，w);/若若w顶点未访问顶点未访问，递归访问它递归访问它 p=p-nextarc;/p指向顶点指向顶点v的下一条边的边头节点的下一条边的边头节点 该算法的时间复杂度为该算法的时间复杂度为O(n+e)。 采用邻接表的采用邻接表的DFS算法：算法： 320 1 4 0 v0134 1 v1023 2 v2134 3 v3012 4 v4023 4 v=2的的DFS序列：序列： 21034 遍历过程结束遍历过程结束 深度优先深度优先遍历过程演示遍历过程演示 320 1 4 DFS思路：思路：距

5、离初始顶点距离初始顶点越远越优先越远越优先访问！访问！ 8.3.3 广度广度优先遍历算法优先遍历算法 广度优先遍历广度优先遍历的过程：的过程： 广度优先搜索遍历体现先进先出的特点，用队列实现。广度优先搜索遍历体现先进先出的特点，用队列实现。 算法设计思路：算法设计思路： 320 1 4 初始点初始点 BFS：12 3 0 用队列用队列保存访问过的顶点保存访问过的顶点 队列队列 320 如何确定一个顶点是否如何确定一个顶点是否访问过访问过? 设置设置一个一个visited 数组数组， visitedi=0表示顶点表示顶点i没有访问；没有访问； visitedi=1表示顶点表示顶点i已经访问过。已

6、经访问过。 ivisitedi void BFS(ALGraph *G，int v) ArcNode *p; int w，i; int queueMAXV，front=0，rear=0; /定义循环队列定义循环队列 int visitedMAXV; for (i=0;in;i+) visitedi=0;/访问标志数组初始化访问标志数组初始化 printf(%2d，v);/输出被访问顶点的编号输出被访问顶点的编号 visitedv=1;/置已访问标记置已访问标记 rear=(rear+1)%MAXV; queuerear=v;/v进队进队 思考题：思考题：为什么为什么visited数组不需要设置

7、为全局变量？数组不需要设置为全局变量？ 采用邻接表的采用邻接表的BFS算法算法： while (front!=rear)/队列队列不空时循环不空时循环 front=(front+1)%MAXV; w=queuefront;/出队并赋给出队并赋给w p=G-adjlistw.firstarc;/找找w的第一个的邻接点的第一个的邻接点 while (p!=NULL) if (visitedp-adjvex=0) printf(“%2d”，p-adjvex); /访问之访问之 visitedp-adjvex=1; rear=(rear+1)%MAXV;/相邻顶点相邻顶点进队进队 queuerear=

8、p-adjvex; p=p-nextarc;/找下一个邻接顶点找下一个邻接顶点 该算法的时间复杂度为该算法的时间复杂度为O(n+e)。 v=2的的BFS序列：序列： 21340 遍历过程结束遍历过程结束 广度优先广度优先遍历过程演示遍历过程演示 320 1 4 320 1 4 0 v0134 1 v1023 2 v2134 3 v3012 4 v4023 4 BFS思路：思路：距离初始顶点距离初始顶点越近越优先越近越优先访问！访问！ 无向无向连通图连通图：调用一次：调用一次DFS或或BFS，能够，能够访问到图中的所有访问到图中的所有顶点。顶点。 8.3.4 非连通图的遍历非连通图的遍历 无向无

9、向非连通图非连通图：调用一次调用一次DFS或或BFS，只能访问到初始点所在连通分量只能访问到初始点所在连通分量 中的所有顶点中的所有顶点，不可能访问到其他连通分量中的顶点不可能访问到其他连通分量中的顶点。 可以分别遍历每个连通分量可以分别遍历每个连通分量，才能够访问到图中的所有顶点才能够访问到图中的所有顶点。 void DFS1(ALGraph *G) int i; for (i=0;in;i+)/遍历所有未访问过的顶点遍历所有未访问过的顶点 if (visitedi=0) DFS(G，i); 采用采用深度深度优先遍历方法优先遍历方法遍历遍历非非连通图连通图的算法如下：的算法如下： 非连通图：

10、非连通图：调用调用DFS()的次数恰好等于连通分量的个数的次数恰好等于连通分量的个数 void BFS1(ALGraph *G) int i; for (i=0;in;i+)/遍历所有未访问过的顶点遍历所有未访问过的顶点 if (visitedi=0) BFS(G，i); 采用采用广度广度优先遍历方法优先遍历方法遍历遍历非非连通图连通图的算法如下：的算法如下： 非连通图：非连通图：调用调用BFS()的次数恰好等于连通分量的个数的次数恰好等于连通分量的个数 采用某种遍历方式来判断采用某种遍历方式来判断无向图无向图G是否连通。这里用深度优先遍历是否连通。这里用深度优先遍历 方法，先给方法，先给vi

11、sited数组（为全局变量）置初值数组（为全局变量）置初值0，然后从，然后从0顶点开始顶点开始 遍历该图。遍历该图。 在一在一次遍历之后，若所有顶点次遍历之后，若所有顶点i的的visitedi均为均为1，则该图是连通的；，则该图是连通的； 否则不连通否则不连通。 【例例8- -1】 假设图假设图G采用邻接表存储采用邻接表存储，设计一个算法设计一个算法，判断判断 无向图无向图G是否连通是否连通。若连通则返回若连通则返回true；否则返回否则返回false。 求解思路求解思路 int visitedMAXV; bool Connect(ALGraph *G) /判断无向图判断无向图G的连通性的连通

12、性 int i; bool flag=true; for (i=0;in;i+)/visited数组置初值数组置初值 visitedi=0; DFS(G,0); /调用前面的中调用前面的中DSF算法算法,从顶点从顶点0开始深度优先遍历开始深度优先遍历 for (i=0;in;i+) if (visitedi=0) flag=false; break; return flag; 判断无向图判断无向图G是否连通是否连通的算法如下：的算法如下： 提示：提示：两个遍历算法两个遍历算法是图搜索算法是图搜索算法的基础，必须熟练掌握！的基础，必须熟练掌握！ 图搜索算法设计图搜索算法设计 DFS或或BFS算法求解算法求解 转化转化 图搜索算法设计一般方法图搜索算法设计一般方法 本讲完本讲完