判断有向图是否存在环的2种方法（深度遍历，拓扑排序）

2023-12-28 17:24| 来源: 网络整理| 查看: 265

此题是美团2017春招实习生在线笔试题，题目是“如何判断有向图有没有回路”，这里给出两种解法以供参考。

解法一：深度遍历

假设图以邻接矩阵表示，一条深度遍历路线中如果有结点被第二次访问到，那么有环。我们用一个变量来标记某结点的访问状态（未访问，访问过，其后结点都被访问过），然后判断每一个结点的深度遍历路线即可。因为采用邻接矩阵存储，一般至少需要将矩阵中元素的一半给过一下，由于矩阵元素个数为n^2，因此时间复杂度就是O(n^2)。如果采用邻接表存储，则只存储了边结点(e条边，无向图是2e条边)，加上表头结点为n（也就是顶点个数），因此时间复杂度为O(n+e)。 Java实现如下：

import java.util.Scanner; public class test2 { //邻接矩阵 static int[][] graph = new int[200][200]; //结点个数和边的个数 static int vNum,eNum; //标记矩阵,0为当前结点未访问,1为访问过,-1表示当前结点后边的结点都被访问过。 static int[] color = new int[200]; //是否是DAG（有向无环图） static boolean isDAG = true; //图的深度遍历函数 void DFS(int i){ System.out.println("正在访问结点"+i); //结点i变为访问过的状态 color[i] = 1; for(int j=1;j //并且已经被访问过 if(color[j] == 1){ isDAG = false;//有环 break; }else if(color[j] == -1){ //当前结点后边的结点都被访问过，直接跳至下一个结点 continue; }else{ DFS(j);//否则递归访问 } } } //遍历过所有相连的结点后，把本节点标记为-1 color[i] = -1; } //创建图,以邻接矩阵表示 void create(){ Scanner sc = new Scanner(System.in); System.out.println("正在创建图，请输入顶点个数vNum："); vNum = sc.nextInt(); System.out.println("请输入边个数eNum："); eNum = sc.nextInt(); //初始化邻接矩阵为0（如果3个顶点，顶点分别是1，2，3） for(int i=1;i graph[i][j] = 0; } } //输入边的情况 System.out.println("请输入边的头和尾:"); for(int k=1;k color[i] = 0; } } public static void main(String[] args) { test2 t = new test2(); t.create(); //保证每个节点都遍历到，排除有的结点没有边的情况 for(int i=1;i continue; } t.DFS(i); if(!isDAG){ System.out.println("有环！"); break; } } if(isDAG){ System.out.println("没环。。。"); } } }

测试输入输出如下：

正在创建图，请输入顶点个数vNum： 5 请输入边个数eNum： 5 请输入边的头和尾: 1 2 2 3 3 4 2 5 5 4 正在访问结点1 正在访问结点2 正在访问结点3 正在访问结点4 正在访问结点5 没环。。。解法二：拓扑排序

方法是重复寻找一个入度为0的顶点，将该顶点从图中删除（即放进一个队列里存着，这个队列的顺序就是最后的拓扑排序，具体见程序），并将该结点及其所有的出边从图中删除（即该结点指向的结点的入度减1），最终若图中全为入度为1的点，则这些点至少组成一个回路。采用邻接矩阵存储时，遍历二维数组，求各顶点入度的时间复杂度是O(n^2)。遍历所有结点，找出入度为0的结点的时间复杂度是O(n)。对于n个入度为0的结点，删除他们的出边的复杂度为O(n^2)。所以总的复杂度为O(n^2)。对于邻接表，遍历所有边，求各顶点入度的时间复杂度是O(e)，即边的个数。遍历所有结点，找出入度为0的结点的时间复杂度是O(n)，即顶点的个数。遍历所有边，删除入度为0的结点的出边的复杂度为O(e)，即边的个数。所以总的时间复杂度是O(n+e)。 Java实现如下：

import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class test1 { //邻接矩阵 static int[][] graph = new int[200][200]; //结点个数和边的个数 static int vNum,eNum; //记录每个结点的入度，初始化为0 static int[] count = new int[200]; //用队列保存拓扑序列 static Queue queue = new LinkedList(); //拓扑排序 void topoSort(){ //入度为0的结点的个数，也就是入队个数 int number = 0; //暂时存放拓扑序列 Queue temp = new LinkedList(); //遍历图中所有结点，找入度为0的结点删除（放进队列） for(int i=1;i queue.offer(i); } } //删除这些被删除结点的出边（即对应结点入度减一） while(!queue.isEmpty()){ int i = queue.peek(); temp.offer(queue.poll()); number++; for(int j=1;j count[j] -= 1; //出现了新的入度为0的结点，删除 if(count[j] == 0){ queue.offer(j); } } } } if(number != vNum){ System.out.println("最后存在入度为1的结点，这个有向图是有回路的。"); }else{ System.out.println("这个有向图不存在回路，拓扑序列为：" + temp.toString()); } } //创建图,以邻接矩阵表示 void create(){ Scanner sc = new Scanner(System.in); System.out.println("正在创建图，请输入顶点个数vNum："); vNum = sc.nextInt(); System.out.println("请输入边个数eNum："); eNum = sc.nextInt(); //初始化邻接矩阵为0（如果3个顶点，顶点分别是1，2，3） for(int i=1;i graph[i][j] = 0; } } //输入边的情况 System.out.println("请输入边的头和尾:"); for(int k=1;k for(int j=1;j count[j] = count[j] + 1; } } } } public static void main(String[] args) { test1 t = new test1(); t.create(); t.topoSort(); } }

【本文地址】

公司简介

联系我们