Topological Sort

模板

  1. 首先通过Map创建图graph，graph的key是节点，graph的value是节点key后继的集合；一般如下定义

    1
    Map<Character, Set<Character>> graph = new HashMap<>();

  2. 创建一个节点映射其入度的Map；一般如下定义

    1
    Map<Character, Integer> inDegrees = new HashMap<>();

  3. 初始化graph的节点，把每个节点都加入图中；初始化inDegrees

    1
    2
    3
    4
    5
    6
    for (String word : words) {
        for (char ch : word.toCharArray()) {
            graph.putIfAbsent(ch, new HashSet<>());
            inDegrees.putIfAbsent(ch, 0);
        }
    }

  4. 初始化graph的边，同时计算入度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    for (int i = 1; i < words.length; ++i) {
        String word1 = words[i - 1], word2 = words[i];
        for (int j = 0; j < word1.length() && j < word2.length(); ++j) {
            char ch1 = word1.charAt(j), ch2 = word2.charAt(j);
            if (ch1 != ch2) {
                if (!graph.get(ch1).contains(ch2)) {
                    graph.get(ch1).add(ch2);
                    inDegrees.put(ch2, inDegrees.get(ch2) + 1);
                }
                break;
            }
        }
    }

  5. 创建队列，并把入度为0的节点加入队列

    1
    2
    3
    4
    Queue<Character> queue = new LinkedList<>();
    for (char key : inDegrees.keySet())
        if (inDegrees.get(key) == 0)
            queue.offer(key);

  6. 创建一个记录结果的容器，每次从queue中取出一个节点，把该节点加入结果集，并将该节点后继的入度减一，如果该节点后继的入度为0，则加入队列

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            char node = queue.poll();
            sb.append(node);
            for (char next : graph.get(node)) {
                inDegrees.put(next, inDegrees.get(next) - 1);
                if (inDegrees.get(next) == 0)
                    queue.offer(next);
            }
        }

  7. 如果结果集包含所有节点，则是有向无环图

207. 课程表

方法一：拓扑排序

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
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // key表示先修的课程，value表示list中的课程需要先修key
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < numCourses; ++i)
            graph.put(i, new LinkedList<>());
        int[] inDegrees = new int[numCourses];
        for (int[] arr : prerequisites) {
            graph.get(arr[1]).add(arr[0]);
            ++inDegrees[arr[0]];
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i)
            if (inDegrees[i] == 0)
                queue.offer(i);
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int next : graph.get(node)) {
                if (--inDegrees[next] == 0)
                    queue.offer(next);
            }
        }
        return order.size() == numCourses ? true : false;
    }
}

210. 课程表 II

方法一：拓扑排序

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
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < numCourses; ++i)
            graph.put(i, new LinkedList<>());
        int[] inDegrees = new int[numCourses];
        for (int[] arr : prerequisites) {
            graph.get(arr[1]).add(arr[0]);
            ++inDegrees[arr[0]];
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i)
            if (inDegrees[i] == 0)
                queue.offer(i);
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int next : graph.get(node)) {
                if (--inDegrees[next] == 0)
                    queue.offer(next);
            }
        }
        return order.size() == numCourses ? order.stream().mapToInt(i->i).toArray() : new int[0];
    }
}

剑指 Offer II 114. 外星文字典

方法一：拓扑排序

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
class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> inDegrees = new HashMap<>();
        for (String word : words) {
            for (char ch : word.toCharArray()) {
                graph.putIfAbsent(ch, new HashSet<>());
                inDegrees.putIfAbsent(ch, 0);
            }
        }
        for (int i = 1; i < words.length; ++i) {
            String word1 = words[i - 1], word2 = words[i];
            if (word1.startsWith(word2) && !word1.equals(word2))
                return "";
            for (int j = 0; j < word1.length() && j < word2.length(); ++j) {
                char ch1 = word1.charAt(j), ch2 = word2.charAt(j);
                if (ch1 != ch2) {
                    if (!graph.get(ch1).contains(ch2)) {
                        graph.get(ch1).add(ch2);
                        inDegrees.put(ch2, inDegrees.get(ch2) + 1);
                    }
                    break;
                }
            }
        }
        Queue<Character> queue = new LinkedList<>();
        for (char key : inDegrees.keySet())
            if (inDegrees.get(key) == 0)
                queue.offer(key);
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            char node = queue.poll();
            sb.append(node);
            for (char next : graph.get(node)) {
                inDegrees.put(next, inDegrees.get(next) - 1);
                if (inDegrees.get(next) == 0)
                    queue.offer(next);
            }
        }
        return sb.length() == inDegrees.size() ? sb.toString() : "";
    }
}

剑指 Offer II 115. 重建序列

方法一：拓扑排序

判断有向图的拓扑排序序列是否唯一

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
class Solution {
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> inDegrees = new HashMap<>();
        for (int[] seq : sequences) {
            for (int i = 0; i < seq.length; ++i) {
                graph.putIfAbsent(seq[i], new HashSet<>());
                inDegrees.putIfAbsent(seq[i], 0);
            }
        }
        for (int[] seq : sequences) {
            for (int i = 1; i < seq.length; ++i) {
                int num1 = seq[i - 1], num2 = seq[i];
                if (!graph.get(num1).contains(num2)) {
                    graph.get(num1).add(num2);
                    inDegrees.put(num2, inDegrees.get(num2) + 1);
                }
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int node : inDegrees.keySet())
            if (inDegrees.get(node) == 0)
                queue.offer(node);
        List<Integer> order = new LinkedList<>();
        while (queue.size() == 1) {
            int node = queue.poll();
            order.add(node);
            for (int next : graph.get(node)) {
                inDegrees.put(next, inDegrees.get(next) - 1);
                if (inDegrees.get(next) == 0)
                    queue.offer(next);
            }
        }
        int[] res = order.stream().mapToInt(i->i).toArray();
        return Arrays.equals(res, nums);
    }
}

二刷

返回queue.isEmpty();就好，如下例，节点1和3的入度都为0，queue.size()为二，不进入while(queue.size() == 1)，此时queue中有1和3，不为空，所以返回false

1
2
3
4
5
输入：nums = [1,2,3], sequences = [[1,2]]
输出：false
解释：最短可能的超序列为 [1,2]。
序列 [1,2] 是它的子序列：[1,2]。
因为 nums 不是最短的超序列，所以返回false。

代码

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 boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        int n = nums.length;
        Map<Integer, List<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> inDegrees = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            graph.putIfAbsent(nums[i], new LinkedList<>());
            inDegrees.putIfAbsent(nums[i], 0);
        }
        for (int[] sequence : sequences) {
            for (int i = 1; i < sequence.length; ++i) {
                graph.get(sequence[i - 1]).add(sequence[i]);
                inDegrees.put(sequence[i], inDegrees.get(sequence[i]) + 1);
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int key : inDegrees.keySet())
            if (inDegrees.get(key) == 0)
                queue.offer(key);
        while (queue.size() == 1) {
            int node = queue.poll();
            for (int next : graph.get(node)) {
                inDegrees.put(next, inDegrees.get(next) - 1);
                if (inDegrees.get(next) == 0)
                    queue.offer(next);
            }
        }
        return queue.isEmpty();
    }
}

三刷

inDegrees换成数组

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
class Solution {
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        int n = nums.length;
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] inDegrees = new int[n + 1];
        for (int i = 0; i < n; ++i) 
            graph.putIfAbsent(nums[i], new LinkedList<>());
        for (int[] sequence : sequences) {
            for (int i = 1; i < sequence.length; ++i) {
                graph.get(sequence[i - 1]).add(sequence[i]);
                ++inDegrees[sequence[i]];
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; ++i)
            if (inDegrees[i] == 0)
                queue.offer(i);
        while (queue.size() == 1) {
            int node = queue.poll();
            for (int next : graph.get(node)) {
                --inDegrees[next];
                if (inDegrees[next] == 0)
                    queue.offer(next);
            }
        }
        return queue.isEmpty();
    }
}

310. 最小高度树

方法一：拓扑排序

  1. 此题的思路是：找到所有边缘上的节点，然后一层一层删除，直到队列为空，那队列中最后的值就是答案了。比如样例1：边缘的节点为0，2，3，删除后就只剩下1了。不难发现，边缘的节点就是度数为1的节点。

  2. 定义graph时为空，需要初始化每一个List

    1
    List<Integer>[] graph = new List[n];
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
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1)
            return Arrays.asList(0);
        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; ++i)
            graph[i] = new ArrayList<>();
        int[] degree = new int[n];
        for (int[] edge : edges) {
            int node1 = edge[0], node2 = edge[1];
            graph[node1].add(node2);
            graph[node2].add(node1);
            ++degree[node1];
            ++degree[node2];
        }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; ++i)
            if (degree[i] == 1)
                queue.offer(i);
        List<Integer> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            res = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                int node = queue.poll();
                res.add(node);
                for (int next : graph[node]) {
                    if (--degree[next] == 1)
                        queue.offer(next);
                }
            }
        }
        return res;
    }
}

二刷

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
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1)
            return Arrays.asList(0);
        List<Integer> res = new LinkedList<>();
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] degrees = new int[n];
        for (int i = 0; i < n; ++i)
            graph.put(i, new LinkedList<>());
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1];
            graph.get(from).add(to);
            graph.get(to).add(from);
            degrees[from]++;
            degrees[to]++;
        }
        for (int i = 0; i < n; i++)
            if (degrees[i] == 1)
                queue.offer(i);
        while (!queue.isEmpty()) {
            res.clear();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int node = queue.poll();
                res.add(node);
                for (int next : graph.get(node)) {
                    if (--degrees[next] == 1)
                        queue.offer(next);
                }
            }
        }
        return res;
    }
}

802. 找到最终的安全状态

方法一：拓扑排序

  1. 找到所有不进入环的节点
  2. 求反向图，拓扑排序
  3. 入度为0的节点符合要求
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
class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        List<Integer>[] adj = new List[n];
        int[] indegrees = new int[n];
        for (int i = 0; i < n; ++i) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < graph.length; ++i) {
            for (int j = 0; j < graph[i].length; ++j) {
                adj[graph[i][j]].add(i);
            }
            indegrees[i] = graph[i].length;
        }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; ++i)
            if (indegrees[i] == 0)
                queue.offer(i);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int next : adj[node])
                if (--indegrees[next] == 0)
                    queue.offer(next);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; ++i)
            if (indegrees[i] == 0)
                res.add(i);
        return res;
    }
}

二刷

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
class Solution {
    public List<Integer> eventualSafeNodes(int[][] g) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int n = g.length;
        int[] outDegrees = new int[n];
        for (int i = 0; i < n; ++i)
            graph.put(i, new ArrayList<>());
        for (int i = 0; i < g.length; ++i) {
            for (int j = 0; j < g[i].length; ++j) {
                graph.get(g[i][j]).add(i);
                outDegrees[i]++;
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; ++i)
            if (outDegrees[i] == 0)
                queue.offer(i);
        while(!queue.isEmpty()) {
            int node = queue.poll();
            for (int next : graph.get(node)) {
                if (--outDegrees[next] == 0)
                    queue.offer(next);
            }
        }
        List<Integer> res = new LinkedList<>();
        for (int i = 0; i < n; i++) 
            if (outDegrees[i] == 0)
                res.add(i);
        return res;
    }
}

2603. 收集树中金币

方法一：两次拓扑排序

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
class Solution {
    public int collectTheCoins(int[] coins, int[][] edges) {
        int n = edges.length + 1;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        int[] degree = new int[n];
        for (int[] edge : edges) {
            int from = edge[0], to = edge[1];
            g[from].add(to);
            g[to].add(from);
            ++degree[from];
            ++degree[to];
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; ++i)
            if (degree[i] == 1 && coins[i] == 0)
                queue.offer(i);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int next : g[node])
                if (--degree[next] == 1 && coins[next] == 0)
                    queue.offer(next);
        }
        for (int i = 0; i < n; ++i)
            if (degree[i] == 1 && coins[i] == 1)
                queue.offer(i);
        int[] times = new int[n];
        int t = 1;
        while (!queue.isEmpty()) {
            int size= queue.size();
            for (int i = 0; i < size; ++i) {
                int node = queue.poll();
                for (int next : g[node]) {
                    if (--degree[next] == 1) {
                        queue.offer(next);
                        times[next] = t;
                    }
                }
            }
            ++t;
        }
        int res = 0;
        for (int[] edge : edges)
            if (times[edge[0]] >= 2 && times[edge[1]] >= 2)
                res += 2;
        return res;
    }
}

2876. 有向图访问计数

方法一：拓扑排序 + 反向图

注意内向基环图可以包含多个环！！！

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
class Solution {
    public int[] countVisitedNodes(List<Integer> g) {
        int n = g.size();
        int[] degree = new int[n];
        List<Integer>[] rg = new List[n];
        Arrays.setAll(rg, e -> new ArrayList<>());
        for (int i = 0; i < n; ++i) {
            int from = i, to = g.get(i);
            degree[to]++;
            rg[to].add(from);
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; ++i)
            if (degree[i] == 0)
                queue.offer(i);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            int next = g.get(node);
            if (--degree[next] == 0)
                queue.offer(next);
        }
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            if (degree[i] <= 0)
                continue;
            List<Integer> ring = new ArrayList<>();
            int j = i;
            while (true) {
                ring.add(j);
                degree[j] = -1;
                j = g.get(j);
                if (j == i)
                    break;
            }
            for (int x : ring)
                dfs(x, ring.size(), rg, res, degree);
        }
        return res;
    }

    private void dfs(int x, int size, List<Integer>[] rg, int[] res, int[] degree) {
        res[x] = size;
        for (int next : rg[x]) {
            if (degree[next] == 0)
                dfs(next, size + 1, rg, res, degree);
        }
    }

}

2360. 图中的最长环

方法一：拓扑排序 + 基环树

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
class Solution {
    public int longestCycle(int[] g) {
        int n = g.length;
        Queue<Integer> queue = new LinkedList<>();
        int[] degree = new int[n];
        for (int i = 0; i < n; ++i)  {
            if (g[i] != -1)
                degree[g[i]]++;
        }
        for (int i = 0; i < n; ++i)
            if (degree[i] == 0)
                queue.offer(i);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            int next = g[node];
            if (next == -1)
                continue;
            if (--degree[next] == 0)
                queue.offer(next);
        }
        int res = -1;
        for (int i = 0; i < n; ++i) {
            if (degree[i]<= 0)
                continue;
            degree[i] = -1;
            List<Integer> ring = new ArrayList<>();
            ring.add(i);
            int next = g[i];
            while (true) {
                if (next == i)
                    break;
                degree[next] = -1;
                ring.add(next);
                next = g[next];
            }
            if (ring.size() > 0)
                res = Math.max(res, ring.size());
        }
        return res;
    }
}
Algorithms > Graph
#图 #拓扑排序
Topological Sort
https://leopol1d.github.io/2023/05/29/topological-sort/
作者
Leopold
发布于
2023年5月29日
许可协议