6. Graph

这里收录的是真正的关于Graph data structure或者Graph Theory的题目.隐式图是一种算法/思想，不是真正关于Graph的，所以就收录在其它章节了BFS/DFS

Graph Valid Tree

• 这道题很好的考察了对Tree和Graph的区别的理解

• 还是BFS的思路更intuitive, 面试更好解释

Tree vs. Graph

• 树和图的区别在于是否有环

• tree是parent-child relationship

• Graph 是 neighbor-neighbor relation

• 如何判断是否是Graph: 图中存在环，同一个节点可能重复进入队列

class Solution {
    /*
    1.valid tree, N nodes can only have N - 1 edges
    2.BFS to traversal all neighbors from a random node, check whether all nodes can be visited
    3.need to build graph, Map<Integer, Set<Integer>> graph, key is node, value is set of neighbors
    */
    public boolean validTree(int n, int[][] edges) {
        if (edges == null || edges.length != n - 1) return false;
        if (n == 1) return true;
        Map<Integer, Set<Integer>> graph = buildGraph(edges);//key is node, value is set of neighbors
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(edges[0][0]);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (!visited.add(node)) continue;
            for (int neighbor : graph.get(node)) {
                queue.offer(neighbor);
            }
        }
        return visited.size() == n;
    }
    private Map<Integer, Set<Integer>> buildGraph(int[][] edges) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            Set<Integer> neighbors = graph.getOrDefault(edge[0], new HashSet<>());
            neighbors.add(edge[1]);
            graph.put(edge[0], neighbors);
            neighbors = graph.getOrDefault(edge[1], new HashSet<>());
            neighbors.add(edge[0]);
            graph.put(edge[1], neighbors);
        }
        return graph;
    }
}

Course Schedule

• 给定一堆课程和 prerequisisites, 判断是否能完成所有课程

• 判断DAG是否有环的经典题型

• topo sort模板题

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> courseToNeighbors = new HashMap<>();
        Map<Integer, Integer> indegrees = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            indegrees.put(i, 0);
            courseToNeighbors.put(i, new ArrayList<>());
        }
        for (int[] pre : prerequisites) {
            // build graph with neighbors
            courseToNeighbors.get(pre[1]).add(pre[0]);
            //get indegrees of each node
            indegrees.put(pre[0], indegrees.get(pre[0]) + 1);
        }
        Queue<Integer> queue = new LinkedList<>();
        int start = 0;
        Set<Integer> visited = new HashSet<>();
        while (start < numCourses) {
            if (indegrees.get(start) == 0) {
                queue.offer(start);
                visited.add(start);
            }
            start++;
        }
        
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            List<Integer> neighbors = courseToNeighbors.get(cur);
            for (int neighbor : neighbors) {
                indegrees.put(neighbor, indegrees.get(neighbor) - 1);
                if (indegrees.get(neighbor) == 0 && !visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        return visited.size() == numCourses;
    }
}

• 这题除了用Set来记录visited node之外，还可以用list来记录visited node

• 这样如果需要返回任意一条路径的话就很方便

public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, Integer> courseToIndegree = new HashMap<>();
        Map<Integer, Set<Integer>> courseToNeighbors = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            courseToIndegree.put(i, 0);
            courseToNeighbors.put(i, new HashSet<Integer>());
        }
        
        for (int[] prerequisite : prerequisites) {
            //get indegrees of each node
            courseToIndegree.put(prerequisite[0], courseToIndegree.get(prerequisite[0]) + 1);
            // build graph with neighbors
            courseToNeighbors.get(prerequisite[1]).add(prerequisite[0]);
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (Integer course: courseToIndegree.keySet()) {
            if (courseToIndegree.get(course) == 0) {
                queue.offer(course);
            }
        }
        
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            Integer cur = queue.poll();
            order.add(cur);
            for (Integer neighbor : courseToNeighbors.get(cur)) {
                courseToIndegree.put(neighbor, courseToIndegree.get(neighbor) - 1);
                if (courseToIndegree.get(neighbor) == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        return order.size() == numCourses;
    }

Course Schedule II

• course schedule 的follow up, 要求返回任意一条路径的结果

• 用一个list来记录visited node

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, Integer> courseToIndegree = new HashMap<>();
        Map<Integer, Set<Integer>> courseToNeighbors = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            courseToIndegree.put(i, 0);
            courseToNeighbors.put(i, new HashSet<Integer>());
        }
        
        for (int[] prerequisite : prerequisites) {
            //get indegrees of each node
            courseToIndegree.put(prerequisite[0], courseToIndegree.get(prerequisite[0]) + 1);
            // build graph with neighbors
            courseToNeighbors.get(prerequisite[1]).add(prerequisite[0]);
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (Integer course: courseToIndegree.keySet()) {
            if (courseToIndegree.get(course) == 0) {
                queue.offer(course);
            }
        }
        
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            Integer cur = queue.poll();
            order.add(cur);
            for (Integer neighbor : courseToNeighbors.get(cur)) {
                courseToIndegree.put(neighbor, courseToIndegree.get(neighbor) - 1);
                if (courseToIndegree.get(neighbor) == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        int[] arr = {};
        if (order.size() == numCourses) {
            arr = convert(order);
        }
        return arr;
    }
    
    private int[] convert(List<Integer> list) {
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }
}

Is Graph Bipartite?

graph coloring

BFS

public boolean isBipartite(int[][] graph) {
        int[] groups = new int[graph.length];//groups[i] can be 0,1,2, 0 means not visited
        for (int i = 0; i < graph.length; i++) {
            //BFS to calculate which group node i should be
            if (groups[i] != 0) continue;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            groups[i] = 1;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                int[] neighbors = graph[cur];
                for (int neighbor : neighbors) {
                    if (groups[neighbor] == 0) {
                        queue.offer(neighbor);
                        groups[neighbor] = groups[cur] == 1 ? 2 : 1;
                    } else if (groups[neighbor] == groups[cur]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

Best Meeting point

Mahattan distance