代码之家 › 专栏 › 技术社区 › int3

如何使用循环查找算法查找欧拉路径?

graph language-agnostic algorithm

int3 · 技术社区 · 15 年前

我正试图理解所描述的算法 here 但解释不太清楚:

'tour' is a stack

find_tour(u):
    for each edge e=(u,v) in E:
        remove e from E
        find_tour(v)
    prepend u to tour

to find the tour, clear stack 'tour' and call find_tour(u),
where u is any vertex with a non-zero degree.

“预先准备”是什么意思 u 堆栈?里面的元素怎么样 tour 甚至用于 find_tour ?如果有人能向我解释,我会很高兴的,谢谢!

2 回复 | 直到 11 年前

Matti Lyra 15 年前

堆栈“prepend”是一个push。所以将顶点U推到堆栈顶部。其思想是,从任何顶点开始,该顶点上至少有一条边。跟随所有边,离开开始顶点,在删除边后递归调用函数(这样您就不会返回同一条边)。

巡演中的元素根本没有被“发现巡演”使用。它只是一个数据存储区,用于恢复算法完成后图形的遍历顺序。要返回巡更,只需继续调用tour.pop(),直到堆栈为空。如果该顶点有许多边,它可能多次包含相同的顶点,但因为每次在递归调用“查找”程序之前,都会删除保留顶点的边,因此函数最终将完成。

oh和e是图中所有的边,(u,v)是从u到v的边。

PerseP 12 年前

该算法适用于有向图。对于无向图,请记住:

(u,v) == (v, u)

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前