简单方法判断邻接矩阵的有向图是否有环
求解思路
实现代码
测试用例
知识背景

求解思路
1.统计所有节点的出度及其前序节点，初始化一个空的访问集合；

2.将出度为零的节点放入访问集合，并将其前序节点的出度数减1；

3.重复第2步骤，直到所有节点从头到尾完整遍历一遍；

4.判断已访问节点个数是否等于节点个数，是则有向图无环，否则有向图有环。
实现代码
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class AlgorithmUtil {
    /**
     * 判断有向图是否有环
     * 根据每个节点的入度和出度计算，把出度为零的依次去掉并更改其前序节点的出度个数，统计最后访问过的节点个数
     */
    public static boolean isDag(int[][] graph) {
        int nodeNum = graph.length;
        // 记录每个有入度的节点，及其所有的前序节点
        Map<Integer, List<Integer>> inEdge = new HashMap<>(nodeNum);
        // 记录每个节点的出度个数
        int[] outEdgeNum = new int[nodeNum];
        // 初始化数据
        for (int i = 0; i < nodeNum; i++) {
            for (int j = 0; j < nodeNum; j++) {
                if (graph[i][j] != Integer.MAX_VALUE) {
                    outEdgeNum[i]++;
                    if (inEdge.get(j) == null) {
                        List<Integer> list = new ArrayList<>();
                        list.add(i);
                        inEdge.put(j, list);
                    } else {
                        inEdge.get(j).add(i);
                    }
                }
            }
        }

        // 已访问的节点
        Set<Integer> visitedSet = new HashSet<>(nodeNum);
        // 循环遍历所有节点的出度
        while (visitedSet.size() < nodeNum) {
            for (int i = 0; i < nodeNum; i++) {
                if (outEdgeNum[i] == 0 && !visitedSet.contains(i)) {
                    visitedSet.add(i);
                    for (int temp = 0; inEdge.get(i) != null && temp < inEdge.get(i).size(); temp++) {
                        outEdgeNum[inEdge.get(i).get(temp)]--;
                    }
                    break;
                }
                // 节点遍历一遍后，判断是否访问了过所有节点
                if ((i == nodeNum - 1) && visitedSet.size() != nodeNum) {
                    return true;
                }
            }
        }

        return false;
    }
}

测试用例
import org.junit.Test;

public class AlgorithmUtilTest {

    private int NAN = Integer.MAX_VALUE;

    @Test
    public void isDag() {
        int[][] graph = new int[][] {{NAN, 1, 1, NAN}, {NAN, NAN, NAN, 1}, {NAN, NAN, NAN, 1}, {NAN, NAN, NAN, NAN}};
        assert !AlgorithmUtil.isDag(graph);
    }

    @Test
    public void isDag2() {
        int[][] graph = new int[][] {{NAN, 1, 1, NAN}, {1, NAN, NAN, 1}, {NAN, NAN, NAN, 1}, {NAN, NAN, NAN, NAN}};
        assert AlgorithmUtil.isDag(graph);
    }

    @Test
    public void isDag3() {
        int[][] graph = new int[][] {{NAN, 1, 1, NAN}, {NAN, NAN, NAN, 1}, {NAN, NAN, NAN, 1}, {1, NAN, NAN, NAN}};
        assert AlgorithmUtil.isDag(graph);
    }
}

知识背景
leetcode 207题  课程表

简单方法查找邻接矩阵有向图的有序集合

如有不同见解，欢迎留言讨论

这里的代码参考了很多别人的代码和文章。。
今天师兄做笔试题，我也跟着看，碰到了一个要构建有向图并判断节点是否有环的题。




另一位师兄说这个题可以用并查集做，并且做出来了，我用并查集试了试做不出来。。
我觉得这题大概是要用有向图做，考察有向图的构建及寻找有向环


但是我只会对着书本抄代码构建有向图，不会寻找环，就尝试了一下用前不久做爬虫用到的广度遍历来寻找有向环。。



import java.util.*;

public class test
{
	public static void main(String[] args)
	{
		UF uf = new UF();
		
		//构建有向图
		uf.AddDependency(1, 2);
		uf.AddDependency(2, 4);
		uf.AddDependency(4, 1);
		uf.AddDependency(1, 6);
		uf.AddDependency(6, 5);
		uf.AddDependency(5, 7);
		uf.AddDependency(4, 7);
		
		boolean isCycle;
		
		isCycle = uf.MouldelsCycularDependency(7);	//判断对应节点是否有环
				
		System.out.println(isCycle);
	}
}

class UF
{
	final int N = 10;	//节点个数
	//private static int E;
	static Stack<Integer>[] adj;
	
	public UF()	//创建一个N个节点但没有边的图
	{
		adj = (Stack<Integer>[]) new Stack[N];
		for(int n = 0; n < N;n++)
		{
			adj[n] = new Stack<Integer>();
		}
	}
	
	public static void addEdge(int v,int w)	//加边,v朝向w
	{
		adj[v].add(w);
	}
	
	public static Stack<Integer> adj(int v)
	{
		return adj[v];
	}
	
	public void clear()	
	{
		adj = (Stack<Integer>[]) new Stack[N];
		for(int n = 0; n < N;n++)
		{
			adj[n] = new Stack<Integer>();
		}
	}
	
	public static void AddDependency(int Moduleld, int DependModuleld)	//往图里加边
	{
		int v = Moduleld;
		int w = DependModuleld;
		
		addEdge(v,w);
	}
	 
	public static boolean MouldelsCycularDependency(int Moduleld)	//判断是否有环
	{
		int v = Moduleld;
		
		HashMap<Integer,Boolean> oldMap = new HashMap<Integer,Boolean>();
		
		for(int i: adj(v))
		{
			oldMap.put(i, false);
		}		
		
		oldMap = reDo(oldMap,v);
		
		if(oldMap.containsKey(v))
		{

			return true;
		}

		return false;
	}
	
	/**
	 * 广度优先遍历。递归，但是当N过大会StackOverFlow
	 * @param oldMap
	 * @param v 判断的节点
	 * @return
	 */
	public static HashMap<Integer,Boolean> reDo(HashMap<Integer,Boolean> oldMap,int v)	
	{
		//定义newMap
		HashMap<Integer,Boolean> newMap = new HashMap<Integer,Boolean>();
		
		for(Map.Entry<Integer, Boolean> k : oldMap.entrySet())
		{
			if(k.getValue() == false)
			{
				for(int i: adj(k.getKey()))
				{
					if(i == v)
					{
						oldMap.put(i, false);
						return oldMap;
					}
					if(!oldMap.containsKey(i))
					{
						newMap.put(i, false);
					}
				}	
				oldMap.replace(k.getKey(),false, true);
			}
		}
		
		//有新节点，继续遍历
		if (!newMap.isEmpty())
		{
			oldMap.putAll(newMap);
			oldMap.putAll(reDo(oldMap,v)); 
		}
		return oldMap;
	}	
}


有一个致命的缺点，题给的节点数目超多，上面代码进行递归的时候八成会StackOverflow。。


但还是很有成就感的，思考了一晚上至少把最基本功能实现了。。

本文主要针对如何判断有向图/无向图中是否存在环的问题进行简单的论述。

一 无向图

1.利用DFS进行判断

利用DFS判断有向图是否存在环，是最为常用的一种方法，虽然这种方法很常用，但可参考的代码的实现比较少，下面对这种方法及其实现进行详细的阐述。

首先，利用DFS判断无向图中是否换的原理是：若在深度优先搜索的过程中遇到回边(即指向已经访问过的顶点的边)，则必定存在环。

所以说，是否存在环的关键在于是否存在满足条件的“回边”，那么如何判断回边呢？

(1)首先，对图中的所有顶点定义三种状态：顶点未被访问过、顶点刚开始被访问、顶点被访问过并且其所有邻接点也被访问过。这三种状态，在visited数组中分别用0、1、2来表示。那么，存在环的情况可以定义为：在遍历过程中，发现某个顶点的一条边指向状态1的顶点，此时就存在环。状态2可以理解为其生成树上的所有的子孙节点都已经访问完。

(2)此外，我们要定义一个father数组，用以存储在DFS过程中顶点的父顶点(或者说是生成树上的父节点)。其主要作用是为了区分邻接点中环中的顶点和遍历过程中的父节点 (单纯的用visited数组无法区分)。

整个过程的实现代码如下：

 


			
1

			
2

			
3

			
4

			
5

			
6

			
7

			
8

			
9

			
10

			
11

			
12

			
13

			
14

			
15

			
16

			
17

			
18

			
19

			
20

			
21

			
22

			
23

			
24

			
25

			
26

			
27

			
28

			
29

			
30

			
31

			
32

			
33

			
34

			
35

			
36

			
37

			
38

			
39

			
40

			
41

			
42

			
43

			
44

			
45

			
46

			
47

			
48

			
49

			
50
			
			

			
#define MAX_NUM 100

			
#define INF 0x7fffffff

			
/*DFS判断无向图中是否有环*/

			
class Graph

			
{

			
    public:

			
    int vertexNum;//顶点个数

			
    int arcNum;//弧的个数

			
    int vertex[MAX_NUM];//顶点表

			
    int arc[MAX_NUM][MAX_NUM];//弧信息表

			
};

			
int visited[MAX_NUM];//顶点访问表

			
int father[MAX_NUM];//父节点表

			
void DFS(int v,Graph G)

			
{

			
    visited[v] = 1;

			
    for(int i = 0 ; i < G.vertexNum; i++)

			
    {

			
        if(i != v && G.arc[v][i] != INF)//邻接矩阵中节点v的邻接点

			
        {

			
            if(visited[i] == 1 && father[v] != i)//vi不是父节点，而且还访问过(而且为状态1，说明不是回溯过来的顶点)，说明存在环(判断i不是v的父节点)

			
            {

			
                cout<<"图存在环";

			
                int temp = v;

			
                while(temp != i)

			
                {

			
                    cout<<temp<<"<-";//输出环

			
                    temp = father[temp];

			
                }

			
                cout<<temp<<endl;

			
            }

			
            else

			
                if(visited[i] == 0)

			
                {

			
                    father[i] = v;//更新father数组

			
                    DFS(i,G);

			
                }

			
 

			
        }

			
    }

			
    visited[v] = 2;//遍历完所有的邻接点才变为状态2

			
}

			
void DFSTraverse(Graph G)

			
{

			
    memset(visited,0,sizeof(visited));

			
    memset(father,-1,sizeof(father));

			
    for(int i = 0 ; i < G.vertexNum; i++)

			
        if(!visited[i])

			
            DFS(i,G);

			
}
			
		
 

　　

 

 由此可见，visited数组相对于一般的情况，增加了个状态2，主要是为了防止在回溯过程中进行误判。所以才能仅用father数组和状态1判断存在环。

状态2可以理解为其生成树上的所有的子孙节点都已经访问完。

由于使用的是邻接矩阵来存储，所以该算法的时间复杂度为O(n^2),空间复杂度为O(n)。

2.其他方法本文不再详述。

二 有向图

1.拓扑排序

关于拓扑排序，资料很多，本文不再详述其原理，只给出其实现代码，代码如下：

 


			
1

			
2

			
3

			
4

			
5

			
6

			
7

			
8

			
9

			
10

			
11

			
12

			
13

			
14

			
15

			
16

			
17

			
18

			
19

			
20

			
21

			
22

			
23

			
24

			
25

			
26

			
27

			
28

			
29

			
30

			
31

			
32

			
33

			
34

			
35

			
36

			
37

			
38

			
39

			
40

			
41

			
42

			
43

			
44

			
45

			
46

			
47

			
48

			
49

			
50

			
51

			
52

			
53

			
54

			
55

			
56

			
57

			
58

			
59

			
60

			
61

			
62

			
63

			
64

			
65

			
66

			
67

			
68

			
69

			
70

			
71

			
72

			
73

			
74

			
75

			
76

			
77

			
78
			
			

			
#include<iostream>

			
#include<unordered_map>

			
#include<queue>

			
#include<cstring>

			
#include<cstdlib>

			
#include<cmath>

			
#include<algorithm>

			
#include<sstream>

			
#include<set>

			
#include<map>

			
#include<stack>

			
using namespace std;

			
#define MAX_NUM 100

			
#define INF 0x7fffffff

			
/*拓扑排序*/

			
int indegree[MAX_NUM];//用以表示每个顶点的入度

			
bool visited[MAX_NUM];//用以表示该顶点是否入栈

			
class Graph

			
{

			
public:

			
    int vertexNum;//顶点个数

			
    int arcNum;//弧的个数

			
    int vertex[MAX_NUM];//顶点表

			
    int arc[MAX_NUM][MAX_NUM]= {{0,1,1},{INF,0,1},{INF,INF,0}}; //弧信息表

			
};

			
void Initindegree(Graph G)//初始化入度数组

			
{

			
    memset(indegree,0,sizeof(indegree));

			
    for(int i = 0; i < G.vertexNum; i++)

			
        for(int j = 0; j < G.vertexNum; j++)

			
        {

			
            if(i != j && G.arc[i][j] != INF)

			
                indegree[j]++;//注意此处增加的是顶点vj的入度

			
        }

			
    memset(visited,0,sizeof(visited));

			
}

			
bool TuoPu(Graph G)

			
{

			
    stack<int> s;

			
    int cnt = 0;//用于记录拓扑序列中节点的个数

			
    for(int i = 0 ; i < G.vertexNum; i++)

			
        if(indegree[i] == 0)

			
        {

			
            s.push(i);

			
            visited[i] = true;//修改入栈顶点的入栈标记数组

			
 

			
        }

			
    while(!s.empty())

			
    {

			
        int v = s.top();

			
        cnt++;//顶点出栈得到时候，计数器加1

			
        s.pop();

			
 

			
        for(int i = 0; i < G.vertexNum; i++)

			
        {

			
            if(v != i && G.arc[v][i] != INF && visited[i] == false)//将所有顶点v的未入栈的邻接点的入度都减去1

			
            {

			
                indegree[i]--;

			
                if(indegree[i] == 0)//如果减1后入度为0了，此时需要将该邻接点入栈，且修改入栈标记数组

			
                {

			
                    visited[i] = true;

			
                    s.push(i);

			
                }

			
            }

			
 

			
 

			
        }

			
    }

			
    return cnt == G.vertexNum ? true : false;

			
}

			
int main()

			
{

			
    Graph G;

			
    G.vertexNum = 3;

			
    Initindegree(G);

			
    cout<<TuoPu(G)<<endl;

			
 

			
}
			
		
 

　　

 

2.利用改进的DFS

对于有向图的话，如果直接应用一般的DFS的话，会出现误判的情况，一个典型的例子是：A->B,A->C->B,我们用DFS来处理这个图，我们会得出它有环，但实际上并没有。然而，本文中所说的无向图的DFS判断算法完全可以直接应用到有向图中来，即上述代码可以直接应用到有向图中来。所以说上述的DFS算法(或称为为改进的DFS算法)既适用于无向图，也适用于有向图。其对应的原理适用于这两种图，即只要我们在遍历过程中，只要发现一个顶点不是当前节点的父节点，同时他还被访问过了(状态为1)，那么就可以认为此处存在环。(通常在DFS中一个顶点的未被访问的邻接点，相当于生成树中的该顶点的子孙节点)

此题是美团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<=vNum;j++){
			//如果当前结点有指向的结点
			if(graph[i][j] != 0){	
				//并且已经被访问过
				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<=vNum;i++){
			for(int j=1;j<=vNum;j++){
				graph[i][j] = 0;
			}
		}
		//输入边的情况
		System.out.println("请输入边的头和尾:");
		for(int k=1;k<=eNum;k++){
			int i = sc.nextInt();
			int j = sc.nextInt();
			graph[i][j] = 1;
		}
		//初始化color数组为0，表示一开始所有顶点都未被访问过
		for(int i=1;i<=vNum;i++){
			color[i] = 0;
		}
	}
	
	public static void main(String[] args) {
		test2 t = new test2();
		t.create();
		//保证每个节点都遍历到，排除有的结点没有边的情况
		for(int i=1;i<=vNum;i++){
			//该结点后边的结点都被访问过了，跳过它
			if(color[i] == -1){
				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<Integer> queue = new LinkedList<>();
	
	//拓扑排序
	void topoSort(){
		//入度为0的结点的个数，也就是入队个数
		int number = 0;
		//暂时存放拓扑序列
		Queue<Integer> temp = new LinkedList<Integer>();
		//遍历图中所有结点，找入度为0的结点删除（放进队列）
		for(int i=1;i<=vNum;i++){
			if(count[i] == 0){
				queue.offer(i);
			}
		}
		//删除这些被删除结点的出边（即对应结点入度减一）
		while(!queue.isEmpty()){
			int i = queue.peek();
			temp.offer(queue.poll());
			number++;
			for(int j=1;j<=vNum;j++){
				if(graph[i][j] == 1){
					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<=vNum;i++){
			for(int j=1;j<=vNum;j++){
				graph[i][j] = 0;
			}
		}
		//输入边的情况
		System.out.println("请输入边的头和尾:");
		for(int k=1;k<=eNum;k++){
			int i = sc.nextInt();
			int j = sc.nextInt();
			graph[i][j] = 1;
		}
		//计算每个结点的入度
		Arrays.fill(count, 0);//先初始化为0
		for(int i=1;i<=vNum;i++){
			for(int j=1;j<=vNum;j++){
				if(graph[i][j] == 1){
					count[j] = count[j] + 1;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		test1 t = new test1();
		t.create();
		t.topoSort();
	}
}