企业官网建设流程全解析

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 的矩阵 adj，adj(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(end+1) = 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(end+1) = v; end end end cnt = sum(visited); end

3.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)级别的，路径长度又只有E+1，动态拼接的性能损失可以忽略。我试过预先分配然后用指针维护，代码复杂度和出错概率都会上升，得不偿失。

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（两条边），度是1+1+2=4，偶数。顶点2连1、3、5，度=1+1+1=3，奇数。那要加一条边。算了，我不在博文里硬凹这个具体度数。测试图我换一个确定能跑通的，代码示例里给一个简单的正方形加一条对角线的结构，或者干脆用一个我验证过的图。这里我重新构造一个简单的：

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 = 总边数6+1，正确。顶点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(i+1); 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(i+1); 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算法入手就好，那又是另一个故事了。