algorithm - 如果在递归堆栈中找到顶点，则在有向图中检测到循环 - 为什么？

Question

我读过一篇来自 here 的文章关于如何检测有向图中的循环。该算法的基本概念是，如果在递归堆栈中找到一个节点，则存在一个循环，但我不明白为什么。这是什么逻辑？

#include<iostream>
#include <list>
#include <limits.h>

using namespace std;

class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // Pointer to an array containing adjacency lists
    bool isCyclicUtil(int v, bool visited[], bool *rs);
public:
Graph(int V);   // Constructor
void addEdge(int v, int w);   // to add an edge to graph
bool isCyclic();    // returns true if there is a cycle in this graph
};

Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}


bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
if(visited[v] == false)
{
    // Mark the current node as visited and part of recursion stack
    visited[v] = true;
    recStack[v] = true;

    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator i;
    for(i = adj[v].begin(); i != adj[v].end(); ++i)
    {
        if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
            return true;
        else if (recStack[*i])
            return true;
    }

}
recStack[v] = false;  // remove the vertex from recursion stack
return false;
}


bool Graph::isCyclic()
{
// Mark all the vertices as not visited and not part of recursion
// stack
bool *visited = new bool[V];
bool *recStack = new bool[V];
for(int i = 0; i < V; i++)
{
    visited[i] = false;
    recStack[i] = false;
}


for(int i = 0; i < V; i++)
    if (isCyclicUtil(i, visited, recStack))
        return true;

return false;
}

int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

if(g.isCyclic())
    cout << "Graph contains cycle";
else
    cout << "Graph doesn't contain cycle";
return 0;
}

Answer 1

简单看一下，代码片段是depth-first search的实现。 ，这是有向图的基本搜索技术；同样的方法适用于 breadth-first search .请注意，显然此实现仅在只有一个连接组件时才有效，否则必须对每个连接组件执行测试，直到找到一个循环。

也就是说，该技术通过随意选择一个节点并在那里开始递归搜索来工作。基本上，如果搜索发现堆栈中的节点，则必须有一个循环，因为它之前已经到达。

在目前的实现中，recStack实际上并不是栈，它只是表示当前某个特定节点是否在栈中，不是存储序列信息。实际循环隐式包含在调用堆栈 中。循环是 isCyclicUtil 的调用尚未返回的节点序列。如果必须提取实际循环，则必须更改实现。