c++ - 在有向图中查找电路

Question

我想在有向图中找到一个电路，这个电路从一个特定的顶点开始，到它结束。我使用邻接表数据结构来创建这个图，但我不知道算法会如何，请帮助我。非常感谢

Answer 1

可能这个提示会有所帮助：

1. 遍历图（任何算法 - BFS DFS）
2. 您访问过的颜色节点并存储其父节点
3. 检查您正在遍历的节点是否已经着色，然后循环回其父节点，直到获得相同的节点。

Answer 2

DFS 会找到一个循环。

http://en.wikipedia.org/wiki/Cycle_%28graph_theory%29

Answer 3

void DFS (Node* ptr , int node , int index , int n )

{诠释我;

if ( ptr == NULL)
{
    ptr=arrNode[index].next;
    node = ptr->vertex;
}

for ( int i=0 ; i < n ; i++)
{
    if ( ( node == arrNode[i].vertex) && (ptr->visit=false))
    {
        ptr=arrNode[i].next;
        ptr->visit = true;
        s.push(arrNode[i].vertex);
    }
    ptr=ptr->next;
    DFS(ptr,ptr->vertex,i+1 , n );

}

}