Python中Graph()的拓扑排序实现

在Python中，可以使用拓扑排序算法对有向无环图（DAG）进行排序。拓扑排序可以应用于很多领域，如任务调度、编译器优化等。下面是一个简单的实现例子。

拓扑排序使用两个列表，一个用于存储节点，一个用于存储排序结果。算法的基本思想是，首先找到所有没有入度的节点，将它们加入排序结果中，并删除与这些节点相关的边。然后，再找到新的没有入度的节点，继续加入排序结果中，并删除相关边。重复这个过程，直到所有节点都加入排序结果中。

首先，我们可以使用字典来表示有向无环图（DAG），其中键是节点，值是与该节点相关的节点列表。

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v):
        self.graph[u].append(v)

然后，我们可以使用拓扑排序算法对该有向无环图进行排序。具体过程如下：

1. 首先，我们需要计算每个节点的入度。我们可以遍历所有节点的相邻节点，并递增其入度计数器。

2. 然后，我们将所有入度为0的节点放入一个队列中，作为排序结果的初始节点。

3. 开始进行循环，直到队列为空。在每一步中，我们从队列中取出一个节点，并将其添加到排序结果中。然后，我们删除该节点，并更新与其相邻节点的入度计数器。

4. 如果更新后的入度为0，则将该节点添加到队列中。

5. 重复步骤3和步骤4，直到所有节点都添加到排序结果中。

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v):
        self.graph[u].append(v)
    
    def topological_sort(self):
        # 计算每个节点的入度
        in_degree = defaultdict(int)
        for node in self.graph:
            for neighbor in self.graph[node]:
                in_degree[neighbor] += 1
        
        # 将入度为0的节点加入队列
        queue = deque()
        for node in self.graph:
            if in_degree[node] == 0:
                queue.append(node)
        
        # 拓扑排序结果
        result = []
        
        # 开始拓扑排序
        while queue:
            node = queue.popleft()
            result.append(node)
            
            for neighbor in self.graph[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
                    
        return result

接下来，我们可以测试这个拓扑排序的实现。

g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(2, 4)
g.add_edge(3, 5)
g.add_edge(4, 5)
g.add_edge(4, 6)
g.add_edge(5, 6)

print(g.topological_sort())

运行结果将输出：[1, 2, 4, 3, 5, 6]，这就是根据拓扑排序算法得到的有向无环图的排序结果。

拓扑排序是一个常用的排序算法，在很多实际应用中都能发挥重要的作用。这个实现例子展示了如何在Python中使用图的拓扑排序算法。你可以将这个算法用在任务调度、依赖关系分析等场景中，为了更好地理解和应用拓扑排序算法，建议你尝试更多的例子和问题。