图经典题目整理

Posted on |

本文整理了关于树和图的总结与经典面试题

存储方法

假设m为边的数量，n为图的点数

  • 直接存边
    • 查询某个边：O(m)
    • 遍历一个点的所有边: O(m)
    • 遍历整个图: O(nm)
    • 空间复杂度：O(m)
  • 领接矩阵
    • 查询某个边：O(1)
    • 遍历一个点的所有边: O(n)
    • 遍历整个图: O(n^2)
    • 空间复杂度：O(n^2)
    • 缺点是空间复杂度过大，不适用于稀疏图
  • 邻接表 (动态数组或者链表)
    • 查询某个边(u->v)：O(d(u)), 这里d(u)是u的出度
      • 如果u的出度边已经排序好，可以用二分做到O(log(d(u)))
    • 遍历一个点的所有边: O(d(u))
    • 遍历整个图: O(n+m), (BFS, DFS)
    • 空间复杂度：O(m)

DFS

  • 使用Depth First Search的遍历本质上是根树前序遍历的推广。
  • 初始点的选择决定了遍历的结果，如果初始点可以通向所有点，随后的遍历结果将是DFS spinning tree；如果初始点有无法到达的点，那么结果将是DFS forest。
  • 在使用邻接表的情况下，算法的复杂度是O(n+m),n是点数，m是边数，空间复杂度是O(n).

有无回路

BFS

  • Breadth First Search is a graph traversal algorithm which explores the neighbor nodes first, before moving to the next level neighbors

Their time complexity are both O(|V| + |E|), where V is the set of the nodes and E is the set of edges.

Code example, traverse the tree using DFS and BFS (both iterative and recursive).

  • DFS (recursive, java)
    1
    2


拓扑排序 Topological sort

A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

  • Implementations:

    • Kahn:

    • DFS TODO

  • Example problem: Leetcode 210
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    // Kahn implementation
    class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            Map<Integer, List<Integer>> edgeMap = new HashMap<>();
            Map<Integer, Integer> inEdgeMap = new HashMap<>();
            for(int i=0; i<prerequisites.length; i++) {
                int from = prerequisites[i][1], to = prerequisites[i][0];
                edgeMap.computeIfAbsent(from, l -> new ArrayList<>()).add(to);
                inEdgeMap.put(to, inEdgeMap.getOrDefault(to, 0) + 1);
            }
            List<Integer> res = new ArrayList<>();
            Queue<Integer> q = new LinkedList<>();
            for(int i=0; i<numCourses; i++) {
                if(inEdgeMap.get(i)==null) {
                    q.add(i);
                }
            }
            while(!q.isEmpty()) {
                int n = q.poll();
                res.add(n);
                for(int toNode: edgeMap.getOrDefault(n, new ArrayList<>())) {
                    inEdgeMap.put(toNode, inEdgeMap.get(toNode) - 1);
                    if(inEdgeMap.get(toNode) == 0) {
                        q.add(toNode);
                    }
                }
            }
            return res.size() == numCourses ?
                res.stream().mapToInt(i->i).toArray(): new int[]{};
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// DFS solution
class Solution {
    
    int[] res;
    int count;
    int[] visited;
    Map<Integer, List<Integer>> map;
    
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // DFS
        int[] indegree = new int[numCourses];
        visited = new int[numCourses];
        for(int i=0; i<numCourses; i++) {
            indegree[i] = 0;
            visited[i] = 0;
        }
        map = new HashMap<>();
        for(int[] edge: prerequisites) {
            int from = edge[1], to = edge[0];
            if(!map.containsKey(from)) map.put(from, new LinkedList<>());
            var list = map.get(from);
            list.add(to);
            indegree[to]++;
        }
        
        // start DFS
        res = new int[numCourses];
        count = numCourses-1;
        for(int i=0; i<numCourses; i++) {
            if(indegree[i]==0 && visited[i]==0) {
                if(!dfs(i)) {
                    return new int[0];
                }
            }
        }
        return count==-1? res : new int[0];
    }
    
    private boolean dfs(int node) {
        visited[node] = 1;
        for(int toNode: map.getOrDefault(node, Collections.emptyList())) {
            if(visited[toNode]==1) {
                return false;
            } else if(visited[toNode]==0 && !dfs(toNode)) {
                return false;
            }
        }
        visited[node] = 2;
        res[count--] = node;
        return true;
    }
}

Minimum Spanning Tree

Prim

  • Prim algorithm is based on the greedy idea. Every iteration it chooses an un-visited node with the lowest cost from the storage, and then it adds all of its adjacent un-visited nodes into the storage with their costs. After $n$ iterations, the MST can be achieved.
  • Time complexity:
    • Note $E$ is the number of edges, and $V$ is the number of nodes in the graph.
    • Adjacency matrix implementation: $O(V^2)$.
    • Binary heap + adjacency list implementation: $O(E*logV)$.
      • Why it’s $logV$?: see this post.
    • Fibonacci heap: …
  • Therefore, in a dense graph, Adjacency matrix implementation is better. Otherwise, heap implementations are better.
  • Example problem. LC 1135
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    class Solution {
        public int minimumCost(int n, int[][] connections) {
            // init
            int visited[] = new int[n+1];
            Map<Integer, List<int[]>> map = new HashMap<>();
            Queue<int[]> q = new PriorityQueue<int[]>((a,b) -> a[1] - b[1]);
            int cost = 0;
            int numOfVisited = n;
            for(int i=0; i<connections.length; i++) {
                int p1 = connections[i][0], p2 = connections[i][1], v = connections[i][2];
                if(!map.containsKey(p1)) { map.put(p1, new ArrayList<>()); }
                if(!map.containsKey(p2)) { map.put(p2, new ArrayList<>()); }
                List<int[]> l1 = map.get(p1); l1.add(new int[]{p2, v});
                List<int[]> l2 = map.get(p2); l2.add(new int[]{p1, v});            
            }
            
            // add initial points
            int initP = connections[0][0];
            visited[initP] = 1; 
            numOfVisited--;
            for(int[] e: map.get(initP)) {
                q.add(e);
            }
            
            // Prim
            while(!q.isEmpty()) {
                int[] e = q.poll();
                int toNode = e[0], v = e[1];
                if(visited[toNode]==1) {
                    continue;
                }
                visited[toNode]=1;
                numOfVisited--;
                cost+=v;
                for(int[] toNodeE: map.get(toNode)) {
                    if(visited[toNodeE[0]]!=1) {
                        q.add(toNodeE);
                    }
                }
            }
            return numOfVisited==0?cost:-1;
        }
    }

Kruskal

  • Kruskal algorithm pick ups the edge with lowest cost that doesn’t include a cycle every iteration, after $n-1$ iterations, the MST can be achieved.
  • Time complexity: $O(ElogE) = O(ElogV)$, where $E$ is the number of edges, and $V$ is the number of nodes in the graph.
  • Example problem. LC 1135
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    class Solution {
        public int minimumCost(int n, int[][] connections) {
            Arrays.sort(connections, (a, b) -> a[2] - b[2]);
            UF uf = new UF(n+1);
            int cost = 0;
            int count = n-1;
            for(int i=0; i<connections.length; i++) {
                int n1 = connections[i][0], n2 = connections[i][1], v = connections[i][2];
                if(uf.union(n1, n2)) {
                    cost+=v;
                    count--;
                }
            }
            return count==0?cost:-1;
        }
        
        class UF {
            int[] parent;
            UF(int n) {
                parent = new int[n];
                for(int i=0; i<n; i++) {
                    parent[i] = i;
                }
            }
            int find(int i) {
                if(parent[i]!=i) {
                    parent[i] = find(parent[i]);
                }
                return parent[i];
            }
            boolean union(int i, int j) {
                int pi = find(i);
                int pj = find(j);
                if(pi==pj) return false;
                parent[pi] = pj;
                return true;
            }
        }
    }

Single Source Shortest Path

Dijkstra

  • Dijkstra algorithm is also based on the greedy idea. It is used to compute the shortest path from a given start node to all rest reachable nodes in the graph.
  • Just like prim algo., every iteration, it picks up an un-visited node with the shortest path, then it evaluates all of the nodes’ unvisited neighbors, update the distance if needed and insert the neighbor nodes into the storage.
  • However, Dijkstra algo. can only be used in graph with non-negative edges.
  • Time Complexity: just like the analysis of Prim:
    • Adjacency matrix implementation: $O(V^2)$.
    • Binary heap + adjacency list implementation: $O(E*logV)$.
  • Example: Leetcode 743
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    class Solution {
        public int networkDelayTime(int[][] times, int n, int k) {
            int[] dis = new int[n+1];
            for(int i=1; i<=n; i++) {
                dis[i] = -1;
            }
            dis[k] = 0;
            Set<Integer> set = new HashSet<>();
            Map<Integer, List<int[]>> map = new HashMap<>();
            for(int i=0; i<times.length; i++) {
                int from = times[i][0], to = times[i][1], cost = times[i][2];
                map.computeIfAbsent(from, list -> new ArrayList<>()).add(new int[]{to, cost});
            }
            PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> a[1]-b[1]);
            for(int[] e: map.getOrDefault(k, new ArrayList<>())) {
                dis[e[0]] = e[1]; // Note here
                q.add(new int[]{e[0], e[1]});
            }
            set.add(k);
            
            while(!q.isEmpty()) {
                int[] e = q.poll();
                int from = e[0];
                if(set.contains(from)) continue; // Note here
                set.add(from);
                for(int[] fromE: map.getOrDefault(from, new ArrayList<>())) {
                    if(set.contains(fromE[0])) continue; // Note here
                    int cost = dis[from] + fromE[1];
                    if(dis[fromE[0]]==-1 || cost<dis[fromE[0]]) {
                        dis[fromE[0]] = cost;
                        q.add(new int[]{fromE[0], dis[fromE[0]]}); // Note here
                    }
                }
            }
            
            if(set.size() < n) return -1;
            int max = -1;
            for(int i=1; i<=n; i++) {
                max = Math.max(max, dis[i]);
            }
            return max;
        }
    }

Bellman-ford

  • Bellman-ford algorithm is a SSSP algorithm that can be applied in any graphs. However, if the graph contains a negative loop, the algorithm will fail.
  • This algorithm will try $n-1$ iterations, in each iteration, it iterates all the edges and tries to update the distance.
  • Time complexity: $O(VE)$

  • Example problem: Leetcode 743

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    class Solution {
        public int networkDelayTime(int[][] times, int n, int k) {
            int[] dis = new int[n+1];
            for(int i=1; i<=n; i++) {
                dis[i] = -1;
            }
            dis[k] = 0;

            for(int i=0; i<n; i++) {
                boolean flag = false;
                for(int j=0; j<times.length; j++) {
                    int from = times[j][0], to = times[j][1], cost = times[j][2];
                    if(dis[from] != -1) {
                        if(dis[to]==-1 || cost + dis[from] < dis[to]) {
                            dis[to] = cost + dis[from];
                            flag = true;
                        }
                    }
                }
                if(!flag) break;
            }

            int max = -1;
            for(int i=1; i<=n; i++) {
                if(dis[i]==-1) return -1;
                max = Math.max(max, dis[i]);
            }
            return max;
        }
    }

  • How to detect a loop with negative value? after the $n-1$ rounds, try to update the distance again, if there is a chance, then the negative loop exists.

  • Shortest Path Faster Algorithm: TODO

Multiple Sources Shortest Path

Floyd

  • Floyd algorithm is used to find shortest path from multiple source nodes. It can be used in graph with negative edges.
  • Time complexity: $O(V^3)$
  • Example code: Leetcode 743
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    class Solution {
        public int networkDelayTime(int[][] times, int n, int k) {
            long[][] dis = new long[n+1][n+1];
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=n; j++)
                    dis[i][j] = Integer.MAX_VALUE;
                dis[i][i] = 0;
            }
                
            for(int i=0; i<times.length; i++) {
                int from = times[i][0], to = times[i][1], cost = times[i][2];
                dis[from][to] = cost;
            }

            for(int t=1; t<=n; t++) {
                for(int i=1; i<=n; i++) {
                    for(int j=1; j<=n; j++) {
                        dis[i][j] = Math.min(dis[i][t] + dis[t][j], dis[i][j]);
                    }
                }
            }

            long max = -1;
            for(int i=1; i<=n; i++) {
                if(dis[k][i]==Integer.MAX_VALUE) return -1;
                max = Math.max(max, dis[k][i]);
            }
            return (int)max;
        }
    }

Critical Connection