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

喜欢ヅ旅行 2022-12-28 00:56 119阅读 0赞

判断一个有向图是否存在回路，除了采用拓扑算法以外，还可以使用深度优先搜索算法，本算法改编自“用邻接矩阵表示的深度优先搜索算法”，即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.输入输出样例如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/7e2ad5d6f57c4671b6b19bd135c68ed8.png