拓扑排序 + 广度优先搜索法实例应用（二）

上篇文章，我们介绍了使用深度优先搜索实现拓扑排序，根据每个节点搜索完成的顺序反向得到拓扑排序。使用广度优先搜索实现拓扑排序，则可以正向得到拓扑排序。

首先计算每个节点的入度，只有入度为 0 的节点可能是拓扑排序中最前面的节点。当一个节点加入拓扑排序之后，该节点的所有相邻节点的入度都减 1，表示相邻节点少了一条入边。当一个节点的入度变成 0 ，则该节点前面的节点都已经加入拓扑排序，该节点也可以加入拓扑排序。

具体做法是：使用队列存储可以加入拓扑排序的节点，初始时将所有入度为 0 的节点入队列。每次将一个节点出队列并加入拓扑排序中，然后将该节点的所有相邻节点的入度都减 1 ，如果一个相邻节点的入度变成 0 ，则将该相邻节点入队列。重复上述操作，直到队列为空时，广度优先搜索结束。

如果有向图中无环，则每个节点都将加入拓扑排序，因此拓扑排序的长度等于字典中的字母个数。如果有向图中有环，则环中的节点不会加入拓扑排序，因此拓扑排序的长度小于字典中的字母个数。广度优先搜索结束时，判断拓扑排序的长度是否等于字典中的字母个数，即可判断有向图中是否有环。

• 如果拓扑排序的长度等于字典中的字母个数，则拓扑排序包含字典中的所有字母，返回拓扑排序；
• 如果拓扑排序的长度小于字典中的字母个数，则有向图中有环，不存在拓扑排序。如果拓扑排序的长度小于字典中的字母个数，则有向图中有环，不存在拓扑排序。

代码

Python3

class Solution: def alienOrder(self, words: List[str]) -> str: g = defaultdict(list) inDeg = {c: 0 for c in words[0]} for s, t in pairwise(words): for c in t: inDeg.setdefault(c, 0) for u, v in zip(s, t): if u != v: g[u].append(v) inDeg[v] += 1 break else: if len(s) > len(t): return "" q = [u for u, d in inDeg.items() if d == 0] for u in q: for v in g[u]: inDeg[v] -= 1 if inDeg[v] == 0: q.append(v) return ''.join(q) if len(q) == len(inDeg) else ""

Java

class Solution { Map<Character, List<Character>> edges = new HashMap<Character, List<Character>>(); Map<Character, Integer> indegrees = new HashMap<Character, Integer>(); boolean valid = true; public String alienOrder(String[] words) { int length = words.length; for (String word : words) { int wordLength = word.length(); for (int j = 0; j < wordLength; j++) { char c = word.charAt(j); edges.putIfAbsent(c, new ArrayList<Character>()); } } for (int i = 1; i < length && valid; i++) { addEdge(words[i - 1], words[i]); } if (!valid) { return ""; } Queue<Character> queue = new ArrayDeque<Character>(); Set<Character> letterSet = edges.keySet(); for (char u : letterSet) { if (!indegrees.containsKey(u)) { queue.offer(u); } } StringBuffer order = new StringBuffer(); while (!queue.isEmpty()) { char u = queue.poll(); order.append(u); List<Character> adjacent = edges.get(u); for (char v : adjacent) { indegrees.put(v, indegrees.get(v) - 1); if (indegrees.get(v) == 0) { queue.offer(v); } } } return order.length() == edges.size() ? order.toString() : ""; } public void addEdge(String before, String after) { int length1 = before.length(), length2 = after.length(); int length = Math.min(length1, length2); int index = 0; while (index < length) { char c1 = before.charAt(index), c2 = after.charAt(index); if (c1 != c2) { edges.get(c1).add(c2); indegrees.put(c2, indegrees.getOrDefault(c2, 0) + 1); break; } index++; } if (index == length && length1 > length2) { valid = false; } } }

复杂度分析

• 时间复杂度：O(n×L +∣Σ∣) ，其中 n 是数组 words 的长度，即字典中的单词数， L 是字典中的平均单词长度，Σ 是字典中的字母集合。遍历字典构造有向图需要 O(n×L) 的时间，由于有向图包含最多 n−1 条边和 ∣Σ∣ 个节点，因此广度优先搜索需要 O(n +∣Σ∣) 的时间，总时间复杂度是 O(n×L + n +∣Σ∣) = O(n×L +∣Σ∣) 。
• 空间复杂度：O(n+∣Σ∣) ，其中 n 是数组 words 的长度，即字典中的单词数，Σ 是字典中的字母集合。空间复杂度主要取决于存储有向图需要的空间，有向图包含最多 n−1 条边和 ∣Σ∣ 个节点。