第10周图（上）第4讲-图遍历的应用.pdf

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

1、DFS过程：过程： vv1v2vm 一步一步向前走，当没有可走的相邻顶点时便一步一步向前走，当没有可走的相邻顶点时便回退回退。 8.4 图遍历的应用图遍历的应用 8.4.1 基于深度优先遍历算法的应用基于深度优先遍历算法的应用 【例例8- -2】 假设假设图图G采用邻接表存储，设计一个算法，判断采用邻接表存储，设计一个算法，判断顶点顶点 uv是否有简单路径。是否有简单路径。 从从顶点顶点u开始进行开始进行深度深度优先遍历，优先遍历，当搜索到顶点当搜索到顶点v时表明从顶点时表明从顶点u到到v有有 路径，即：路径，即： 用用形参形参has（调用时其初值置为（调用时其初值置为false）表示顶点）表

2、示顶点uv是否有路径。是否有路径。 uu1u2v 深度优先遍历过程深度优先遍历过程 求解思路求解思路 void ExistPath(AGraph *G,int u,int v,bool ArcNode *p; visitedu=1;/置已访问标记置已访问标记 if (u=v)/找到了一条路径找到了一条路径 has=true;/置置has为为true并结束算法并结束算法 return; p=G-adjlistu.firstarc;/p指向顶点指向顶点u的第一个相邻点的第一个相邻点 while (p!=NULL) w=p-adjvex;/w为顶点为顶点u的相邻顶点的相邻顶点 if (visited

3、w=0)/若若w顶点未访问顶点未访问,递归访问它递归访问它 ExistPath(G,w,v,has); p=p-nextarc;/p指向顶点指向顶点u的下一个相邻点的下一个相邻点 深度优先遍历 【例例8- -3】假设假设图图G采用邻接表存储，设计一个算法输出图采用邻接表存储，设计一个算法输出图G中从中从 顶点顶点u v的一条简单路径（假设图的一条简单路径（假设图G中从中从顶点顶点u v至少有一条简单至少有一条简单 路径）。路径）。 采用采用深度优先遍历的深度优先遍历的方法方法。 增加增加path和和d形参形参，其中，其中path存放顶点存放顶点u到到v的路径，的路径，d表示表示path中的路中

4、的路 径长度，其初值为径长度，其初值为- -1。 当当从顶点从顶点u遍历到顶点遍历到顶点v后，输出后，输出path并返回。并返回。 DFS(G,u,v,path,d)DFS(G,u1,v,path,d)DFS(G,um,v,path,d) um=v 输出输出path并返回并返回 求解思路求解思路 void FindaPath(AGraph *G,int u,int v,int path,int d) /d表示表示path中的路径长度，初始为中的路径长度，初始为-1 int w,i; ArcNode *p; visitedu=1; d+; pathd=u;/路径长度路径长度d增增1，顶点，顶点u

5、加入到路径中加入到路径中 if (u=v)/找到一条路径后输出并返回找到一条路径后输出并返回 printf(一条简单路径为一条简单路径为:); for (i=0;iadjlistu.firstarc; /p指向顶点指向顶点u的第一个相邻点的第一个相邻点 while (p!=NULL) w=p-adjvex;/相邻点的编号为相邻点的编号为w if (visitedw=0) FindaPath(G,w,v,path,d); p=p-nextarc; /p指向顶点指向顶点u的下一个相邻点的下一个相邻点 深度优先遍历 【例例8- -4】假设假设图图G采用邻接表存储，设计一个算法，输出图采用邻接表存储，

6、设计一个算法，输出图G 中从中从顶点顶点u v的所有简单路径。的所有简单路径。 利用利用回溯的回溯的深度深度优先遍历方法优先遍历方法。 从从顶点顶点u开始进行开始进行深度深度优先遍历。增加优先遍历。增加path和和d记录存记录存走过走过的的路径。路径。 若若当前当前扫描的扫描的顶点顶点u = v时，表示找到了一条路径，则输出路径时，表示找到了一条路径，则输出路径path。 当从顶点当从顶点u出发的路径找完后，置出发的路径找完后，置visitedu=0，即，即回溯回溯。 求解思路求解思路 DFS(G,u,v,path,d) 回溯所有路径后结束回溯所有路径后结束 um=v 输出一条输出一条path

7、 DFS(G,u1,v,path,d) DFS(G,um,v,path,d) um=v 输出一条输出一条path DFS(G,um,v,path,d) visitedum=0 回溯回溯 visitedum=0 回溯回溯 visitedu1=0回溯回溯 void FindPath(AGraph *G,int u,int v,int path,int d) /d表示表示path中的路径长度，初始为中的路径长度，初始为-1 int w,i; ArcNode *p; d+; pathd=u;/路径长度路径长度d增增1，顶点，顶点u加入到路径中加入到路径中 visitedu=1;/置已访问标记置已访问标

8、记 if (u=v iadjlistu.firstarc;/p指向顶点指向顶点u的第一个相邻点的第一个相邻点 while (p!=NULL) w=p-adjvex;/w为顶点为顶点u的相邻顶点的相邻顶点 if (visitedw=0)/若若w顶点未访问顶点未访问,递归访问它递归访问它 FindPath(G,w,v,path,d); p=p-nextarc;/p指向顶点指向顶点u的下一个相邻点的下一个相邻点 visitedu=0; 深度优先遍历 恢复环境，使该顶点可重新使用 1 32 4 0 算法执行结果算法执行结果 从从1到到4的所有路径的所有路径: 1 2 4 1 2 3 4 1 0 3 4

9、 1 0 3 2 4 【例例8- -5】假设图假设图G采用邻接表存储，设计一个算法，输出图采用邻接表存储，设计一个算法，输出图 G中中从顶点从顶点u到到v的长度为的长度为l的所有简单路径的所有简单路径。 遍历遍历思路和上例相似，只需将路径输出条件改为：思路和上例相似，只需将路径输出条件改为：u=v且且d=l。 void PathAll(ALGraph*G,int u,int v,int l,int path,int d) /d是到当前为止已走过的路径长度，调用时初值为是到当前为止已走过的路径长度，调用时初值为-1 int w，i; ArcNode *p; visitedu=1; d+; /路径

10、长度增路径长度增1 pathd=u;/将当前顶点添加到路径中将当前顶点添加到路径中 if (u=v iadjlistu.firstarc; /p指向指向u的第一条边的边头节点的第一条边的边头节点 while (p!=NULL) w=p-adjvex;/w为为u的邻接顶点的邻接顶点 if (visitedw=0) /若顶点未标记访问，则递归访问之若顶点未标记访问，则递归访问之 PathAll(G,w,v,l,path,d); p=p-nextarc/找找u的下一个邻接顶点的下一个邻接顶点 visitedu=0; 深度优先遍历 恢复环境，使该顶点可重新使用 1 32 4 0 算法执行结果算法执行结

11、果 从从1到到4的所有长度为的所有长度为3路径路径: 1 0 3 4 1 2 3 4 u 一圈一圈向外走。一圈一圈向外走。 BFS过程：过程： u1 v 以以 u v 的的 最最 短短 路路 径径 构构 成成 分分 层层 8.4.2 基于基于广度广度优先遍历算法的应用优先遍历算法的应用 【例例8- -6】假设假设图图G采用邻接表存储，设计一个算法，求不带采用邻接表存储，设计一个算法，求不带 权无向连通图权无向连通图G中从中从顶点顶点uv的一条的一条最短最短路径路径（路径上经过的顶点（路径上经过的顶点 数最少）数最少）。 最好采用最好采用广度优先遍历广度优先遍历来实现。来实现。 typedef

12、struct int data;/顶点编号顶点编号 int parent;/前一个顶点的位置前一个顶点的位置 QUERE; void ShortPath(ALGraph *G,int u,int v) /输出从顶点输出从顶点u到顶点到顶点v的最短逆路径的最短逆路径 ArcNode *p; int w,i; QUERE quMAXV;/定义非定义非循环队列循环队列 int front=-1, rear=-1;/队列的头、尾指针队列的头、尾指针 int visitedMAXV; for (i=0;in;i+)/访问标记置初值访问标记置初值0 visitedi=0; rear+;/顶点顶点u进队进队

13、 qurear.data=u; qurear.parent=-1; visitedu=1; 非循环队列类型非循环队列类型 while (front!=rear)/队不空循环队不空循环 front+;/出队顶点出队顶点w w=qufront.data; if (w=v) i=front; while (qui.parent!=-1) printf(%2d ,qui.data); i=qui.parent; printf(%2dn,qui.data); break; 输出逆路径 p=G-adjlistw.firstarc; /找找w的第一个邻接点的第一个邻接点 while (p!=NULL) if

14、 (visitedp-adjvex=0) visitedp-adjvex=1; rear+;/将将w的未访问过的邻接点进队的未访问过的邻接点进队 qurear.data=p-adjvex; qurear.parent=front; p=p-nextarc;/找找w的下一个邻接点的下一个邻接点 用用DFS和和BFS求解迷宫问题求解迷宫问题 0 1 2 3 4 5 0 1 2 3 4 5 (0,0) (1,2)(2,1) (1,1) (1,1)(1,3) (1,2) (1,2) (1,3) 创建迷宫问题的邻接表：创建迷宫问题的邻接表： (1,2)(2,1) (1,1) typedef struct

15、 VNode adjlistM+2N+2; ALGraph; /迷宫图的邻接表类型迷宫图的邻接表类型 typedef struct ANode int i, j; structANode *nextarc; ArcNode; typedef struct Vnode ArcNode *firstarc; VNode; 邻接表设计：邻接表设计： 算法设计算法设计 具体算法请你实现！具体算法请你实现！ DFS和和BFS求解迷宫问题求解迷宫问题的差别的差别 1 32 4 0 013 2 4 以以0v的的 最短路径最短路径 构成分层构成分层 每个顶点表示一个方块每个顶点表示一个方块 起点起点 表示相邻

16、的边表示相邻的边 深度优先遍历深度优先遍历可能找到可能找到04的的一条路径：一条路径： 1 32 4 0 013 2 4 路径：路径：0 1 2 4 路径上的顶点可能在路径上的顶点可能在同一层同一层 不一定是不一定是最短路径最短路径 1 23 4 0013 2 4 广度优先广度优先遍历遍历找到找到04的的路径路径同一层只能有一个顶点。同一层只能有一个顶点。 逆逆路径：路径：4 3 0路径：每路径：每一层只有一个顶点一层只有一个顶点 一定是一定是最短路径最短路径 广度优先遍历找到广度优先遍历找到的路径一定是的路径一定是最短路径，而最短路径，而深度深度优先遍历则优先遍历则 不一定。不一定。 深度优先遍历能找所有深度优先遍历能找所有路径，而路径，而广度优先遍历难以实现。广度优先遍历难以实现。 结论：结论： 以路径上经过的边数来衡量路径长度以路径上经过的边数来衡量路径长度 数据结构数据结构算法的多维性算法的多维性 同一问题的多种解法。同一问题的多种解法。 迷宫问题迷宫问题 用用栈方法求解栈方法求解用用队列方法求解队列方法求解 用用图搜索方法求解图搜索方法求解用用递归方法求解递归方法求解 各种求解方法的特点和差别各种求解方法的特点和差别 本讲完本讲完