不可否认，欧拉回路与欧拉路径是图论中的经典概念之一。若图中的一条路径从某个节点出发，经过每条边恰好一次，并回到起点，则称该路径为欧拉回路。若只要求路径经过每条边恰好一次，不要求其回到起点，则称该路径为欧拉路径。

这些算法问题看似抽象，然而欧拉回路、欧拉路径乃至整个图论的研究领域，都起源于实际生活中的问题。

本文将从哥尼斯堡的居民们在散步过程中提出的谜题开始，向各位介绍欧拉回路与欧拉路径的相关概念与算法。

哥尼斯堡七桥问题

在 18 世纪初，普鲁士的哥尼斯堡（今日俄罗斯的加里宁格勒）被普列戈利亚河分成了南北两岸，河中心还有两座岛屿。岛屿与河的两岸由七座桥连接，如下图所示。

当时，当地居民在桥上散步的过程中，逐渐产生了一项有趣的消遣活动：找到一条从任意地点出发的路径，经过每座桥恰好一次，并回到出发点。

这个谜题看似简单，然而许多年过去了，都没有人找到符合要求的路径。1735 年，时年 28 岁的数学家欧拉也听说了这一问题。经过了一段时间的研究后，欧拉对该问题做出了分析。

实践出真知

俗话说，实践出真知。遇到一下子难以解决的算法问题时，不妨先在草稿纸上分析一些简单的例子，可能会对问题产生新的洞见。因此，在讲解欧拉的分析之前，让我们先来动手试一试，看能否有所发现。

例如，从河的南岸出发，我们可能会走出如下路径。

上图的路径中，我们将被“困在”左边的岛屿 上无法离开，且还有一座桥未被经过。您还可以尝试其它路径。可以发现，您将总是被“困在”一片不同于起点的地区，且无法通过一座未被经过的桥离开。这不禁让我们思考：一片地区需要满足怎样的条件，才能让我们总是有机会从该地区离开？

让我们考虑任意一片与起点不同的地区。为了进入该地区，我们需要“消耗”一座桥；同时，为了从该地区离开，我们需要“消耗”另一座桥。也就是说，用来进入该地区的桥，和用来离开该地区的桥，数量必须相等。因此，连接该地区的桥的数量必须为偶数。

然而，在哥尼斯堡七桥问题中，连接地区 的桥梁为 座，、、 的桥梁为 座，均为奇数。因此可以推断，经过每座桥恰好一次，并回到出发点的路径并不存在。