207. Course Schedule

207,課程表。題目鏈接

判斷給定的圖形是不是有環(huán)圖，有兩種解決辦法是：深度優(yōu)先搜索，和廣度優(yōu)先搜索

1.深度優(yōu)先搜索

思路：使用一個(gè)onStack[]來(lái)判定當(dāng)前訪問(wèn)到的節(jié)點(diǎn)是不是在當(dāng)前的路徑上,如果是,則證明有環(huán)

/**
 * 深度優(yōu)先搜索判斷環(huán)
 */
class Topological {
    private final int N;
    private List<Integer>[] bags;
    private boolean[] marked;
    private boolean hasCycle = false;
    private boolean[] onStack;

    public Topological(int N, int[][] prerequisites) {
        this.N = N;
        bags = (List<Integer>[]) new List[N];
        marked = new boolean[N];
        onStack = new boolean[N];
        for (int i = 0; i < N; i++) {
            bags[i] = new ArrayList<>();
        }
        for (int[] pre : prerequisites) {
            bags[pre[0]].add(pre[1]);
        }
        for (int v = 0; v < N; v++) {
            if (!marked[v])
                dfs(v);
        }
    }

    private void dfs(int v) {
        onStack[v] = true;
        marked[v] = true;
        for (int w : bags[v]) {
            if (hasCycle) return;
            if (!marked[w])
                dfs(w);
            else if (onStack[v] == onStack[w]) hasCycle = true;
        }
        onStack[v] = false;
    }

    public boolean isHasCycle() {
        return hasCycle;
    }
}

2.廣度優(yōu)先搜索:

有沒(méi)有想起來(lái)教材數(shù)據(jù)結(jié)構(gòu),判定拓?fù)涞姆椒?首先刪掉入度為0的節(jié)點(diǎn),然后刪掉這個(gè)節(jié)點(diǎn)的鏈接.在判斷其他節(jié)點(diǎn)是否入度為0.最后如果能夠全部刪除節(jié)點(diǎn),證明無(wú)環(huán)

/**
 * 廣度優(yōu)先搜索判斷環(huán)
 */
class Topological1 {
    private int N;
    private int[] inDegree; //入度表
    private List<Integer>[] adj;

    public Topological1(int n, int[][] prerequisites) {
        N = n;
        inDegree = new int[N];
        adj = (List<Integer>[]) new List[n];
        for (int i = 0; i < N; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] pre : prerequisites) {
            inDegree[pre[1]]++;
            adj[pre[0]].add(pre[1]);
        }
        bfs();
    }

    private void bfs() {
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            if (inDegree[i] == 0) queue.add(i);
        }
        while (!queue.isEmpty()) {
            int v = queue.poll();
            N--;
            for (int w : adj[v]) {
              //刪除節(jié)點(diǎn)的時(shí)候減去其他節(jié)點(diǎn)的入度
                if (--inDegree[w] == 0) queue.add(w);
            }
        }
    }

    public boolean hasCycle() {
        return N == 0;
    }
}