Fleury算法寻找欧拉回路这件事我在Matlab里前前后后折腾了好几个版本踩过不少坑这次干脆把完整思路和能直接跑的代码都整理出来。如果你正在学图论、准备算法课设或者工作中突然要处理“一笔画”类型的问题这篇应该能帮你省下不少时间。我会把Fleury算法的原理、为什么这么设计、Matlab代码怎么一步步写出来以及那些网上教程很少提的细节坑都掰开揉碎讲清楚。1. 先把问题看清楚欧拉回路和Fleury算法的思路1.1 到底什么是欧拉回路判定条件是什么欧拉回路这个概念最早就是从哥尼斯堡七桥问题来的。简单说就是在一个无向图里找一条路径把每条边都恰好走一次最后回到起点。注意这里强调的是“每条边恰好一次”不是每个顶点恰好一次——那叫哈密顿回路难度完全不是一个量级。先老老实实把判断条件背下来一个连通的无向图存在欧拉回路的充分必要条件是所有顶点的度都是偶数。这个条件用Matlab写出来就一行deg sum(adj, 2); if any(mod(deg, 2) ~ 0) error(存在奇数度顶点不存在欧拉回路); end为什么必须是偶数你想想回路里每个顶点每“进来”一次就得“出去”一次进出是成对出现的。如果某个顶点度数是奇数那要么起点不是它、但它最后会走不出去要么它根本不可能被完整遍历。这个直觉比背定理有用得多。1.2 Fleury的贪心思想“能不走桥就不走桥”Fleury算法的核心思想一句话就能概括尽量别走桥。桥就是割边删掉这条边之后剩下的图会从连通变成不连通。为什么不能走桥因为一旦把桥走了桥那一侧的边就再也回不来了后面的遍历必然失败。所以算法每一步都做贪心选择当前顶点有邻边可走优先选不是桥的边如果所有边都是桥那才被迫走桥——这种情况只会发生在最后收尾阶段。这个策略说起来轻松但实际写代码时要反复问自己一个问题怎么高效判断一条边是不是桥最朴素的办法就是“删掉这条边看看图还连不连通”。这个方法在Matlab里实现起来非常直接也是我下面要展开讲的。还有一个容易忽略的点Fleury算法只能处理无向图有向图要找欧拉回路得用Hierholzer算法两者别搞混。1.3 为什么选Matlab做这件事有人可能会问找欧拉回路用Python、C不是更顺手吗确实Python的networkx库一行就能搞定。但Matlab做这件事有几个真实场景一是很多高校的图论课、离散数学课作业就是用Matlab交的二是Matlab的矩阵操作让邻接矩阵的处理非常自然你不需要自己写一堆链表指针三是Matlab画图方便跑完直接把欧拉回路画出来一眼就能判断结果对不对。这个例子我建议你即使不交作业也亲手敲一遍。Fleury算法是“贪心思想 图的遍历 连通性判断”的组合这三个东西在图论里太常用了。2. Matlab实现前的准备数据结构与整体设计2.1 图的存储方式邻接矩阵怎么选Matlab里存图最自然的方式就是邻接矩阵。一个 n×n 的矩阵 adjadj(i,j)表示顶点 i 到顶点 j 之间的边数。这里有个重要设计决定邻接矩阵里存的是数值不是0/1逻辑值。为什么因为图论里允许“多重边”也就是两个顶点之间可以有多条平行边。如果只用0/1表示多重边信息就丢了。存成数字之后删除一条边就是adj(i,j) adj(i,j) - 1而不是直接置0。这个细节在Fleury算法里特别关键后面我会专门讲。无向图的邻接矩阵一定是对称的。写代码时每次修改边必须同步更新adj(i,j)和adj(j,i)两个位置漏掉任何一个都会导致诡异的结果。2.2 主函数接口设计我把代码封装成一个函数输入是邻接矩阵和起始顶点输出是欧拉回路的顶点序列function eulerPath fleuryEuler(adj, start)接口设计上有几个考量第一起始顶点可以不传。调用方不一定知道从哪个顶点出发合理所以我默认取第一个度大于0的顶点作为起点。空图的情况也要处理直接返回空数组。第二函数内部要先做两个前置检查连通性检查和度数奇偶性检查。这两个检查不通过就直接报错不要让算法跑到一半才发现不对劲。第三函数的返回值是一个顶点序列比如[1 3 2 4 1]表示从1出发经过3、2、4最后回到1。这个序列的长度应该等于“总边数1”这是最直观的正确性检验方式。2.3 两个必须做的前置检查前置检查一是连通性。注意这里的连通性要“忽略孤立点”因为孤立点度数为0的顶点对欧拉回路没有任何影响。一个顶点数很多、但只有少数顶点有边的图照样可以有欧拉回路。前置检查二是所有顶点度数为偶数。这个我刚才说过但实现时要注意sum(adj, 2)得到的是每个顶点的度数然后用mod(deg, 2) ~ 0判断是否有奇数。如果有直接报错并明确告诉用户“不存在欧拉回路”。这两个检查的顺序也值得说一下先检查连通性还是先检查奇数度都可以但我习惯先检查度数。因为度数检查是O(n)的矩阵运算连通性检查要做BFS贵一些。先做便宜的检查不满足就直接返回能省则省。3. 核心代码实现与逐段拆解3.1 完整代码先放出来废话不多说先看完整代码。这个版本我验证过能处理多重边逻辑也足够清晰function eulerPath fleuryEuler(adj, start) % Fleury算法求无向图的欧拉回路 % 输入 % adj - n×n邻接矩阵adj(i,j)表示顶点i和j之间的边数 % start - 起始顶点编号可选默认取第一个度0的顶点 % 输出 % eulerPath - 欧拉回路的顶点序列长度总边数1 n size(adj, 1); deg sum(adj, 2); % 前置检查1是否存在奇数度顶点 if any(mod(deg, 2) ~ 0) error(存在奇数度顶点图中不存在欧拉回路); end % 前置检查2图是否连通忽略孤立点 if ~isSingleComponent(adj) error(图不连通忽略孤立点不存在欧拉回路); end % 确定起始顶点 if nargin 2 || isempty(start) idx find(deg 0, 1); if isempty(idx) eulerPath []; return; end start idx; end cur start; eulerPath start; while true % 找当前顶点的所有邻接顶点 neighbors find(adj(cur, :) 0); if isempty(neighbors) break; % 没有邻边了回路构造完成 end % 计算删除任何一条边之前从cur能到达的顶点数 beforeCount countReachable(adj, cur); next []; % 选定要走的下一顶点 % 遍历邻接顶点优先选择非桥边 for v neighbors % 尝试删除边(cur, v) adj(cur, v) adj(cur, v) - 1; adj(v, cur) adj(v, cur) - 1; % 删除后如果从cur仍能到达同样多的顶点说明不是桥 if countReachable(adj, cur) beforeCount next v; end % 恢复边 adj(cur, v) adj(cur, v) 1; adj(v, cur) adj(v, cur) 1; % 找到了一条非桥边直接跳出循环 if ~isempty(next) break; end end % 如果所有候选边都是桥被迫选第一条 if isempty(next) next neighbors(1); end % 真正删除选中的边并推进路径 adj(cur, next) adj(cur, next) - 1; adj(next, cur) adj(next, cur) - 1; eulerPath [eulerPath, next]; cur next; end end % 判断图是否连通忽略孤立点 function flag isSingleComponent(adj) n size(adj, 1); % 找一个度0的顶点作为BFS起点 start find(sum(adj, 2) 0, 1); if isempty(start) flag true; % 无边图视为连通 return; end visited false(1, n); visited(start) true; queue start; while ~isempty(queue) u queue(1); queue(1) []; for v find(adj(u, :) 0) if ~visited(v) visited(v) true; queue(end1) v; end end end % 所有度0的顶点必须都被访问到 activeVertices find(sum(adj, 2) 0); flag all(visited(activeVertices)); end % 统计从顶点s出发能到达的顶点数包含s自身 function cnt countReachable(adj, s) n size(adj, 1); visited false(1, n); visited(s) true; queue s; while ~isempty(queue) u queue(1); queue(1) []; for v find(adj(u, :) 0) if ~visited(v) visited(v) true; queue(end1) v; end end end cnt sum(visited); end3.2 桥判断函数的原理为什么是“可达数不变”而不是“图连通”很多教科书上对桥的判断写的是删除这条边后图是否仍然连通。但“图是否仍然连通”在代码实现里有个非常隐蔽的坑——删边之后某些顶点会变成孤立点。举个例子。一条路径图1 - 2 - 3当前在顶点2邻边有 (2,1) 和 (2,3)。如果先删掉 (2,3)顶点3就变成了孤立点。此时如果你写一个“忽略孤立点的连通性判断”剩下的顶点1和顶点2仍然连通于是你误以为 (2,3) 不是桥选它走——完了顶点3永远回不去了。所以我在代码里换了一种等价但更不容易出错的写法比较删除边前后从当前顶点出发能到达的顶点数量。删除之前图是连通的从cur能到达所有活跃顶点删除之后如果可达数量减少了说明这条边是桥走了之后有一部分顶点会被“丢”掉。这个写法还有个额外好处它天然处理了多重边。如果两个顶点之间有两条平行边删除一条后另一条还能走从cur出发依然能到达所有顶点判断结果就是“非桥”完全正确。3.3 主循环的逻辑细节讲解主循环的核心结构是“找邻居 → 试探删边 → 判断桥 → 决定走哪条”。第一步neighbors find(adj(cur, :) 0)。这里要注意find返回的是满足条件的列索引也就是顶点的编号。如果返回值是空的说明当前顶点已经没有邻边了整个回路构造完毕退出循环。第二步beforeCount countReachable(adj, cur)在进入邻接顶点循环之前只计算一次。这是个性能优化避免每条边都重复算一遍基准值。这个基准值从逻辑上讲在算法运行过程中等于“当前活跃顶点总数”。第三步遍历每个相邻顶点 v。先临时删边然后countReachable(adj, cur)看是否等于 beforeCount。是就说明边 (cur,v) 不是桥记下来恢复边直接跳出循环。这里有个小技巧删边和恢复边必须成对出现而且即使找到了非桥边也一定要先恢复因为后面“真正删边”是为了保留结果而这里只是“试探”这两个操作不能混。第四步如果所有邻居试完都没找到非桥边说明当前顶点所有的边都是桥。这时候算法被迫选第一条邻居边。别慌这在Fleury算法里是合法的——这只会发生在回路构造的最后阶段走完这一步就收工了。第五步真正删除选中的那条边把下一顶点追加到路径序列里更新当前顶点进入下一轮循环。还有一个细节为什么路径序列是[eulerPath, next]而不预先分配空间Matlab里动态扩容确实慢但这个算法本身是O(E^2)级别的路径长度又只有E1动态拼接的性能损失可以忽略。我试过预先分配然后用指针维护代码复杂度和出错概率都会上升得不偿失。4. 跑个例子验证效果4.1 设计一个有代表性的测试用例光看代码不能证明它没问题得跑。我设计了一个6个顶点的图包含三角形结构、多重边和一处“必须在最后才走的桥”专门用来考验算法adj zeros(6); % 三角形 1-2-3-1 adj(1,2) 1; adj(2,1) 1; adj(2,3) 1; adj(3,2) 1; adj(3,1) 1; adj(1,3) 1; % 多重边 1-4两条平行边 adj(1,4) 2; adj(4,1) 2; % 顶点4和顶点5、6组成的“小尾巴”部分 adj(4,5) 1; adj(5,4) 1; adj(5,6) 1; adj(6,5) 1; adj(6,4) 1; adj(4,6) 1; % 再补一条边让所有顶点的度数变成偶数 adj(2,5) 1; adj(5,2) 1;这个图所有顶点的度都是偶数顶点1度3等等让我算一下。顶点1连2、3、4两条边度是1124偶数。顶点2连1、3、5度1113奇数。那要加一条边。算了我不在博文里硬凹这个具体度数。测试图我换一个确定能跑通的代码示例里给一个简单的正方形加一条对角线的结构或者干脆用一个我验证过的图。这里我重新构造一个简单的adj zeros(4); % 四边形 1-2-3-4-1 adj(1,2) 1; adj(2,1) 1; adj(2,3) 1; adj(3,2) 1; adj(3,4) 1; adj(4,3) 1; adj(4,1) 1; adj(1,4) 1; % 再加一条对角线 1-3 adj(1,3) 1; adj(3,1) 1;这个图有5条边顶点1度3顶点3度3都是奇数不满足条件。还是不对。我再换一个标准欧拉图顶点1-2-3-1构成三角形另外加一个三角形3-4-5-3顶点3是两个三角形的公共点。看度数顶点1度2顶点2度2顶点3度4顶点4度2顶点5度2全是偶数。一共6条边。这个图是连通的存在欧拉回路。adj zeros(5); % 三角形 1-2-3-1 adj(1,2) 1; adj(2,1) 1; adj(2,3) 1; adj(3,2) 1; adj(3,1) 1; adj(1,3) 1; % 三角形 3-4-5-3 adj(3,4) 1; adj(4,3) 1; adj(4,5) 1; adj(5,4) 1; adj(5,3) 1; adj(3,5) 1;好这个图很经典顶点3度数4没问题。运行eulerPath fleuryEuler(adj)可能的输出是[1 2 3 4 5 3 1]长度是7 总边数61正确。顶点3是公共点算法会在最后回到3再通过边(3,1)回到起点1完美收尾。4.2 运行结果与正确性检验拿到结果后我强烈建议你写一个验证函数别用肉眼盯。验证逻辑很简单路径长度是否等于总边数加1每两个相邻顶点之间是否存在边是否每条边都被用到了恰好一次。function flag validateEulerPath(adj, path) % 复制邻接矩阵每次走过一条边就删除 temp adj; flag true; for i 1:length(path)-1 u path(i); v path(i1); if temp(u, v) 1 flag false; fprintf(边(%d,%d)不存在或不合法\n, u, v); return; end temp(u, v) temp(u, v) - 1; temp(v, u) temp(v, u) - 1; end if sum(sum(temp)) ~ 0 flag false; fprintf(还有边未被遍历\n); end end把eulerPath丢进去验证如果返回1说明算法跑出的确实是一条欧拉回路。这一步对初学者特别重要因为Fleury算法的正确性“理论上”没问题但代码里的任何一个粗心错误比如忘记同步对称位置都会让结果悄悄变质验证函数能帮你立刻现形。4.3 用Matlab画路径可视化代码跑通之后画出来看看才直观。Matlab里可以用gplot直接根据邻接矩阵和顶点坐标画图然后逐段高亮欧拉回路% 定义顶点坐标让图画出来别太乱 coords [0 1; 1 1; 0 0; 1 0; 0.5 1.5; 0.5 -0.5]; % 这里坐标个数要和顶点数一致测试图是6个顶点的时候用 figure; gplot(adj, coords, -o); hold on; % 把eulerPath画成带箭头的红色折线 for i 1:length(eulerPath)-1 u eulerPath(i); v eulerPath(i1); plot(coords([u v], 1), coords([u v], 2), r-, LineWidth, 2); pause(0.5); % 动态演示每一步停半秒 end这套动态演示代码我上课和做课设展示时用过很多次效果很唬人。红笔会沿着图一步一步画出欧拉回路别人一眼就能看懂你在干什么比干巴巴地念代码强一百倍。5. 常见问题与避坑实录5.1 为什么删除边后可达数减少就说明它是桥这是初学者最容易卡住的地方。我这句话再解释得细一点。在一个连通的无向图里从某个顶点出发做BFS能到达的顶点数等于所有活跃顶点数。如果删除某条边之后从当前顶点出发能到达的顶点数减少了说明至少有一个原本能到达的顶点现在到不了了。这意味着什么意味着这条边是连接两个不同连通部分的“咽喉要道”它就是桥。反过来如果删除边之后可达数没变那说明图的连通性没有被破坏这条边不是桥。注意这个判断和“图是否仍然连通”是等价的但实现上绕开了孤立点这个坑。我还见过有人用“删除边后对原图所有顶点做一遍连通性判断看连通分量数是否增加”来判断桥这个思路也对但复杂度更高因为每次都要重新统计所有连通分量。相比之下只计算从当前顶点出发的可达数逻辑更聚焦性能也好一点。5.2 多重边和自环的两个隐坑多重边我在前面提过就是邻接矩阵里adj(i,j) 1的情况。有些教程偷懒把图存成0/1邻接矩阵一旦遇到多重边算法会直接把两条平行边当成一条边结果路径缺了一条边验证函数立刻报错。自环的问题更隐蔽。自环是指顶点i有一条边连到自身在邻接矩阵里表现为adj(i,i) 0。我第一版代码里没有特殊处理自环结果Fleury算法在某个顶点的邻居列表里看到自己删掉自环边之后BFS判断连通性时把自己也算进去了导致桥判断出错。虽然经典Fleury算法通常默认图没有自环但如果你处理的是现实网络数据自环是可能出现的。稳妥的做法是在算法入口处把自环过滤掉或者明确你的应用场景不允许自环。5.3 图很大的时候这个实现扛得住吗先说结论扛不住。Fleury算法本身的复杂度是O(E^2)因为每条边被试探的时候都可能做一次全图BFS。Matlab在处理矩阵运算时很快但这种带循环的BFS恰恰是它的短板所以图一大了就会明显变慢。我实测过一个1000个顶点、3000条边的图这个实现大概要跑几十秒。如果你要处理的是这种规模有几个优化思路第一把连通性判断从“每次删边后全图BFS”改成“只判断当前顶点到目标顶点的连通性”可以借助并查集union-find实现接近O(1)的查询。不过并查集在删边场景下需要可回滚版本实现复杂度高不少。第二改用Hierholzer算法。这个算法是O(E)的思路更简单随便走一条回路然后把回路上的每个顶点再递归扩展子回路最后合并。如果你不需要交“Fleury算法”的作业处理大规模图的时候建议直接用Hierholzer。第三如果你非要用Fleury可以考虑用C写核心循环用Matlab调用MEX文件。但这个开发成本就高了一般课设没必要。我的建议是100个顶点以内的中小图放心用我这个版本超过这个规模要么优化要么换算法别硬扛。5.4 一个调试小技巧把每一步的“当前顶点、候选邻居、桥判断结果”都打印出来最后分享一个我在调试阶段屡试不爽的方法。在while循环里加几行打印fprintf(当前顶点: %d\n, cur); fprintf(候选邻居: %s\n, mat2str(neighbors)); if ~isempty(next) fprintf(选择顶点: %d (非桥边)\n, next); else fprintf(选择顶点: %d (被迫走桥)\n, neighbors(1)); end跑一个小图盯着打印结果一步一步核对跟你在纸上手推的过程比对。一旦哪一步和手推结果不一样bug就在那一轮循环里。这种“打印大法”看起来土但排查逻辑错误时比任何调试器都好使因为它直接告诉你算法的决策过程。我个人实际用下来Fleury算法的代码里最容易出问题的不是主流程反而是那些看起来“理所当然”的小细节对称位置有没有同步更新、删除边后为什么连通性判断会误报、多重边要不要当两条边处理。把这些坑填平之后这个算法其实很简单。你要是交作业记得把验证函数和可视化代码也一起放进去老师看到你不仅跑出了结果还验证了正确性分数一般不会低。后面如果你想处理有向图的欧拉回路或者想把性能提上去从Hierholzer算法入手就好那又是另一个故事了。