如图所示，有一个存在环路的有向图，判断是否存在环路有两种方式：

一、使用深度优先搜索（DFS）判断

1、简介

判断逻辑如下：

  • 创建一个visited数组来记录每个节点是否被遍历过。

  • 对于每个未被遍历过的节点，进行深度优先搜索。

  • 在搜索过程中，记录每个节点的状态，如果在搜索中遇到一个已经访问过的节点，且状态为正在访问（正在遍历它的子节点），则说明存在环。

  • 如果搜索完所有节点都没有发现环路，则说明不存在环。

2、样例

public class DFSTest {

	//记录节点是否被访问
	private boolean[] visited;
	//记录正在访问的节点
	private boolean[] onStack;
	//邻接表，记录每个节点相邻的节点
	private List<Integer>[] adj;
	
	/**
	 * 判断是否存在环
	 * @param num 节点数
	 * @param edges 连线
	 * @return
	 */
	public boolean hasCycle(int num, int[][] edges) {
		visited = new boolean[num];
		onStack = new boolean[num];
		adj = new ArrayList[num];
		//初始化邻接表
		for(int i = 0; i < num; i++){
			//每个节点的相邻节点（节点0对应邻接表中第0个元素，依次类推）
			adj[i] = new ArrayList<>();
		}
		//根据线的走向计算节点的相邻节点
		for(int[] edge : edges){
			int from = edge[0];
			int to = edge[1];
			adj[from].add(to);
		}
		//从第一个节点开始搜索
		for(int i = 0; i < num; i++){
			if(visited[i]){
				continue;
			}
			if(dfs(i)){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 深度优先搜索节点
	 * @param vertex
	 */
	private boolean dfs(int vertex){
		visited[vertex] = true;
		onStack[vertex] = true;
		for(int neighbor : adj[vertex]){
			if(!visited[neighbor]){
				//如果相邻节点没有被访问过，则搜索相邻节点
				if(dfs(neighbor)){
					return true;
				}
			}else if(onStack[neighbor]){
				//搜索到已访问过的节点，存在环路
				return true;
			}
		}
		//搜索完当前节点后修改状态
		onStack[vertex] = false;
		return false;
	}
	
}

测试代码：

public static void main(String[] args) {
	//节点为：0,1,2,3,4,5
	//连线的数组，例如：数组元素{0,4}表示0到4的连线
	int[][] edges = new int[][]{
		{0, 4}, {4, 1}, {1, 3}, {3, 2}, {2, 5}, {2, 4}
	};
	System.out.println(new DFSTest().hasCycle(6, edges));//true
}

二、使用拓扑排序判断

1、简介

拓扑排序概念可参考 百度百科。

判断逻辑如下：

  • 对于有向图中的每个节点，计算它的入度。

  • 将所有入度为0的节点放入一个队列中。

  • 从队列中取出一个节点，将它相邻节点的入度减1；如果减1后邻接节点的入度为0，则将邻接节点添加到队列中。重复此步骤，直到队列为空。

  • 如果所有节点都被处理（排序），则不存在环。

2、样例

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TopologyTest {

	private List<Integer>[] adjacencyList;

	/**
	 * 判断是否存在环
	 * @param num 节点数
	 * @param edges 连线
	 * @return
	 */
	public boolean hasCycle(int num, int[][] edges){
		//记录每个节点的入度
		int[] indegree = new int[num];
		//初始化邻接表
		this.adjacencyList = new ArrayList[num];
		for(int i = 0; i < num; i++){
			//每个节点的相邻节点（节点0对应邻接表中第0个元素，依次类推）
			adjacencyList[i] = new ArrayList<>();
		}
		//根据线的走向计算节点的相邻节点
		for(int[] edge : edges){
			int from = edge[0];
			int to = edge[1];
			adjacencyList[from].add(to);
			indegree[to]++;
		}
		//使用队列存放所有入度为0的节点
		Queue<Integer> queue = new LinkedList<>();
		for(int i = 0; i < num; i++){
			if(indegree[i] == 0){
				queue.offer(i);
			}
		}
		int visited = 0;
		while(!queue.isEmpty()){
			int vertex = queue.poll();
			visited++;
			for(int neighbor : adjacencyList[vertex]){
				if(--indegree[neighbor] == 0){
					queue.add(neighbor);
				}
			}
		}
		return visited != num;
	}
	
}

测试代码：

public static void main(String[] args) {
	//节点为：0,1,2,3,4,5
	//连线的数组，例如：数组元素{0,4}表示0到4的连线
	int[][] edges = new int[][]{
		{0, 4}, {4, 1}, {1, 3}, {3, 2}, {2, 5}, {2, 4}
	};
	System.out.println(new TopologyTest().hasCycle(6, edges));//true
}