拓扑排序Python

拓扑排序是一种对有向无环图(DAG)进行排序的算法，它可以确定图中节点的线性顺序，使得对于图中的每一条有向边 (u, v)，节点 u 在排序中都排在节点 v 的前面。在Python中，我们可以使用广度优先搜索（BFS）或深度优先搜索（DFS）来实现拓扑排序。

一种方法是使用广度优先搜索（BFS）。我们首先构建一个入度矩阵，记录每个节点的入度（即指向该节点的边的数量）。然后，我们创建一个队列，并将入度为0的节点加入队列中。接下来，我们循环处理队列中的节点，将其添加到结果列表中，并更新其子节点的入度。如果子节点的入度变为0，则将其加入队列。如果最终结果列表的长度小于图中节点的数量，则说明图中存在环。否则，结果列表就是拓扑排序的结果。

下面是使用广度优先搜索实现拓扑排序的Python代码示例：

# 构建图类
class Graph():
    ...
    
    def topological_sort(self):
        in_degree_map = {}  # 入度map
        queue = Queue()
        result = []
        
        # 构造入度矩阵
        for vertex in self.vertices.values():
            if len(vertex.inEdges) == 0:
                queue.put(vertex)  # 入队
            else:
                in_degree_map[vertex = len(vertex.inEdges)
        
        while not queue.empty():
            vertex = queue.get()
            result.append(vertex.value)
            
            for edge in vertex.outEdges:
                in_degree = in_degree_map.get(edge.to) - 1
                in_degree_map[edge.to = in_degree
                if in_degree == 0:
                    queue.put(edge.to)
        
        if len(result) < len(self.vertices):
            print('图有环，无法进行拓扑排序')
        else:
            print('图无环，拓扑排序结果为：')
            print(result)

另一种方法是使用深度优先搜索（DFS）。我们可以给每个节点标记3种状态：未访问、正在访问和已访问。在DFS过程中，我们首先将节点标记为正在访问，然后递归地访问其邻居节点。当我们遇到一个已经标记为正在访问的节点时，说明图中存在环，无法进行拓扑排序。当我们访问完一个节点的所有邻居节点后，我们将该节点标记为已访问，并将其添加到结果列表的开头。最后，结果列表的顺序就是拓扑排序的结果。

这是使用深度优先搜索实现拓扑排序的Python代码示例：

# 构建图类
class Graph():
    ...
    
    def topological_sort_dfs(self):
        color_map = {}  # 节点颜色map
        result = []
        
        def dfs(vertex):
            nonlocal result
            color_map[vertex = 'gray'  # 标记为正在访问
            
            for edge in vertex.outEdges:
                if color_map.get(edge.to) == 'gray':
                    print('图有环，无法进行拓扑排序')
                    return
                elif color_map.get(edge.to) == 'white':
                    dfs(edge.to)
            
            color_map[vertex = 'black'  # 标记为已访问
            result.insert(0, vertex.value)
        
        for vertex in self.vertices.values():
            color_map[vertex = 'white'  # 标记为未访问
            
        for vertex in self.vertices.values():
            if color_map[vertex == 'white':
                dfs(vertex)
        
        print('图无环，拓扑排序结果为：')
        print(result)

以上是两种使用Python实现拓扑排序的方法：广度优先搜索（BFS）和深度优先搜索（DFS）。具体选择哪种方法取决于实际需求和图的特点。