Глубины первого поиск с использованием списка смежности

Question

Я пытаюсь unterstand код ниже, но there's что-то не ясно, в функции DFS

введите код здесь

#include<stdio.h> 

typedef struct node 
{ 
    struct node *next; 
    int vertex; 
}node; 

node *G[20]; 

int visited[20]; 
int n; 
void read_graph(); 
void insert(int,int); 
void DFS(int); 

void main() 
{ 
    int i; 
    read_graph(); 
    //initialised visited to 0 

    for(i=0;i<n;i++) 
     visited[i]=0; 

    DFS(0); 
} 

void DFS(int i) 
{ 
    node *p; 

    printf("\n%d",i); 
    p=G[i]; 
    visited[i]=1; 
    while(p!=NULL) 
    { 
     i=p->vertex; 
     if(!visited[i]) 
      DFS(i); 
     p=p->next; 
    } 
} 

void read_graph() 
{ 
    int i,vi,vj,no_of_edges; 
    printf("Enter number of vertices:"); 

    scanf("%d",&n); 

    //initialise G[] with a null 

    for(i=0;i<n;i++) 
    { 
     G[i]=NULL; 
     //read edges and insert them in G[] 

     printf("Enter number of edges:"); 
     scanf("%d",&no_of_edges); 

     for(i=0;i<no_of_edges;i++) 
     { 
      printf("Enter an edge(u,v):"); 
      scanf("%d%d",&vi,&vj); 
      insert(vi,vj); 
     } 
    } 
} 

void insert(int vi,int vj) 
{ 
    node *p,*q; 

    //acquire memory for the new node 
    q=(node*)malloc(sizeof(node)); 
    q->vertex=vj; 
    q->next=NULL; 

    //insert the node in the linked list number vi 
    if(G[vi]==NULL) 
     G[vi]=q; 
    else 
    { 
     //go to end of the linked list 
     p=G[vi]; 

     while(p->next!=NULL) 
      p=p->next; 
     p->next=q; 
    } 
} 

как делает откат произойдет после завершения времени цикл в функции DFS()? Я не получить его

Thx

Answer 1

Ну, это не ДФС (Depth First Поиск), так как ничего не искали. Все, что делает ваша функция DFS, пересекает все ребра, отмечая их узлы как посещенные. После того, как вы закончите, вы знаете только, является ли это подключенным графиком - если есть какие-либо ребра, которые не были посещены, то они не были помечены, и поэтому не может быть достигнуто от G[0].

Answer 2

исходный код не мой .. я только что нашел на этом сайте: http://www.thecrazyprogrammer.com/2014/03/depth-first-search-dfs-traversal-of-a-graph.html