一般来说使用深度优先搜索实现拓扑排序的总体思想是对于一个特定节点如果该节点的所有相邻节点都已经搜索完成则该节点也会变成已经搜索完成的节点在拓扑排序中该节点位于其所有相邻节点的前面。一个节点的相邻节点指的是从该节点出发通过一条有向边可以到达的节点。由于拓扑排序的顺序和搜索完成的顺序相反因此需要使用一个栈存储所有已经搜索完成的节点。深度优先搜索的过程中需要维护每个节点的状态每个节点的状态可能有三种情况「未访问」、「访问中」和「已访问」。初始时所有节点的状态都是「未访问」。每一轮搜索时任意选取一个「 未访问 」的节点 u 从节点 u 开始深度优先搜索。将节点 u 的状态更新为「 访问中 」对于每个与节点 u 相邻的节点 v 判断节点 v 的状态执行如下操作如果节点 v 的状态是「未访问」则继续搜索节点 v如果节点 v 的状态是「访问中」则找到有向图中的环因此不存在拓扑排序如果节点 v 的状态是「已访问」则节点 v 已经搜索完成并入栈节点 u 尚未入栈因此节点 u 的拓扑顺序一定在节点 v 的前面不需要执行任何操作。当节点 u 的所有相邻节点的状态都是「已访问」时将节点 u 的状态更新为「已访问」并将节点 u 入栈。当所有节点都访问结束之后如果没有找到有向图中的环则存在拓扑排序所有节点从栈顶到栈底的顺序即为拓扑排序。实现方面由于每个节点是一个字母因此可以使用字符数组代替栈当节点入栈时在字符数组中按照从后往前的顺序依次填入每个字母。当所有节点都访问结束之后将字符数组转成字符串即为字典顺序。代码Python3class Solution: def alienOrder(self, words: List[str]) - str: g {} for c in words[0]: g[c] [] for s, t in pairwise(words): for c in t: g.setdefault(c, []) for u, v in zip(s, t): if u ! v: g[u].append(v) break else: if len(s) len(t): return VISITING, VISITED 1, 2 states {} order [] def dfs(u: str) - bool: states[u] VISITING for v in g[u]: if v not in states: if not dfs(v): return False elif states[v] VISITING: return False order.append(u) states[u] VISITED return True return .join(reversed(order)) if all(dfs(u) for u in g if u not in states) else Javaclass Solution { static final int VISITING 1, VISITED 2; MapCharacter, ListCharacter edges new HashMapCharacter, ListCharacter(); MapCharacter, Integer states new HashMapCharacter, Integer(); boolean valid true; char[] order; int index; 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]); } order new char[edges.size()]; index edges.size() - 1; SetCharacter letterSet edges.keySet(); for (char u : letterSet) { if (!states.containsKey(u)) { dfs(u); } } if (!valid) { return ; } return new String(order); } 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); break; } index; } if (index length length1 length2) { valid false; } } public void dfs(char u) { states.put(u, VISITING); ListCharacter adjacent edges.get(u); for (char v : adjacent) { if (!states.containsKey(v)) { dfs(v); if (!valid) { return; } } else if (states.get(v) VISITING) { valid false; return; } } states.put(u, VISITED); order[index] u; index--; } }复杂度分析时间复杂度O(n×L∣Σ∣)其中 n 是数组 words 的长度即字典中的单词数L 是字典中的平均单词长度Σ 是字典中的字母集合。遍历字典构造有向图需要 O(n×L) 的时间由于有向图包含最多 n-1 条边和 ∣Σ∣ 个节点因此深度优先搜索需要 O(n∣Σ∣) 的时间总时间复杂度是 O(n×Ln∣Σ∣) O(n×L∣Σ∣) 。空间复杂度O(n∣Σ∣) 其中 n 是数组 words 的长度即字典中的单词数Σ 是字典中的字母集合。空间复杂度主要取决于存储有向图需要的空间有向图包含最多 n−1 条边和 ∣Σ∣ 个节点。