algorithm - 了解 Skiena 的算法以检测图中的循环

Question

我无法理解 Skeina 算法中的所有内容以检测图形中的循环，无论是有向的还是无向的

void process_edge(int v, int y) {
    // if parent[v] == y it means we're visitng the same edge since this is unweighted?
    // y must be discovered otherwise this is the first I'm seeing it?
    if (discovered[y] && parent[v] != y) {
        printf("\nfound a back edge (%d %d) \n", v, y);
    }
}

void DFSRecursive(graph *g, int v) {
    discovered[v] = true;

    edge *e = g->edges[v];
    while (e != NULL) {
        int y = e->y;
        if (discovered[y] == false) {
            parent[y] = v;
            DFSRecursive(g, y);
        } else if (!processed[y] || g->directed) { // can't be processed and yet has an unvisited kid!?
            process_edge(v, y, data);
        }
        e = e->next;
    }

    processed[v] = true;
}

1. 我们为什么要检查 !processed[y]？如果我们看到一个邻居 y 并且它已经被发现(第一个 if 条件)，怎么可能已经处理了 y？鉴于 v 是一个邻居，我们刚刚发现它？
2. 我对 parent[v] !== y 的检查感到困惑，但我想这在未加权图的情况下是有意义的，如果我们有一个只有两个节点的图，两个节点彼此相邻，所以这不是循环。我不清楚为什么它在定向情况下有意义，因为 1->2 和 2->1 被认为是一个循环，对吧？
3. 我对过程边缘方法中的第三个条件 discovered[y] 没有问题，因为如果它未被发现，这将意味着这是我们第一次看到它

Answer 1

I was confused with the check for parent[v] !== y but I guess it makes sense in the unweighted graph case, if we have a graph with just two nodes, both nodes have each other in their adjacency so this is not a cycle. I'm not clear though on why it would make sense in the directed case because 1->2 and 2->1 is considered a cycle, right?

我不同意其他答案。 cycle不会多次访问边，否则任何具有边的图，无论是否有向，都会有一个循环。书上给出的算法是正确的。仅无向图需要检查，但我认为代码可以非常干净地处理这两者。

如果您指的是我们可能有两条有向边的情况​​:

1 -> 2
2 -> 1

那么你是否认为这是一个循环是值得商榷的。一般来说，有向图被认为不存在这种情况。我可以将这样的一对解释为无向边，然后将它走两次就没有意义了。您可以将其解释为两条有向边，然后您就可以认为算法是错误的。但这只会对您的解释造成错误。

对于最常用(且最容易理解)的解释，该算法会执行它应该执行的操作。

作为另一个例子，也可以允许像 1 -> 1 这样的边。你会认为这是一个循环吗？无论哪种方式你都不会错。这只是定义的问题。对于教科书，人们通常使用让作者提出最方便(最容易理解)解决方案的定义。