algorithm - 只走一次无向图的所有边

Question

我正在寻找一种算法，它会告诉我是否有可能只走一次单向图的所有边。该算法必须能够从任何节点开始并遍历整个图，而无需重新访问同一条边。

Answer 1

您正在寻找的东西被称为欧拉路径，如果您的图满足必要条件，维基百科描述了几种构造一个算法。

Answer 2

柯尼斯堡七桥是欧拉路径的经典例子。

Hierholzer 的算法，来自 Wikipedia：

选择任何起始顶点 v，并沿着从该顶点开始的边轨迹直到返回 v。不可能卡在除 v 之外的任何顶点，因为所有顶点的度数相等，确保当轨迹进入另一个顶点时w 必须有一条未使用的边离开 w。这样形成的游览是一个封闭的游览，但可能不会覆盖初始图的所有顶点和边。

只要存在属于当前游览但相邻边不属于游览的顶点 v，则从 v 开始另一条路径，沿着未使用的边直到返回 v，并将以这种方式形成的游览加入前一个旅游。

通过使用诸如双向链表之类的数据结构来维护入射到每个顶点的未使用边的集合，维护当前游览中具有未使用边的顶点列表，并维护游览本身，算法（找到退出每个顶点的未使用边，为一个旅行找到一个新的起始顶点，并连接两个共享一个顶点的旅行）可以在每个固定时间执行，因此整个算法需要线性时间。