判断一个有向图是否存在回路

判断一个有向图是否存在回路，除了采用拓扑算法以外，还可以使用深度优先搜索算法，本算法改编自“用邻接矩阵表示的深度优先搜索算法”，即DFS算法，两者共同点均为递归调用,DFS算法已在注释中标出，可进行对比学习。loop函数无论是强连通图和非强连通图均能判断出是否存在回路。

在loop函数中
1.visited数组用于记录被访问过的节点，和DFS算法中的visited数组相同。
2.count数组只有一个元素即count[0]，初始值为1，若能找到回路,则count[0]=1；为什么用count[0]而不直接用int count变量？因为loop函数中要进行很多次递归调用，若用count变量，当形参改变时，实参的值并不能跟着改变，无法判断count的值是否改变。若是能找到回路，count[0]++只执行一次，即变为1.
3.形参source为源节点，以source为源节点，loop在遍历过程中是否能回到source节点,若能回到source节点，则存在回路。
4.形参s用于记录source节点，在loop函数不断递归过程中,source的值回不断的改变，无法知道源节点是哪个，故需要一个s来记录source 节点，s在递归过程中始终不变。

void loop(GraphMatrix *graphMatrix,int *visited,int source,int s,int *count)
{
    int j;
    visited[source]=1//源节点被遍历到，记录为1;
    for(j=0;j<graphMatrix->size;j++)
    {
        if(graphMatrix->graph[source][j]!=MAX&&j==s)//在每一次使用loop函数中，count[0]++其实只执行一次
        {   count[0]++;
            printf("%d",count[0]);
        }

        if(graphMatrix->graph[source][j]!=MAX&&!visited[j])//若有节点还为遍历到，则继续递归
            loop(graphMatrix,visited,j,s,count);
    }
}

/*void DFS(GraphMatrix*graphMatrix,int* visited,int source)
{
    int j;
    visited[source]=1;
    printf("%d",source)
    for(j=0;j<graphMatrix;j++)
    {
        if(graphMatrix->graph[soure][j]!=MAX&&!visited[j])
            DFS(graphMatrix,visited,j);
    }
}*/

完整代码如下

#include <stdio.h>
#include <stdlib.h>
#define MAX 0
typedef struct GRAPHMATRIX_STRU
{
    int size;
    int **graph;
}GraphMatrix;

GraphMatrix* InitGraph(int num)
{
    int i,j;
    GraphMatrix *graphMatrix=(GraphMatrix*)malloc(sizeof(GraphMatrix));
    graphMatrix->size=num;
    graphMatrix->graph=(int**)malloc(sizeof(int*)*graphMatrix->size);
    for(i=0;i<graphMatrix->size;i++)
        graphMatrix->graph[i]=(int*)malloc(sizeof(int)*graphMatrix->size);
    for(i=0;i<graphMatrix->size;i++)
    {
        for(j=0;j<graphMatrix->size;j++)
        graphMatrix->graph[i][j]=MAX;

    }
    return graphMatrix;
}
void ReadMatrix(GraphMatrix*graphMatrix)
{
    int vex1,vex2;
    scanf("%d%d",&vex1,&vex2);
    while(vex1!=-1||vex2!=-1)
    {
        graphMatrix->graph[vex1][vex2]=1;
        scanf("%d%d",&vex1,&vex2);
    }

}
void loop(GraphMatrix *graphMatrix,int *visited,int source,int s,int *count)
{
    int j;
    visited[source]=1//源节点被遍历到，记录为1;
    for(j=0;j<graphMatrix->size;j++)
    {
        if(graphMatrix->graph[source][j]!=MAX&&j==s)//在每一次使用loop函数中，count[0]++其实只执行一次
        {   count[0]++;
            printf("%d",count[0]);
        }

        if(graphMatrix->graph[source][j]!=MAX&&!visited[j])//若有节点还为遍历到，则继续递归
            loop(graphMatrix,visited,j,s,count);
    }
}

/*void DFS(GraphMatrix*graphMatrix,int* visited,int source)
{
    int j;
    visited[source]=1;
    printf("%d",source)
    for(j=0;j<graphMatrix;j++)
    {
        if(graphMatrix->graph[soure][j]!=MAX&&!visited[j])
            DFS(graphMatrix,visited,j);
    }
}*/
int main()
{
    int num=7;//节点个数为7个，可将num改为输入方式，节点个数动态定义
    int i=0,j;
    int count[1]={0};//count[1]=0则不存在回路，count[1]=1则存在回路
    int *visited=(int*)malloc(sizeof(int)*num);
   GraphMatrix *graphMatrix;
   //初始化邻接矩阵
   graphMatrix=InitGraph(num);
   ReadMatrix(graphMatrix);
   //从0开始判断每一个节点是否能存在回路
   for(i=0;i<(graphMatrix->size);i++)
   {
       if(count[0]!=0)//若oount变为1，则已存在回路，不需要再进行下去了
       break;
       for(j=0;j<graphMatrix->size;j++)//每一次都 visited数组元素全部初始化，因为每次循环都是不同的源接待你
       {
           visited[j]=0;
       }
       loop(graphMatrix,visited,i,i,count);

   }
   if(count[0]==0)
    printf("0");
   return 0;
}

若存在回路则输出1，否则输出0.输入输出样例如下