Directed Graph

DFS

Detect Cycle

• 最优解法是 CLRS 上用三种状态表示每个节点：

• • "0" 还未访问过;
  • "1" 代表正在访问；
  • "2" 代表已经访问过；
• DFS 开始时把当前节点设为 "1";
• 在从任意节点出发的时候，如果我们试图访问一个状态为 "1" 的节点，都说明图上有环。
• 当前节点的 DFS 结束时，设为 "2";
• 在找环上，DFS 比起 BFS 最大的优点是"对路径有记忆"，DFS 记得来时的路径和导致环的位置，BFS 却不行。

Topological Sort

• 类似剥洋葱，可以选择任意点开始向里 DFS ，记录path，后面做的其他 DFS path 都放在之前结果的前面。(CLRS有)

• 等价做法是，把每次 DFS 探索中的 path 按照由内向外的顺序添加(单序列反序), 后进行的 DFS 结果放在之前运行完的结果后面(全序列反序)，然后 reverse 就好了，可以改良 ArrayList 添加的时间复杂度。

• 更简单的做法是用 Java 内置的 LinkedList，支持双端操作。

BFS

Detect Cycle

首先，在 DAG 上找环，DFS 要比 BFS 强。

• 其次重点注意，有向图靠 3 个状态 BFS 是不能正确判断是否有环的，要靠 indegree，一个例子是 【0, 1】 和 【1,0】，环在发现之前已经被标注为 state 2 了。

• 扫一遍所有 edge，记录每个节点的 indegree.
• 在有向无环图中，一定会存在至少一个 indegree 为 0 的起点，将所有这样的点加入queue。
• 依次处理queue里的节点，把每次poll出来的节点的 children indegree -1. 减完之后如果 child 的 indegree = 0 了，就也放入队列。
• 如果图真的没有环，可以顺利访问完所有节点，如果还有剩的，说明图中有环，因为环上节点的 indegree 没法归 0.

Topological Sort

步骤同上，扫的时候按顺序 append 就好了。

类似于“剥洋葱”，从最外面一层出发，逐步向里。

Undirected Graph

无向图算法的整体思路和有向图基本一致，但是需要重点注意 正确处理 “原路返回” 的情况，免得死循环或者误报。

在无向图的2个状态基础上增加一个 “正在访问” 的新状态，加上注意 prev 就可以了。

DFS

Detect Cycle

• 用 int[] 表示每个点的状态，其中

• • 0 代表“未访问”；
  • 1 代表“访问中”；
  • 2 代表“已访问”；

• DFS call 里要传入 "prev节点" 参数，避免出现原路返回，或者回到前一个节点误判为有环。(和 directed graph DFS 唯一的不同之处)

• 其他情况下，如果我们试图访问一个状态为 “1” 的节点，都可以说明图中有环。

BFS

Detect Cycle

• 扫描所有 edges 记录图到底长啥样；

• 用 "0,1,2" states;

• 随便扔一个点进 queue，标记 "1"，然后 BFS，所有 child = "0" 的都加入队列

• 所有 child 都检查完之后，立刻把当前 node = 2，不然下一层 BFS 会回头去看自己然后误报。

• 如果遇到 child = "1" 的说明有环

Count Components

• pick unvisited node as a starting point and fully explore its graph component
• keep until all nodes have been visited

class Solution {
    public int countComponents(int n, int[][] edges) {
        //bfs + pick unvisited node
        //construct graph
        ArrayList[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        for (int[] edge: edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        int[] status = new int[n];
        int num = 0;
        int start = pickNode(status);
        while (start != -1) {
            //bfs 
            num++;
            Queue<Integer> queue = new LinkedList<Integer>();
            queue.add(start);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int curr = queue.poll();
                    status[curr] = 1;
                    ArrayList<Integer> neighbors = graph[curr];
                    for (int nei: neighbors) {
                        if (status[nei] != 1) {
                            queue.add(nei);
                            status[nei] = 1;
                        }
                    }
                }
            }
            start = pickNode(status);
        }
        return num;
    }

    private int pickNode(int[] status) {
        for (int i = 0; i < status.length; i++) {
            if (status[i] == 0) return i;
        }
        return -1;
    }
}

=================================

undirected graph:

    //DFS
    private boolean hasCycle(int pre, int vertice, List<List<Integer>> adjList, int[] status) {
        status[vertice] = 1;
        List<Integer> neighbors = adjList.get(vertice);
        for (int n: neighbors) {

            //skip the predecessor
            if (n == pre) continue;

            if (status[n] == 1) return true;
            if (hasCycle(vertice, n, adjList, status)) return true;
        }
        status[vertice] = 2;//finish visiting
        return false;
    }

    //BFS
    private boolean hasCycle(List<List<Integer>> adjList, int[] status) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(0);
        status[0] = 1;
        while (queue.size() != 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int vertice = queue.poll();
                for (int n: adjList.get(vertice)) {
                    if (status[n] == 1) return true;

                    //note: need to skip predecessor
                    if (status[n] == 2) continue;

                    status[n] = 1;
                    queue.add(n);
                }
                status[vertice] = 2;
            }
        }
        return false;
    }