有向图中的循环

我试图找到循环是否存在于有向图中。 它可以是什么方法？同样算法将帮助..有向图中的循环

我用邻接表来实现图形和一切工作的权利到目前为止

代码

#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"); 
}

此外，如果任何人都可以完成的功能，即'd真的很有帮助！感谢

** 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

注意：在任何情况下输出为 - 周期不存在。

来源

2015-02-07 psychoCoder

请添加您用来测试您的逻辑的样本输入数据。 – 2015-02-07 09:02:51

@RSahu现在添加所有细节！ – psychoCoder 2015-02-07 09:19:59

函数checkCycle中'n'的用途是什么？它永远不会被读取，而是递归地传递给下一个调用。为什么你要在函数体的末尾重置visited []'？ – Codor 2015-02-07 09:24:11

编辑1部分：您总是收到“循环不存在”，因为您找不到正确的答案。

在程序中唯一的错误是在

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

状态检查在此之前那么在默认情况下你发送错误的答案，即你没有返回正确的答案，返回false。 :)

快乐编码！

来源

2015-02-07 11:08:43 vkrishna17

有向图中的循环

回答

相关问题