拓扑排序中的最小内存使用

Kahn算法

Kahn算法是拓扑排序中最常用的算法，也是内存使用最小的算法之一。该算法是基于宽度优先搜索（BFS）的，核心思想是不断找到入度为0的节点并将其从图中移除，直到图中所有节点都被移除。

以下是Kahn算法的Python代码实现：

def topo_sort(graph):
    in_degree = {node: 0 for node in graph}  # 计算每个节点的入度
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
            
    queue = [node for node in graph if in_degree[node] == 0]  # 入度为0的节点入队
    
    result = []  # 存储拓扑排序结果
    
    while queue:
        node = queue.pop(0)
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1  # 更新入度
            if in_degree[neighbor] == 0:
                queue.append(neighbor)  # 入度为0的节点入队
                
    if len(result) == len(graph):
        return result
    else:
        print("图中存在环！")

在这个实现中，我们使用了一个in_degree字典来存储每个节点的入度。我们首先计算每个节点的入度，并将所有入度为0的节点加入队列中。然后，我们不断从队列中出队一个节点，并将其添加到拓扑排序结果中。接着，我们更新该节点所有邻居节点的入度，如果有节点的入度变成了0，就将其入队。最后，我们将得到的拓扑排序结果返回。如果拓扑排序结果中节点数量少于图中节点数量，就说明图中存在环。

这个实现只使用了O(V+E)的内存，其中V是节点数量