了解 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;
}

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

Answer 1

有向图是可以的。假设我们有一个有 2 个顶点和 1 条边的图：2 -> 1。如果我们从第一个顶点开始深度优先搜索，它将在我们访问第二个顶点时处理。所以边 2 -> 1 将导致处理的顶点。但是，无向图是不可能的。
我同意你的看法。

在我看来，此代码的主要问题在于它试图同时处理：有向图和无向图，这使得逻辑不清晰且难以理解。使用深度优先搜索检测图中的循环实际上非常简单，所以我只建议找到一个更好的实现（或自己制作，分别处理有向图和无向图）。

Answer 2

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这样的边。你会认为这是一个循环吗？无论哪种方式你都不会错。这只是定义的问题。对于教科书，通常使用让作者提出最方便（最容易理解）解决方案的定义。

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

Understanding Skiena's algorithm to detect cycles in a graph

algorithm

graph

depth-first-search