clone graph - undirected graph

• BFS
• Queue
• notice: dont add repeatedly
• 过一遍所有节点，建新节点放到 HashMap 中；
• 再过一遍所有节点，这次更新每个对应节点的 neighbors.

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {

        if (node == null) {
            return null;
        }

        // write your code here
        Queue<UndirectedGraphNode> nodes = new LinkedList<>();
        // a map of original to its clone
        Map<UndirectedGraphNode, UndirectedGraphNode> cloneMap = new HashMap<>();

        nodes.add(node);
        cloneMap.put(node, new UndirectedGraphNode(node.label));

        // BFS
        while (!nodes.isEmpty()) {
            UndirectedGraphNode head = nodes.poll();
            for (UndirectedGraphNode neighbor : head.neighbors) {
                if (!cloneMap.containsKey(neighbor)) {
                    cloneMap.put(neighbor, new UndirectedGraphNode(neighbor.label));
                    nodes.add(neighbor);
                }
            }
        }

        // add neighbors
        for (UndirectedGraphNode n : cloneMap.keySet()) {
            for (UndirectedGraphNode neighbor : n.neighbors) {
                //注意是cloneMap.get(neigbor) 而不是 直接neighbor
                cloneMap.get(n).neighbors.add(cloneMap.get(neighbor));
            }
        }

        return cloneMap.get(node);
    }

topological sort - directed graph

• Assumption: DAG
• BFS

    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        // write your code here
        ArrayList<DirectedGraphNode> result = new ArrayList<>();
        // frequency of node
        Map<DirectedGraphNode, Integer> frequency = new HashMap<>();

        for (DirectedGraphNode node : graph) {
            for (DirectedGraphNode neighbor : node.neighbors) {
                if (frequency.containsKey(neighbor)) {
                    frequency.put(neighbor, frequency.get(neighbor) + 1);
                } else {
                    frequency.put(neighbor, 1);
                }
            }
        }

        // add start point to result
        Queue<DirectedGraphNode> queue = new LinkedList<>();
        for (DirectedGraphNode node : graph) {
            if (!frequency.containsKey(node)) {
                result.add(node);
                queue.offer(node);
            }
        }

        while (!queue.isEmpty()) {
            DirectedGraphNode head = queue.poll();
            for (DirectedGraphNode neighbor : head.neighbors) {
                frequency.put(neighbor, frequency.get(neighbor) - 1);
                if (frequency.get(neighbor) == 0) {
                    result.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }

        return result;
    }

• DFS
• addFirst(node)
• by default, no cycle, so visited.contains(neighbor) only means visited, which <=> visited[neighbor] =2, cf visiting

    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        // write your code here
        LinkedList<DirectedGraphNode> rst = new LinkedList<>();
        Set<DirectedGraphNode> visited = new HashSet<>();

        for (DirectedGraphNode node : graph) {
            if (!visited.contains(node)) {
                dfs(rst, visited, node);
            }
        }

        return new ArrayList<>(rst);
    }

    private void dfs(LinkedList<DirectedGraphNode> rst, Set<DirectedGraphNode> visited, DirectedGraphNode node) {

        visited.add(node);
        for (DirectedGraphNode neighbor : node.neighbors) {
            if (!visited.contains(neighbor)) {
                dfs(rst, visited, neighbor);
            }
        }
        rst.addFirst(node);
    }

course schedule

• 这题的本质就是，给你一个代表 graph 的 adjacency array，判断 graph 是否有环。其实和 Graph Valid Tree 非常像。
• dfs here is better than topological sort, b/c no need to go to each node, since once cycle, return.

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        int[] visited = new int[numCourses];
        List<List<Integer>> graph = createGraph(numCourses, prerequisites);

        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0 && hasCycle(graph, visited, i)) return false;   
        }

        return true;        
    }

    private boolean hasCycle(List<List<Integer>> graph, int[] visited, int curr) {
        visited[curr] = 1;

        for (int neighbor : graph.get(curr)) {
            if (visited[neighbor] == 2) continue;
            if (visited[neighbor] == 1) return true;
            if (hasCycle(graph, visited, neighbor)) return true;
        }
        visited[curr] = 2;

        return false;        
    }

    private List<List<Integer>> createGraph(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] course : prerequisites) {
            graph.get(course[1]).add(course[0]);
        }
        return graph;
    }
}

• topological sort: num of indegree nodes == num of course, return true

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[][] matrix = new int[numCourses][numCourses]; // i -> j
    int[] indegree = new int[numCourses];

    for (int i=0; i<prerequisites.length; i++) {
        int ready = prerequisites[i][0];
        int pre = prerequisites[i][1];
        if (matrix[pre][ready] == 0)
            indegree[ready]++; //duplicate case
        matrix[pre][ready] = 1;
    }

    int count = 0;
    Queue<Integer> queue = new LinkedList();
    for (int i=0; i<indegree.length; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int i=0; i<numCourses; i++) {
            if (matrix[course][i] != 0) {
                if (--indegree[i] == 0)
                    queue.offer(i);
            }
        }
    }
    return count == numCourses;
}

course schedule ii

• topological sort

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {

        int[] freq = new int[numCourses];
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] course : prerequisites) {
            graph.get(course[1]).add(course[0]);
            freq[course[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
            if(freq[i] == 0) queue.offer(i);
        }

        int count = 0;
        int index = 0;
        int[] rst = new int[numCourses];
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            count++;
            rst[index++] = curr;
            for (int neighbor : graph.get(curr)) {
                freq[neighbor]--;
                if (freq[neighbor] == 0) queue.add(neighbor);                
            }
        }

        return count == numCourses ? rst : new int[0];

    }
}

graph valid tree (detect cycle)

• dfs
• visit[] =1 means visiting, =2 means visited, =0 means not yet visited
• undirected , need to keep prev; directed, no need for prev

• 无向图的 DFS 要注意避免 “原路返回” 的情况，仅仅依靠设 state = 1 是不行的，所以 dfs 里最好有个参数，代表 “前一个节点”，这样在下一步的搜索中可以直接跳过，又避免了误判有环。

public boolean validTree(int n, int[][] edges) {
        // write your code here
        int[] visited = new int[n];
        List<List<Integer>> graph = createGraph(n, edges);

        if (hasCycle(-1, 0, graph, visited)) return false;
        // exist disjoint component
        for (int v : visited) {
            if (v == 0) return false;
        }

        return true;
    }

    private boolean hasCycle(int prev, int curr, List<List<Integer>> graph, int[] visited) {

        visited[curr] = 1;
        for (int neighbor : graph.get(curr)) {
            if (neighbor == prev) continue;
            if (visited[neighbor] == 1) return true;
            if (visited[neighbor] == 2) continue;
            if (hasCycle(curr, neighbor, graph, visited)) return true;
        }

        visited[curr] = 2;
        return false;
    }

    private List<List<Integer>> createGraph(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        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]);
        }

        return graph;
    }

• BFS

public boolean validTree(int n, int[][] edges) {
        int[] visited = new int[n];
        List<List<Integer>> graph = createGraph(n, edges);

        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visited[0] = 1;

        if (hasCycleBFS(queue, visited, graph)) return false;

        // exist disjoint component
        for (int v : visited) {
            if (v == 0) return false;
        }

        return true;
    }

    private boolean hasCycleBFS(Queue<Integer> queue, int[] visited, List<List<Integer>> graph) {
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            visited[curr] = 1;
            for (int v : graph.get(curr)) {
                if (visited[v] == 1 || queue.contains(v)) return true;
                if (visited[v] == 2) continue;
                queue.add(v);
            }
            visited[curr] = 2;
        }
        return false;
    }

• Union Find

public class Solution {

    public boolean validTree(int n, int[][] edges) {
        // write your code here
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            if (uf.find(x) == uf.find(y)) return false;
            uf.union(x, y);
        }

        return uf.count == 1;
    }

    class UnionFind {
        int[] parent;
        int[] rank;
        int count;

        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            this.count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        int find(int x) {
            if (x == father[x]) { // NOTICE: **if** not **while**
                return x;
            }
            return father[x] = find(father[x]);    // find with path compression
        }

        void union(int x, int y) {
            int X = find(x);
            int Y = find(y);
            if (rank[X] > rank[Y]) { parent[Y] = X; }  // tree Y is lower
            else if (rank[X] < rank[Y]) { parent[X] = Y; }  // tree X is lower
            else {  // same height
                parent[Y] = X;
                rank[X]++;
            }
            count--;
        }

        int getCount() {return this.count;}
    }
}

reconstruct itinerary

class Solution {
    public List<String> findItinerary(String[][] tickets) {

        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        for (String[] ticket : tickets) {
            String s = ticket[0];
            String t = ticket[1];            
            if (!graph.containsKey(s)) {
                graph.put(s, new PriorityQueue<>());
            }
            graph.get(s).add(t);
        }

        LinkedList<String> rst = new LinkedList<>();
        dfs(graph, rst, "JFK");

        return rst;
    }

    private void dfs(Map<String, PriorityQueue<String>> graph, LinkedList<String> rst, String curr) {
        while (graph.containsKey(curr) && !graph.get(curr).isEmpty()) {
            dfs(graph, rst, graph.get(curr).poll());
        }
        rst.offerFirst(curr);
    }
}