c++ - 有向グラフで回路を見つける

Question

Direct Graph で回路を見つけたいのですが、この回路は特定の頂点で始まり、そこで終わります。このグラフを作成するために隣接リストのデータ構造を使用していますが、アルゴリズムがどのようになるかわかりませんでした。助けてください。どうもありがとう

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

}

}