算法奇妙屋(十七)-BFS解决拓扑排序问题

景画

发布于 2025-12-19 13:34:37

算法整体解析

这里我们会介绍什么事有向无环图, 有向无环图应用, 什么是拓扑排序, 以及拓扑排序如何实现, 算是拓扑排序的整体解析, 后面的题都离不开这个推导过程

一. 力扣 207. 课程表

1. 题目解析

2. 算法原理

从如何建图, 建什么图, 怎么用建的图三个方面来讲解

3. 代码

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];
        Map<Integer,List<Integer>> hash = new HashMap<>();
        // 建邻接表
        for (int i = 0; i < prerequisites.length; i++) {
            int a = prerequisites[i][0];
            int b = prerequisites[i][1]; // b->a a的入度+1
            in[a]++;
            if (!hash.containsKey(b)) {
                hash.put(b, new ArrayList<>());
            }
            hash.get(b).add(a);
        }
        // 加入队列
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) {
                q.offer(i); // 加入的是这门课 i
            }
        }
        while(!q.isEmpty()) {
            int t = q.poll();
            for (int x : hash.getOrDefault(t, new ArrayList<>())) {
                in[x]--;
                if (in[x] == 0) {
                    q.offer(x);
                }
            }
        }
        // 判断是否有环
        for (int x : in) {
            if (x > 0) {
                return false;
            }
        }
        return true;
    }

二. 力扣 210. 课程表 II

1. 题目解析

2. 算法原理

因为这道题和课程表I原理基本一模一样, 唯一的不同已经在题目解析解释过了, 这里我就直接把上道题的算法原理copy过来, 方便大家观看

3. 代码

    public int[] findOrder(int n, int[][] p) {
        int[] in = new int[n];
        Map<Integer, List<Integer>> hash = new HashMap<>();
        // 建邻接表
        for (int i = 0; i < p.length; i++) {
            int a = p[i][0];
            int b = p[i][1]; // b->a
            in[a]++;
            if (!hash.containsKey(b)) {
                hash.put(b, new ArrayList<>());
            }
            hash.get(b).add(a);
        }
        // 加入队列
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) {
                q.offer(i);
            }
        }
        int[] ret = new int[n];
        int step = 0;
        while(!q.isEmpty()) {
            int t = q.poll();
            ret[step++] = t;
            for (int x : hash.getOrDefault(t, new ArrayList<>())) {
                in[x]--;
                if (in[x] == 0) {
                    q.offer(x);
                }
            }
        }
        return step == n ? ret : new int[0];
    }

三. 力扣 LCR 114. 火星词典

1. 题目解析

这道题是简直offer的一道题, 只能说算法原理并不难想, 看完题解就能想明白, 但是细节问题巨多, 小编做这道题做了4个小时😭, 一点点调试出来的

2. 算法原理

细节很多, 干货满满, 具体细节和需要注意的点都写到下方图解里面了⬇️

3. 代码

    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> hash = new HashMap<>();
        Map<Character, Integer> in = new HashMap<>();
        int n = words.length;
        // 初始化入度表 in
        for (String s : words) {
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                in.put(ch, 0);
            }
        }
        // 建图和给入度表赋值
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                String prev = words[i];
                String next = words[j];
                for (int k = 0; k < prev.length(); k++) {
                    char pch = prev.charAt(k);
                    if (k < next.length()) {
                        char nch = next.charAt(k);
                        if (pch != nch) {
                            if (!hash.containsKey(pch)) {
                                hash.put(pch, new HashSet<>());
                            }
                            if (!hash.get(pch).contains(nch)) {
                                in.put(nch, in.get(nch) + 1);
                            }
                            hash.get(pch).add(nch);
                            break;
                        }
                    } else {
                        // 出现了abc在前 ab在后这种情况, 直接不合理!
                        return "";
                    }
                }
            }
        }
        // 初始化队列
        Queue<Character> q = new LinkedList<>();
        for (Map.Entry<Character, Integer> x : in.entrySet()) {
            if (x.getValue() == 0) {
                q.offer(x.getKey());
            }
        }
        // 拓扑排序
        StringBuilder ret = new StringBuilder();
        while (!q.isEmpty()) {
            char ch = q.poll();
            ret.append(ch);
            for (char c : hash.getOrDefault(ch, new HashSet<>())) {
                // 所有元素入度数-1
                in.put(c, in.get(c) - 1);
                if (in.get(c) == 0) {
                    q.offer(c);
                }
            }
        }
        for (Map.Entry<Character, Integer> x : in.entrySet()) {
            if (x.getValue() != 0) {
                return "";
            }
        }
        return ret.toString();
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-09，如有侵权请联系 cloudcommunity@tencent.com 删除

算法