当您在已经实现的有向图类上添加一个名为'topological_sort'的方法,可以用于执行拓扑排序算法。以下是一个使用深度优先搜索(DFS)算法实现拓扑排序的示例代码:

class DirectedGraph:
    def __init__(self):
        self.graph = {}
        self.topological_order = []

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, start_vertex, end_vertex):
        if start_vertex in self.graph:
            self.graph[start_vertex].append(end_vertex)
        else:
            print("Start vertex doesn't exist in the graph.")

    def get_neighbors(self, vertex):
        if vertex in self.graph:
            return self.graph[vertex]
        else:
            print("Vertex doesn't exist in the graph.")

    def topological_sort(self):
        visited = set()

        def dfs(vertex):
            visited.add(vertex)
            neighbors = self.get_neighbors(vertex)
            if neighbors:
                for neighbor in neighbors:
                    if neighbor not in visited:
                        dfs(neighbor)
            self.topological_order.append(vertex)

        for vertex in self.graph:
            if vertex not in visited:
                dfs(vertex)

        self.topological_order.reverse()
        for index, vertex in enumerate(self.topological_order):
            print(f"Vertex: {vertex}, Topological Order: {index + 1}")

    def __str__(self):
        return str(self.graph)

在这个实现中,'topological_sort'方法使用了深度优先搜索(DFS)算法来进行拓扑排序。在DFS过程中,我们首先访问图中的每个顶点,如果当前顶点未被访问过,则调用递归的DFS函数进行深度搜索。在递归的DFS函数中,我们访问当前顶点的所有邻居顶点,并对未访问过的邻居进行递归调用。当我们完成对邻居顶点的访问后,将当前顶点添加到'self.topological_order'列表中。

最后,我们对'self.topological_order'列表进行反转,以得到拓扑排序的顺序。然后,我们遍历该列表,并打印每个顶点及其拓扑顺序赋值。

以下是使用示例:

# 创建一个有向图实例
graph = DirectedGraph()

# 添加顶点
graph.add_vertex("A")
graph.add_vertex("B")
graph.add_vertex("C")
graph.add_vertex("D")
graph.add_vertex("E")

# 添加边
graph.add_edge("A", "C")
graph.add_edge("B", "C")
graph.add_edge("B", "D")
graph.add_edge("C", "D")
graph.add_edge("D", "E")

# 执行拓扑排序
graph.topological_sort()

输出结果应该类似于:

Vertex: A, Topological Order: 3
Vertex: B, Topological Order: 2
Vertex: C, Topological Order: 1
Vertex: D, Topological Order: 4
Vertex: E, Topological Order: 5

这表明顶点C是第一个处理的顶点(拓扑顺序为1),顶点E是最后一个处理的顶点(拓扑顺序为5)。

希望这能满足您的需求!如果您还有其他问题,请随时提问。

Python 实现拓扑排序算法:深度优先搜索(DFS)示例

原文地址: https://www.cveoy.top/t/topic/YU0 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录