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

上篇文章我们介绍了使用深度优先搜索实现拓扑排序根据每个节点搜索完成的顺序反向得到拓扑排序。使用广度优先搜索实现拓扑排序则可以正向得到拓扑排序。首先计算每个节点的入度只有入度为 0 的节点可能是拓扑排序中最前面的节点。当一个节点加入拓扑排序之后该节点的所有相邻节点的入度都减 1表示相邻节点少了一条入边。当一个节点的入度变成 0 则该节点前面的节点都已经加入拓扑排序该节点也可以加入拓扑排序。具体做法是使用队列存储可以加入拓扑排序的节点初始时将所有入度为 0 的节点入队列。每次将一个节点出队列并加入拓扑排序中然后将该节点的所有相邻节点的入度都减 1 如果一个相邻节点的入度变成 0 则将该相邻节点入队列。重复上述操作直到队列为空时广度优先搜索结束。如果有向图中无环则每个节点都将加入拓扑排序因此拓扑排序的长度等于字典中的字母个数。如果有向图中有环则环中的节点不会加入拓扑排序因此拓扑排序的长度小于字典中的字母个数。广度优先搜索结束时判断拓扑排序的长度是否等于字典中的字母个数即可判断有向图中是否有环。如果拓扑排序的长度等于字典中的字母个数则拓扑排序包含字典中的所有字母返回拓扑排序如果拓扑排序的长度小于字典中的字母个数则有向图中有环不存在拓扑排序。如果拓扑排序的长度小于字典中的字母个数则有向图中有环不存在拓扑排序。代码Python3class 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 Javaclass Solution { MapCharacter, ListCharacter edges new HashMapCharacter, ListCharacter(); MapCharacter, Integer indegrees new HashMapCharacter, 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 ArrayListCharacter()); } } for (int i 1; i length valid; i) { addEdge(words[i - 1], words[i]); } if (!valid) { return ; } QueueCharacter queue new ArrayDequeCharacter(); SetCharacter 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); ListCharacter 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 条边和 ∣Σ∣ 个节点。