파이썬 토폴로지 정렬
이 튜토리얼은 Python에서 토폴로지 정렬 알고리즘의 구현을 보여줍니다.
Python의 토폴로지 정렬 알고리즘
토폴로지 정렬 알고리즘은 방향성 비순환 그래프(DAG)를 정렬합니다. 방향성 비순환 그래프(DAG)는 한 노드에서 다른 노드로 향하는 에지가 있지만 주기가 없는 그래프입니다.
토폴로지 정렬은 DAG를 입력으로 받아들이고 각 노드가 가리키는 노드 앞에 나타나는 배열을 반환하는 알고리즘입니다.
토폴로지 정렬은 노드 간 에지의 방향에 따라 순서가 완전히 달라지기 때문에 DAG 이외의 그래프에는 적용할 수 없으며 그래프 내부에 주기가 있으면 여러 배열이 있을 수 있습니다.
결과적으로 방향성 비순환 그래프의 노드의 위상적 정렬은 에지(i,j)가 존재하는 경우 i가 j보다 먼저 오도록 노드를 배열하는 작업이라고 말할 수 있습니다. 목록에 있습니다.
토폴로지 정렬은 본질적으로 작업을 수행해야 하는 순서를 제공하고 그래프에 주기가 있는지 여부를 결정하는 데 도움이 됩니다.
모든 그래프는 둘 이상의 토폴로지 순서를 지원할 수 있습니다. 그래프에서 노드의 진입차수가 이를 결정합니다.
또한 네트워크의 토폴로지 순서는 진입차수가 0인 노드, 즉 들어오는 에지가 없는 노드에서 시작합니다.
토폴로지 정렬에서 일어나는 일을 더 잘 이해하기 위해 예를 살펴보겠습니다.
입력 DAG:
첫 번째 반복: []
두 번째 반복: [B]
세 번째 반복: [B, E]
네 번째 반복: [B, E, A]
다섯 번째 반복: [B, E, A, F]
최종 출력: [B, E, A, F, C, D]
위의 예에서는 그래프에서 입력 가장자리가 없는 노드를 반복적으로 제거하고 배열에 넣습니다. 그래프에 노드가 하나만 남을 때까지 이 프로세스를 반복합니다.
결국 이 최종 노드를 배열 끝에 추가합니다.
Python에서 토폴로지 정렬 알고리즘 구현
위에서 설명한 것과 동일한 논리를 구현하여 Python에서 토폴로지 정렬 프로그램을 만들 수 있습니다. 코드에서 이 알고리즘을 구현하는 단계는 다음과 같습니다.
- 들어오는 에지가 없는 노드를 식별합니다.
- 그래프에서 이 노드와 해당 에지를 삭제합니다.
- 인접 노드의 진입 차수를 업데이트합니다.
- 그래프가 비워질 때까지 1~3단계를 반복합니다.
이 4단계에서 토폴로지 정렬을 위한 그래프를 만들어야 한다는 것이 분명합니다. 여러 가지 방법으로 수행할 수 있지만 가장 편리한 방법은 노드와 에지를 그래프에 삽입하는 메서드가 포함된 그래프 클래스를 만드는 것입니다.
다음 코드 스니펫은 생성자와 그래프에 가장자리를 더 추가하는 메서드가 있는 graph 클래스를 보여줍니다.
from collections import defaultdict
class Graph:
def __init__(self, directed=False):
self.graph = defaultdict(list)
self.directed = directed
def addEdge(self, frm, to):
self.graph[frm].append(to)
if self.directed is False:
self.graph[to].append(frm)
else:
self.graph[to] = self.graph[to]
이제 유방향 또는 무방향 그래프를 초기화할 수 있는 graph라는 클래스와 그래프에 더 많은 가장자리를 추가하는 데 사용할 수 있는 addEdge() 메서드가 있습니다.
지금 필요한 것은 토폴로지 정렬 알고리즘을 구현하는 메커니즘입니다. 우리는 노드를 방문하고 들어오는 에지가 없는지 확인하고 들어오는 에지가 없으면 해당 노드를 삭제하는 함수를 만들어야 합니다.
이 유형의 함수는 다음 코드 스니펫에 표시됩니다.
def visitNode(self, s, visited, sortlist):
visited[s] = True
for i in self.graph[s]:
if not visited[i]:
self.visitNode(i, visited, sortlist)
sortlist.insert(0, s)
위 함수는 현재 노드 s의 인덱스를 사용합니다. 노드가 이미 방문했는지 여부에 대한 정보를 포함하는 부울 목록 visited 및 그래프에서 삭제된 노드를 저장하는 데 사용할 sortlist.
그래프의 모든 노드에 대해 이 visitNode()를 점진적으로 호출하고 마지막에 정렬된 목록의 값을 인쇄하는 또 다른 도우미 함수를 만들어야 합니다. 다음 코드 스니펫은 Python에서 구현된 유사한 함수를 보여줍니다.
def topologicalSort(self):
visited = {i: False for i in self.graph}
sortlist = []
for v in self.graph:
if not visited[v]:
self.visitNode(v, visited, sortlist)
print(sortlist)
이제 graph 클래스의 구현이 완료되었습니다. 이제 그래프를 만들고 topologicalSort() 함수를 호출하여 목록을 정렬해야 합니다.
이 프로세스는 다음 코드로 구현되었습니다.
if __name__ == "__main__":
graph = Graph(directed=True)
graph.addEdge(1, 6)
graph.addEdge(1, 3)
graph.addEdge(2, 1)
graph.addEdge(2, 5)
graph.addEdge(3, 4)
graph.addEdge(5, 1)
graph.addEdge(5, 6)
graph.addEdge(5, 6)
graph.addEdge(6, 3)
graph.addEdge(6, 4)
print("Topological Sort Algorithm:")
graph.topologicalSort()
출력:
Topological Sort Algorithm:
[2, 5, 1, 6, 3, 4] #[B, E, A, F, C, D] in terms of previous example
이 코드에서 생성한 그래프는 위에 제공된 다이어그램의 다이어그램에 해당합니다. 여기에서 인덱스 1에서 6은 노드 A에서 F를 나타냅니다.
본 것처럼 최종 정렬 목록은 [B, E, A, F, C, D]였으며 코드의 출력과 동일합니다.
이제 하나의 코드 블록에 결합된 위의 코드를 살펴보겠습니다.
from collections import defaultdict
class Graph:
def __init__(self, directed=False):
self.graph = defaultdict(list)
self.directed = directed
def addEdge(self, frm, to):
self.graph[frm].append(to)
if self.directed is False:
self.graph[to].append(frm)
else:
self.graph[to] = self.graph[to]
def visitNode(self, s, visited, sortlist):
visited[s] = True
for i in self.graph[s]:
if not visited[i]:
self.visitNode(i, visited, sortlist)
sortlist.insert(0, s)
def topologicalSort(self):
visited = {i: False for i in self.graph}
sortlist = []
for v in self.graph:
if not visited[v]:
self.visitNode(v, visited, sortlist)
print(sortlist)
if __name__ == "__main__":
graph = Graph(directed=True)
graph.addEdge(1, 6)
graph.addEdge(1, 3)
graph.addEdge(2, 1)
graph.addEdge(2, 5)
graph.addEdge(3, 4)
graph.addEdge(5, 1)
graph.addEdge(5, 6)
graph.addEdge(5, 6)
graph.addEdge(6, 3)
graph.addEdge(6, 4)
print("Topological Sort Algorithm:")
graph.topologicalSort()
출력:
Topological Sort Algorithm:
[2, 5, 1, 6, 3, 4] #[B, E, A, F, C, D] in terms of previous example
이것으로 튜토리얼을 마칩니다. 이제 작동 방식을 완전히 이해하고 토폴로지 정렬을 구현할 수 있습니다.
Maisam is a highly skilled and motivated Data Scientist. He has over 4 years of experience with Python programming language. He loves solving complex problems and sharing his results on the internet.
LinkedIn