How to implement topological sorting algorithm using Python?

How to implement topological sorting algorithm using Python?

Topological sorting is a sorting algorithm in graph theory, used to sort directed acyclic graphs (DAG). In topological sorting, nodes in the graph represent tasks or events, and directed edges represent dependencies between tasks or events. In the sorted result, all dependencies are satisfied and each node is ranked after all its predecessor nodes.

Implementing the topological sorting algorithm in Python can be solved using the idea of ​​depth-first search (DFS). The following is a specific code example:

from collections import defaultdict

class Graph:
    def __init__(self, num_vertices):
        self.graph = defaultdict(list)
        self.num_vertices = num_vertices

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def topological_sort_util(self, v, visited, stack):
        visited[v] = True

        for i in self.graph[v]:
            if visited[i] == False:
                self.topological_sort_util(i, visited, stack)

        stack.append(v)

    def topological_sort(self):
        visited = [False] * self.num_vertices
        stack = []

        for i in range(self.num_vertices):
            if visited[i] == False:
                self.topological_sort_util(i, visited, stack)

        sorted_list = []
        while stack:
            sorted_list.append(stack.pop())

        return sorted_list

# 测试代码
g = Graph(6)
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)

sorted_list = g.topological_sort()
print("拓扑排序结果：", sorted_list)

The above code first defines a Graph class, which includes methods such as adding edges and topological sorting. During topological sorting, a depth-first search is used to traverse the nodes in the graph. By using a stack to store the nodes that have been visited, you can finally get a list of nodes arranged according to topological ordering rules.

The above code also contains a simple test case to verify the correctness of the topological sorting algorithm. In this test case, a graph of size 6 is defined and some nodes and edges are added. Finally, print out the topologically sorted node list.

Using Python to implement the topological sorting algorithm can easily handle dependencies in the graph, which is very helpful for issues such as task scheduling. By understanding and applying this algorithm, practical problems can be better solved. Hope this article is helpful to you.

The above is the detailed content of How to implement topological sorting algorithm using Python?. For more information, please follow other related articles on the PHP Chinese website!