Python 实现拓扑排序算法:深度优先搜索(DFS)示例
当您在已经实现的有向图类上添加一个名为'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)。
希望这能满足您的需求!如果您还有其他问题,请随时提问。
原文地址: https://www.cveoy.top/t/topic/YU0 著作权归作者所有。请勿转载和采集!