在直接图中查找电路

Question

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

Answer 1

可能是这个提示将帮助：

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

Answer 2

DFS会找到一个循环。

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

Answer 3

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

{ INT I;

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); 

} 

}