위상정렬

지시된 비순환 그래프(DAG)의 위상 정렬은 순서가 정해진 모든 모서리 u, v에 대해 정점 u가 순서에서 v보다 먼저 오는 정점의 선형 순서이다.

• 그래프가 DAG가 아닌 경우 그래프의 위상 정렬은 불가능합니다

위상 분류 알고리즘

전제 조건: DFS

DFS에서 다음과 같이 작동합니다:

1.정점에서 시작하여 해당 정점을 먼저 출력
2. 인접한 정점에 대해 DFS를 재귀적으로 호출

그러나 위상 분류 알고리즘에서는 아래와 같은 수정 된 접근 방법을 사용합니다:

1. 임시 스택을 사용
2. 정점을 즉시 출력
3. 먼저 인접한 모든 정점에 대해 재귀적으로 위상 정렬 함수를 호출한 후 스택에 해당 정점을 밀어넣습니다.
4. 스택의 내용을 출력

from collections import defaultdict

class Graph:
	def __init__(self, vertices):
		self.graph = defaultdict(list) # 딕셔너리에 인접한 list를 담는다.
		self.V = vertices # 정점의 no

	# 그래프에 edge를 추가
	def addEdge(self, u, v):
		self.graph[u].append(v)

	def topologicalSortUtil(self, v, visited, stack):
		visited[v] = 1

        # 모든 정점에 인접한 정점들을 재귀로 호출
		for i in self.graph[v]:
			if visited[i] == 0:
				self.topologicalSortUtil(i, visited, stack)

        # 현재 정점을 결과를 담는 stack에 push
		stack.append(v)

	def topologicalSort(self):
		visited = [0] * self.V
		stack = []

		# 각 정점에서 하나씩 시작하여 정렬하기
		for i in range(self.V):
			if visited[i] == 0:
				self.topologicalSortUtil(i, visited, stack)

		print(stack[::-1]) 


# Driver Code
if __name__ == '__main__':
	g = Graph(6)
	g.addEdge(5, 2)
	g.addEdge(5, 0)
	g.addEdge(4, 0)
	g.addEdge(4, 1)
	g.addEdge(2, 3)
	g.addEdge(3, 1)

	print("F주어진 그래프의 위상 정렬 결과는 다음과 같습니다.")

	g.topologicalSort()