题目地址：

给定一个有向图，判断其是否有环。图有 $n$ 个顶点，每个顶点的标号为 $1\sim n$ 。

思路是DFS，先用邻接表建图，然后进行DFS。用一个数组标记每个顶点的访问状态，每次从一个顶点DFS的时候，标记为 $0$ 的顶点表示当前这次DFS经过的顶点，标记为 $- 1$ 的表示从未访问过的顶点，标记为 $1$ 的表示本次DFS全部结束后已经访问过的顶点（包括之前DFS访问过的顶点）。如果在某次从一个顶点出发的时候，发现某个邻接点标记为了 $0$ ，则说明有环；如果某个邻接点标记为 $- 1$ 则对其进行DFS；回溯之前要把遍历过的顶点都标记为 $1$ 。代码如下：

import java.util.*;public class Solution {       /**     * @param start: The start points set     * @param end:   The end points set     * @return: Return if the graph is cyclic     */    public boolean isCyclicGraph(int[] start, int[] end) {           // Write your code here        if (start == null || start.length == 0) {               return false;        }        // 算一下一共多少个顶点        int n = 0;        for (int i = 0; i < start.length; i++) {               n = Math.max(n, start[i]);            n = Math.max(n, end[i]);        }        // 用邻接表建图        Map
   
    > graph = buildGraph(start, end);        // 先把所有顶点都标记为未访问        int[] visited = new int[n + 1];        Arrays.fill(visited, -1);        for (int i = 1; i <= n; i++) {           	// 如果标号为i的顶点未访问，则对其进行DFS            if (visited[i] == -1 && dfs(graph, i, visited)) {                   return true;            }        }                return false;    }        // 从cur开始进行DFS，返回是否发现了环    private boolean dfs(Map
    
     > graph, int cur, int[] visited) {           visited[cur] = 0;        List
     
       nexts = graph.get(cur);        if (nexts != null) {               for (int next : graph.get(cur)) {                   if (visited[next] == 0) {                       return true;                }                if (visited[next] == -1 && dfs(graph, next, visited)) {                       return true;                }            }        }                visited[cur] = 1;        return false;    }        private Map
      
       > buildGraph(int[] start, int[] end) {           Map
       
        > graph = new HashMap<>();        for (int i = 0; i < start.length; i++) {               graph.putIfAbsent(start[i], new ArrayList<>());            graph.get(start[i]).add(end[i]);        }                return graph;    }}

时空复杂度 $O (V + E)$ 。

转载地址：http://bhds.baihongyu.com/

你可能感兴趣的文章