《3路径、最短路径、最大流》由会员分享，可在线阅读，更多相关《3路径、最短路径、最大流（15页珍藏版）》请在金锄头文库上搜索。
1、路径、最短路径、最大流 图论畅想与 matlab 编程简化假设：图都是连通的。1 无权图中单点到单点的路径1.1 示例数据：迷宫邻接矩阵：MG(i,j)表示顶点i与顶点j的邻接关系。迷宫A迷宫B迷宫CMG=MG=MG=0,0,1,1,1,1,10,0,1,1,1,1,10,0,1,1,1,1,11,0,1,1,1,1,11,0,1,1,1,1,11,0,1,1,1,1,11,0,0,0,1,0,01,0,0,0,1,0,01,0,0,0,0,0,01,1,1,0,1,1,01,1,1,0,1,1,01,1,1,0,1,1,01,1,1,0,1,1,01,1,1,0,1,1,01,1,1,0,1
2、,1,01,1,1,0,0,0,01,1,1,0,0,0,01,1,1,0,0,0,01,1,1,1,1,1,01,1,1,1,1,1,11,1,1,0,1,1,11,1,1,1,1,1,01；1,1,1,1,1,1,11;1,1,1,0,0,0,01;1.2求一条简单路径(有误)function path二findMGPath(MG,s,t)m,n二size(MG);FS二0,1; 1,0; 0,-1; -1,0; % 东南西北path=s 0;%路径栈栈顶值：1 1 0while isempty(path)path %调试语句%从栈顶取出当前位置loc，访问过的方向编号floc=path(
3、end,1:2); f=path(end,3);if f=4path(e nd,:) = ;%尝试了所有的方向之后，出栈elsepath(end,3)=f+1;nextloc=loc+FS(f+1,:); % 下一步的位置 nextlocif nextloc(1)=1 & nextloc(1)=1 &path=path; nextloc 0; %进栈if nextloc(1)=t(1) & nextloc(2)=t(2)path=path(:,1:2); return;endendendendend分析:迷宫A、迷宫D,找出一条路径。迷宫B、迷宫C,陷入死循环！ 原因：未考虑走回头路的可能性！
4、1.3求一条简单路径(检查足迹)function path二findMGPath(MG,s,t)m,n二size(MG);FS二0,1; 1,0; 0,-1; -1,0; % 东南西北path二s 0;%路径栈 栈顶值：1 1 0while isempty(path)path %调试语句%从栈顶取出当前位置loc，访问过的方向编号f loc=path(end,1:2); f=path(end,3);if f=4path(end,:) = ;%尝试了所有的方向之后，出栈elsepath(end,3)=f+1;nextloc=loc+FS(f+1,:); % 下一步的位置 nextloc if n
5、extloc(1)=1 & nextloc(1)=1 & path二path; nextloc 0; % 进栈if nextloc(1)=t(1) & nextloc(2)二二t(2)path二path(:,1:2); return;endendendendendfunction F=isln(path,loc)for i=1:size(path,1)if path(i,1)二二loc & path(i,2)二二loc(2)F=1; return;endendF=0;end分析：迷宫A、迷宫B、迷宫C、迷宫D,找出一条路 径，但未必是最短路径。归纳：图缺少明确的层次性,在遍历时,完全有可能 访
6、问已经访问过的顶点(位置/状态)。思考：有无其他检查足迹的方法？当然有！1.4求所有简单路径function findMGPaths(MG,s,t)m,n二size(MG);FS二0,1; 1,0; 0,-1; -1,0; % 东南西北path二s 0;%路径栈 栈顶值：1 1 0while isempty(path)%从栈顶取出当前位置loc，访问过的方向编号f loc=path(end,1:2); 仁 path(end,3);if f=4path(end,:) = ;%尝试了所有的方向之后，出栈elsepath(end,3)=f+1;nextloc=loc+FS(f+1,:); % 下一步
7、的位置 nextloc if nextloc(1)=1 & nextloc(1)=1 & path二path; nextloc 0;if nextloc(1)=t(1) & nextloc(2)二二t(2)path(:,1:2)%显示所有路径endendendendend思考：虽然能输出所有路径，但更希望保存所有的路 径，以便进一步计算。2 带权图中单点到单点的路径2.1 示例数据：有向图有向无环图有向有环图G=032000001340000020000002000003000000 ；G=0 3 2 0 0 00 0 1 3 1 00 0 0 0 2 00 0 0 0 0 20 3 0 0
8、0 30 0 0 0 0 0 ；目标：求出一条简单路径。若无路径，则路径为空。 path=FindPath(G, 1, 6) 注意：要检查足迹。2.2 从起点到终点的路径(非递归算法)function path=FindPath(G,S,t);path=s 0;% 路径栈while isempty(path)%从栈顶取出当前位置v,访问过的邻接点下标f v=path(end,1); f=path(end,2);adjv=find(G(v,f+1:end)0)+f; % +f 细节决定胜负 if isempty(adjv)path(end,:) = ;%尝试了所有邻接点后，出栈elsenexta
9、djv二adjv(1); % 下一个邻接点 adjv path(end,2)=nextadjv;if isempty(find(path(:,1)二二nextadjv) %检查足迹 path二path; nextadjv 0; % 进栈 if nextadjv二二t % 找到了终点 path二path(:,1); return;endendendendend测试：path二FindPath(G,1 6)有路径 测试： path=FindPath(G, 1, 8) 无路径2.3 思考：从起点到终点的所有路径2.4从起点到终点的路径(递归算法)function testPathglobalGpat
10、h pathsG二032000001340000020000002000003000000 ;paths=; path=;FindPath(1,6)；pathsendfunction FindPath(s,t)；global G path paths path=path; s;% 进栈if s二二tpaths(end+1).path二path % 保存所有路径elseadjv二find(G(s,:)0); % 所有的邻接点for i=1:length(adjv)if isempty(find(path二二adjv(i)%以未被访问过的邻接点为起点，进行深度优先搜索FindPath(adjv(i
11、), t);endendendpath(end) = ;% 出栈end算法检验：所求路径中当然没有回路!有向无环图e、 y 冷仁1 一：丿342tt有向有环图3 一2.宀匸1-30飞2329)所有路径所有路径1,2,3,5,61,2,3,5,61,2,4,61,2,4,61,2,5,61,2,5,61,3,5,61.3.5.2.4.61.3.5.63 归纳与提高3.1 归纳 图的遍历的功能：从指定顶点出发，遍历图中每个顶 点。深度优先搜索 DFS 算法的特征是：以未被访问过的邻 接点为起点，进行 DFS。核心数据结构：栈。 实现形式：可递归，可非递归。3.2 提高：欧拉回路 算法步骤：1、利用
12、DFS，从图中求得任一回路；若无回路，则原 图非欧拉图；2、从图中删掉回路中的边；3、若图中的边集不为空，转步骤 1，否则转步骤4；4、组合所有的回路，即得到欧拉回路。练习1:将上述DFS函数改为求一条回路的函数。 练习 2：如何将上述 C1、 C2、 C3 合并为一条回路。4 单点到多点的最短路径算法4.1 无权图的最短路径算法计算从 v3 到其余各个顶点的最短路径。G=0101000000110010000100010111000000100000000000010；sd=BFS(G,3)% sd=1 2 0 2 3 1 3function testBFSend0:巧1:Vj and2:v
13、2 and v43:v5 and v7BFS 算法的特征是：从起点由近及远，访问未被访问过的顶点。核心数据结构：队列。%队列的示例:% 3 1 6 2 %第1行是节点下标，% 0 1 1 2 %第2行是节点对应的最短路径长度 每个顶点只能进一次队列。同样要防备顶点重复进队 列。引入标志向量 flag。flag(i)=0 表示顶点 i 未进队列flag(i)=1表示顶点i已进队列function sd=BFS(G,sv) n=size(G,1);flag二zeros(1, n); % 标志向量 sd=ones(1,n)*inf； sd(sv)=0； % 初始化sd 为inf inf 0 inf in Q=sv; 0; flag(sv)=1;% 队列 Q 初始化while isempty(Q)v二Q(1,1)； d=Q(2,1)； sd(v)=d； % 填写最短路径长度Q(：,1) = ;% 出队列adjv二find(G(v,:)=1);% 找到 v 的所有邻接点 adj、adjv二adjv(find(flag(adjv)=O)
