Python을 사용하여 위상 정렬 알고리즘을 구현하는 방법은 무엇입니까?

Python을 사용하여 위상 정렬 알고리즘을 구현하는 방법은 무엇입니까?

토폴로지 정렬은 방향성 비순환 그래프(DAG)를 정렬하는 데 사용되는 그래프 이론의 정렬 알고리즘입니다. 토폴로지 정렬에서 그래프의 노드는 작업 또는 이벤트를 나타내고 방향성 간선은 작업 또는 이벤트 간의 종속성을 나타냅니다. 정렬된 결과에서 모든 종속성이 충족되고 각 노드는 모든 이전 노드 이후에 순위가 지정됩니다.

Python에서 위상 정렬 알고리즘을 구현하는 것은 깊이 우선 탐색(DFS) 아이디어를 사용하여 해결할 수 있습니다. 다음은 구체적인 코드 예입니다.

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)

위 코드는 먼저 가장자리 추가 및 위상 정렬과 같은 메서드를 포함하는 Graph 클래스를 정의합니다. 위상 정렬 중에는 그래프의 노드를 탐색하기 위해 깊이 우선 검색이 사용됩니다. 스택을 사용하여 방문한 노드를 저장하면 최종적으로 토폴로지 순서 규칙에 따라 정렬된 노드 목록을 얻을 수 있습니다.

위 코드에는 위상 정렬 알고리즘의 정확성을 확인하기 위한 간단한 테스트 사례도 포함되어 있습니다. 이 테스트 사례에서는 크기 6의 그래프가 정의되고 일부 노드와 간선이 추가됩니다. 마지막으로 위상적으로 정렬된 노드 목록을 인쇄합니다.

Python을 사용하여 위상 정렬 알고리즘을 구현하면 그래프의 종속성을 쉽게 처리할 수 있어 작업 스케줄링과 같은 문제에 매우 유용합니다. 이 알고리즘을 이해하고 적용함으로써 실제 문제를 더 잘 해결할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 Python을 사용하여 위상 정렬 알고리즘을 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!