Найти схему в прямом графике

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

} 

}