Цикл в направленном графе

Question

Я пытаюсь найти, существует ли цикл в ориентированном графе. Каковы могут быть подходы? Также алгоритм поможет ..

Я реализовал график, используя список смежности и все работает правильно до сих пор

Код

#include<stdio.h> 
#include<stdlib.h> 
typedef struct Graph 
{ 
    int vertex; 
    struct Graph *next; 
}Graph; 
Graph *g[10]; 
void initializeGraph(int n) 
{ 
    int i; 
    for(i=0;i<n;i++) 
    { 
     g[i]=(Graph*)malloc(sizeof(Graph)); 
     g[i]->vertex=i; 
     g[i]->next=NULL; 
    } 
} 
void addEdge(int v,int u) 
{ 

    Graph *head=g[v]; 
    while(head->next) 
     head=head->next; 
    head->next=(Graph*)malloc(sizeof(Graph)); 
    head=head->next; 
    head->next=NULL; 
    head->vertex=u; 

} 
void printGraph(int n) 
{ 
    Graph *head; 
    int i; 
    for(i=0;i<n;i++) 
    { 
     head=g[i]; 
     printf("\n"); 
     while(head) 
     { 
      if(head->next) 
       printf("%d ---> ",head->vertex); 
      else 
       printf("%d ",head->vertex); 
      head=head->next; 
     } 
    } 

} 
void checkCycle(int v,int n) 
{ 
} 
int main() 
{ 
    int n,e,i,a[100],v,u; 
    printf("\nEnter the number of vertices - "); 
    scanf("%d",&n); 

    initializeGraph(n); 
    printf("\nEnter the number of edges - "); 
    scanf("%d",&e); 

    printf("\nVertices are - "); 
    for(i=0;i<n;i++) 
     printf("%d ",i); 


    printf("\nEnter the edges separated by space - "); 
    for(i=0;i<e;i++) 
    { 
     scanf("%d%d",&v,&u); 
     addEdge(v,u); 
    } 
    printGraph(n); 
    checkCycle(0,n); 
    printf("\n\n"); 
} 

Кроме того, если кто-то может выполнить функцию, которая 'действительно быть полезным! Благодаря

** EDIT1: ** Я попробовал этот

//Global arrays - visited[],isCycle[] 
//visited[] is initialized to 0 
//isCycle[] initialized to -1  

//Method call : checkCycle(0,n); 

int checkCycle(int v,int n) 
{ 
    Graph *head; 
    int w; 
    visited[v]=1; 
    head=g[v]->next; 
    while(head) 
    { 
     w=head->vertex; 
     if(visited[w]) 
      return 1; 

     if(isCycle[w]==-1) 
      checkCycle(w,n);  //We haven't visited that vertex yet 
     else 
      return 0;   //We visited this vertex before but a cycle was not found 
     head=head->next; 
    } 
    visited[v]=0; 
    isCycle[v]=0; 
    return 0; 

} 


**Sample Input 1** - 
Enter the number of vertices - 4 

Enter the number of edges - 4 

Vertices are - 0 1 2 3 
Enter the edges separated by space - 0 1 
1 2 
2 3 
3 0 

0 ---> 1 
1 ---> 2 
2 ---> 3 
3 ---> 0 


Cycle Does not exist 


**Sample Input 2**- 
Enter the number of vertices - 4 

Enter the number of edges - 3 

Vertices are - 0 1 2 3 
Enter the edges separated by space - 0 1 
1 2 
2 3 

0 ---> 1 
1 ---> 2 
2 ---> 3 
3 


Cycle Does not exist 

ПРИМЕЧАНИЕ: В любом случае ВЫВОД IS - цикл не существует.

Answer 1

в разделе «Редактировать 1»: вы всегда получаете «Цикл не существует», потому что вы не возвращаете правильный ответ, когда он найден.

единственная ошибка в вашей программе в проверке состояния в

if(isCycle[w] == -1) 
     return checkCycle(w, n); 

до этого вы не возвращает правильный ответ, чтобы по умолчанию вы посылали неправильный ответ т.е., возвращать ложь. :)

Happy Coding !!!