《3路径、最短路径、最大流》由会员分享，可在线阅读，更多相关《3路径、最短路径、最大流（17页珍藏版）》请在金锄头文库上搜索。
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=isIn(path,loc)for i=1:size(pa th,l)if pat h(i,1)=loc(1) & pat h(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=pa th(end,1:2); f=pa th(end,3);if f=4path(end,:)二口；%尝试了所有的方向之后，出栈elsepat h(end,3)=f+1;nextloc二loc+FS(f+1,:);
7、% 下一步的位置 nextlocif nex tl oc(1)=1 & nex tl oc(1)二m & nex tl oc(2)=1 & path=path; nextloc 0;if nex tl oc(1)二二t(1) & nex tl oc二二t(2)path(:,l显示所有路径endendendendend思考：虽然能输出所有路径，但更希望保存所有的路 径，以便进一步计算。2带权图中单点到单点的路径2.1示例数据：有向图有向无环图有向有环图G=0 3 2 0 0 00 0 1 3 4 00 0 0 0 2 00 0 0 0 0 20 0 0 0 0 30 0 0 0 0 0 ;G=0
8、 3 2 0 0 00 0 1 3 1 00 0 0 0 2 00 0 0 0 0 20 3 0 0 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
9、isempty(adjv)path(end,:) = ;%尝试了所有邻接点后，出栈elsenextadjv二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 思考：从起点到终点
10、的所有路径2.4从起点到终点的路径(递归算法)function testPathglobalGpath pathsG二032000001340000020000002000003000000 ;paths=; path=;FindPat h(l,6)；pathsendfunction FindPa th(s,t)；global G path paths path=path; s;% 进栈if s=tpat hs(end+l).pa th二pa th % 保存所有路径elseadjv=find(G(s,:)0); % 所有的邻接点for i=1:length(adjv)if isempty(fi
11、nd(path二二adjv(i)%以未被访问过的邻接点为起点，进行深度优先搜索 FindPath(adjv(i), t);endendendpath(end) = ;% 出栈end算法检验：所求路径中当然没有回路!有向无环图/21 :仁1 t丿3 4 2 Xb2 3有向有环图(厂一 3； 土 c : 丫2门）2（少3所有路径所有路径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算法的特征是：以未被访问过的
12、邻 接点为起点，进行DFS。核心数据结构：栈。 实现形式：可递归，可非递归。3.2 提高：欧拉回路算法步骤：1、利用DFS，从图中求得任一回路；若无回路，则原 图非欧拉图；2、从图中删掉回路中的边；3、若图中的边集不为空，转步骤1，否则转步骤4；4、组合所有的回路，即得到欧拉回路。练习2 :如何将上述C1、C2、C3合并为一条回路。4单点到多点的最短路径算法4.1 无权图的最短路径算法计算从v3到其余各个顶点的最短路径。G=0101000000110010000100010111000000100000000000010；sd=BFS(G,3)% sd=1 2 0 2 3 1 3functio
13、n testBFSend0:巧1:Vj and2:v2 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); % adjv 没有进过队列的邻接 adjvsd=ones(1,length(adjv) * (d+
