1/20 Graph

graph representation

adjacency list (DFS / BFS) -> List<List<Integer>> list
adjacency matrix

BFS or DFS traversal in graph: need to keep a visited matrix or array if we cannot modify the original matrix or array.

cycle detection

cycle detection in undirected graph (graph valid tree) undirected graph..
- -> union find(check the root of two vertices of one edge) //
- -> DFS (acyclic(parent) & all connected) // check two things, no cycle, ...
- -> BFS (3 colors, 1 being visited, 2 completely visited, 0 not visited yet) // explain why we need 3 colors
cycle detection in directed graph(determine DAG) (course schedule 1) directed graph
- -> DFS(3 colors, 1 being visited, 2 completely visited, 0 not visited yet)
- -> BFS(the key is to check set.size() == numCourses) preferred method...
  - in DG, we need to not only construct adjacency list, but also create the intake array representing how many nodes point to the current node?

Topological Sort

is possible only when it is a DAG...
DFS
BFS (preferred method...)
- after creating adjacency list and intake array, it's worth noticing that we need to decrement the intake element, and add those element as long as value drop down to 0;

Graph valid tree

用DFS做，check 2 things：

whether there is loop -> 如果我的parent 点和我的下一个点是一个的话，不是环，是一条边
whether the number of connected components is 1 -> 可以用hashset来去重复，最后统计他的size == n；

class Solution {
    public boolean validTree(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        // build the graph
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        Set<Integer> visited = new HashSet<>();
        visited.add(0);

        // check cycle
        if (hasCycle(-1, 0, graph, visited)) {     // 1. check there is no cycle.
            return false;
        }

        return visited.size() == n;    // 2. check all the components are connected.
    }

    private boolean hasCycle(int parent, int cur, List<List<Integer>> graph, Set<Integer> visited) {

        for (int next : graph.get(cur)) {
            if (parent == next) continue;   // skip this neighbor since this is a undirected graph.
            if (visited.contains(next))  return true;   // has a cycle if we have visited this cell.

            visited.add(next);
            if (hasCycle(cur, next, graph, visited)) {
                return true;
            }
        }
        return false;
    }
}

bfs version:

use 3 colors to represent the status of the node, 一开始是0，然后开始访问就设为1，每一层把自己的neighbor全部添加结束后，设置为2，表示访问结束。

why we need 3 colors instead of 2 to solve this problem?

because we cannot handle the following situation.
- in the situation below, after visiting 2, we will label 1, 3, 4 as visiting node, so next time, if we found two visiting nodes are neighbors each other, we will tell that there is a cycle inside the graph. However, if we have two color, how to label their parent node say 2.

//     1  -  2(root)
//           |  \
//           3 -  4
//           |
//           5

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        int[] visited = new int[n];
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i=0; i<n; ++i) { 
            adjList.add(new ArrayList<Integer>()); 
        }
        for (int[] edge: edges) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]);
        }
        Deque<Integer> q = new LinkedList<>();
        q.offer(0); 
        visited[0] = 1;  // vertex 0 is in the queue, being visited
        while (!q.isEmpty()) {
            Integer cur = q.poll();
            for (int succ: adjList.get(cur)) {
                if (visited[succ] == 1) { 
                    return false;      // loop detected
                }  
                if (visited[succ] == 0) { 
                    q.offer(succ); 
                    visited[succ] = 1; 
                }
            }
            visited[cur] = 2;  // visit completed
        }
        for (int v: visited) { 
            if (v == 0) { 
                return false; // # of connected components is not 1
            } 
        }  
        return true;
    }
}

还可以用union find 做，区别是，在添加edge的时候判断是否有环，如果father[pair[0]] == father[pair[1]] 就是有环。

class Solution {
    public boolean validTree(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        uf.setCount(n);
        for (int[] pair : edges) {
            int x = uf.find(pair[0]);
            int y = uf.find(pair[1]);

            if (x == y) return false;

            uf.connect(x, y);
        }
        return uf.query() == 1;
    }

    private class UnionFind{

        private int[] father;
        private int count;

        public UnionFind(int n) {
            father = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
        }

        private void connect(int a, int b) {
            // to do
            int root_a = find(a);
            int root_b = find(b);

            if (root_a != root_b) {
                father[root_a] = root_b;
                count--;
            }
        }

        private int find(int a) {
            // to do
            if (a == father[a]) {
                return a;
            }
            return father[a] = find(father[a]);
        }

        private int query() {
            return count;
        }

        private void setCount(int n) {
            count = n;
        }
    }
}

Course Schedule

有向图的检测valid，首选BFS，一定要注意neighbor节点是如何加到queue中去的。最后set.size() == numCourses 既检查了是否便利了所有的点，又检查了是否有环，因为如果有环那么就不会存在arr[i] == 0，则这个节点就不会被加入到queue中去。

the basic idea is that put NODE with 0 indgree into the queue, then make indegree of NODE's successor dereasing 1. Keep the above steps with BFS. Finally, if each node' indgree equals 0, then it is validated DAG (Directed Acyclic Graph), which means the course schedule can be finished.

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] arr = new int[numCourses];

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] pair : prerequisites) {
            graph.get(pair[1]).add(pair[0]);
            arr[pair[0]]++;
        }

        Deque<Integer> queue = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < numCourses; i++) {
            if (arr[i] == 0) {
                queue.offer(i);
                set.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int course = queue.poll();
            for (int i : graph.get(course)) {
                arr[i]--;
                if (arr[i] == 0) {
                    queue.offer(i);
                    set.add(i);
                }
            }
        }
        return set.size() == numCourses;
    }
}

DFS version:

use Map<Integer, List<Integer>> map 去表示一个图这是一个一般表示的方法
设计dfs 返回boolean，在每一层DFS中，只要发现false，立马返回false
用1表示正在访问，这个DFS遍历完，改为2，

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            map.put(i, new ArrayList<>());
        }

        for (int[] pair : prerequisites) {
            map.get(pair[1]).add(pair[0]);
        }

        int[] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(map, i, visited)) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(Map<Integer, List<Integer>> map, int course, int[] visited) {
        // base case
        if (visited[course] == 1) return false;
        if (visited[course] == 2) return true;

        // recursive case
        visited[course] = 1;

        for (int next : map.get(course)) {
            if (!dfs(map, next, visited)) return false;
        }

        visited[course] = 2;
        return true;
    }

}

Course Schedule 2

和上一题思路一样，唯一的不同是加一个array 输出course的结果

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int[] arr = new int[numCourses];
        for (int i= 0; i < numCourses; i++) {
            map.put(i, new ArrayList<>());
        }

        for (int[] pair : prerequisites) {
            map.get(pair[1]).add(pair[0]);
            arr[pair[0]]++;
        }

        Deque<Integer> queue = new LinkedList<>();
        Set<Integer> set = new HashSet<>();

        int[] order = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (arr[i] == 0) {
                queue.offer(i);
                set.add(i);
            }
        }
        int i = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            order[i++] = course;

            for (int next : map.get(course)) {
                if (set.contains(next)) {
                    continue;
                }
                arr[next]--;
                if (arr[next] == 0) {
                    queue.offer(next);
                    set.add(next);
                }
            }
        }
        if (i == numCourses) return order;
        return new int[0];
    }
}

clone graph

we can solve this problem using the way we did in copy linked list with random pointer.

getNodes()
create new nodes and store them in the map
deal with neighbors

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) return null;

    // 1. get nodes 
    List<UndirectedGraphNode> list = getNodes(node);

    // 2. create new nodes and store in map
    Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
    for (UndirectedGraphNode cur : list) { 
        UndirectedGraphNode newNode = new UndirectedGraphNode(cur.label);
        map.put(cur, newNode);
    }

    // 3. copy their neighbor
    for (UndirectedGraphNode cur : list) {
        UndirectedGraphNode newNode = map.get(cur);
        for (UndirectedGraphNode neighbor : cur.neighbors) {
            newNode.neighbors.add(map.get(neighbor));
        }
    }
    return map.get(node);
}

private List<UndirectedGraphNode> getNodes(UndirectedGraphNode node) {
    Deque<UndirectedGraphNode> queue = new LinkedList<>();
    Set<UndirectedGraphNode> set = new HashSet<>();

    queue.offer(node);
    set.add(node);

    while(!queue.isEmpty()) {
        UndirectedGraphNode temp = queue.poll();
        for (UndirectedGraphNode neighbor : temp.neighbors) {
            if (!set.contains(neighbor)) {
                queue.offer(neighbor);
                set.add(neighbor);
            }
        }
    }
    return new ArrayList<>(set);
}

another idea is that we can use dfs to solve the problem. note that 1. use the map to store the processed nodes, 2. recursively invoke the clone method when add the neighbors

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) return null;

    Map<Integer, UndirectedGraphNode> map = new HashMap<>();
    return clone(node, map);
}

private UndirectedGraphNode clone(UndirectedGraphNode node, 
                                        Map<Integer, UndirectedGraphNode> map) {
    // base case
    if (node == null) return null;
    if (map.containsKey(node.label)) return map.get(node.label);

    // recursive case
    UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
    map.put(node.label, newNode);

    for (UndirectedGraphNode neighbor : node.neighbors) {
        newNode.neighbors.add(clone(neighbor, map));
    }
    return newNode;
}

Alien Dictionary

this problem is topological sorting. And the key idea is that you should get understanding of relationship among those words.

in other words, when comparing two adjencent words, we should skip their common prefix, and establish one edge between different character and modify their inbounds.

class Solution {

    public String alienOrder(String[] words) {
        // build graph
        // create graph and indegree
        List<Set<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < 26; ++i) {
            adj.add(new HashSet<>());
        }
        Integer[] indegree = new Integer[26];

        for (int i = 0; i < words.length; ++i) {
            // build the indegrees for each character
            String curString = words[i];
            for (int j = 0; j < curString.length(); ++j) {
                int curChar = curString.charAt(j) - 'a';
                indegree[curChar] = 0;
            }
        }
        // build graph
        for (int i = 1; i < words.length; ++i) {
            String w1 = words[i-1];
            String w2 = words[i];

            int k = 0;
            while (k < w1.length() && k < w2.length()) {
                if (w1.charAt(k) != w2.charAt(k)) {
                    adj.get(w1.charAt(k) - 'a').add(w2.charAt(k) - 'a');
                    break;
                }
                k++;
            }
        }
        // build indegrees
        for (int i = 0; i < 26; ++i) {
            for (Integer item : adj.get(i)) {
                indegree[item]++;
            }
        }

        // topological sort
        StringBuilder sb = new StringBuilder();
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < indegree.length; ++i) {
            if (indegree[i] != null && indegree[i] == 0) 
                queue.add(i);
        }

        while (!queue.isEmpty()) {
            int cur = (int)queue.poll();
            sb.append((char)(cur + 'a'));
            for (Integer i : adj.get(cur)) {
                indegree[i] = indegree[i] - 1;
                if (indegree[i] == 0) {
                    queue.offer(i);
                }
            }
        }

        for (int i = 0; i < indegree.length; ++i) {
            if (indegree[i] != null && indegree[i] > 0) return "";
        }

        return sb.toString();
    }
}

graph