几种算法递推解的理解

Question

大多数情况下，我们需要理解其他人的代码--例如，我正在研究Sedgewick的在线资源中的图算法，具体的代码示例取自循环检测算法这里：

 private void dfs(Graph G, int u, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {

            // short circuit if cycle already found
            if (cycle != null) return;

            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, v, w);
            }

            // check for cycle (but disregard reverse of edge leading to v)
            else if (w != u) {
                cycle = new Stack<Integer>();
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
    }

虽然我知道算法的基本原理(找到后面的边缘)，并且从代码中可以看出，它也试图存储生成的循环，但我无法跟踪算法将如何执行，以及为什么作者在dfs代码中增加了一个参数。一般来说，我应该如何继续理解这样的递归算法？

Answer 1

这个dfs算法在图G中寻找一个循环，从v开始，“额外参数"u是搜索树中v的”前一个“或”父“节点，它在这里传递是因为它使算法能够避免在循环中接受像”u u“这样的序列。

理解代码有时并不容易，需要实践，尤其是递归代码。有几种技术，比如添加注释、“划痕重构”、在调试器中运行代码(如Robert Harvey建议的那样)、向代码中添加日志语句并运行它、或在一张纸上绘制一个示例并使用铅笔“执行它”。只有你才能找出哪种技术最适合你和你的具体情况。