直接グラフ内の回路を見つける

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) 

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

} 

}