在有向图中循环

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

另外，如果有人能完成这个功能，那将是非常有帮助的！谢谢

**编辑1：** 我试过这个

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

注意：在每种情况下输出都是 - 循环不存在。

Answer 1

在编辑 1 部分：你总是得到 "Cycle doesnt exists" 因为你没有 return 找到正确的答案。

您程序中唯一的错误是

的条件检查

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

在此之前你没有 return 得到正确的答案，所以默认情况下你发送的是错误的答案，即 return 错误。 :)

编码愉快！！！

在有向图中循环

Cycle in a directed graph

c

graph

directed-graph