用深度周遊dfs判斷一個有向圖是否有環

這裡有一個無向圖的深度周遊算法，無向圖 深度優先周遊 c語言實作， 有向圖的DFS周遊跟這個算法一樣。

利用DFS判斷一個有向圖是否有環的思路是：對一個節點v進行深度周遊，判斷是否能從v到達自己這個節點，即是否存在從v到v的環路。

在圖的深度周遊中，我們将圖中每個節點設定為三個狀态：-1,0,1，分别表示還沒發現的節點；已經發現但是還沒處理完的節點；已經處理完的節點。對應上述思路，假設我們正在處理v，那麼v的狀态為0，其餘正在處理節點的狀态也為0，如果從狀态為0的節點周遊到狀态為0的節點就存在環。

下面是leetcode中的一個題：Course Schedule，可以用dfs來解決，代碼如下（下面代碼效率很低，僅用來說明用dfs發現環的思路），

import java.util.ArrayList;
import java.util.List;

public class Solution {

    boolean flag = true;

    public void dfs(List<List<Integer>> adjList,int v,int[] color){

        color[v] = ;   //表示正在處理v節點
        List<Integer> adjs = adjList.get(v); 

        for(int i=;i<adjs.size();i++){
            if(color[adjs.get(i)]==-){
                dfs(adjList,adjs.get(i),color);
            }else if(color[adjs.get(i)]==){//回到了狀态為0的節點，有環
                flag = false;
            }
        }
        color[v] = ;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = new ArrayList<List<Integer>>();

        //根據course個數初始化一個空的鄰接表
        for(int i=;i<numCourses;i++){
            adjList.add(new ArrayList<Integer>());
        }
        //初始化color數組
        int[] color = new int[numCourses];
        for(int i=;i<numCourses;i++){
            color[i] = -;
        }

        //adjList表示鄰接表，頭結點是後面的課程，後面的list表示先修課
        //由先修課指向 後修課
        for(int i=;i<prerequisites.length;i++){
            int[] cp = prerequisites[i];
            adjList.get(cp[]).add(cp[]);
        }

        //下面對鄰接表進行深度周遊，看看是否有環，從每一個節點都周遊一次
        for(int i=;i<numCourses;i++){
            dfs(adjList, i, color);
            if(!flag){
                return false;
            }
            for(int j=;j<numCourses;j++){
                color[j] = -;
            }
        }
        return flag;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        //4, [[0,1],[3,1],[1,3],[3,2]]
        int[][] nums = {{,},{,},{,}};

        System.out.println(s.canFinish(, nums));
    }
}