위상정렬(Topology Sort)

📖 정의

 

- 방향성을 거스르지 않고 유향 그래프의 정점을 나열하는 방법

- 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를  위해 사용하는 알고리즘

- 여러 개의 답이 존재할 수 있다.

 

📌 조건

 

- DAG(Directed Acyclic Graph)에만 적용 가능

- 사이클이 발생하는 경우 시작점이 불분명하므로 위상 정렬 불가

 

📌 구현 방법

 

1) Stack / DFS 이용

2) Queue 이용

• 진입 차수가 0인 정점을 queue에 삽입
• queue에서 원소를 꺼내 연결된 모든 간선 제거
• 간선 제거 후 다시 1부터 반복
• Point!
  
  • 모든 정점을 방문했다면 queue에서 꺼낸 순서가 위상 정렬의 결과
  • 모든 정점을 방문하기 전에 queue가 비면 사이클이 존재 -> 위상 정렬 불가
• 수행시간 O(V+E)

📌 예시 코드

static void topologicalSort(int[] indegree, List<List<Integer>> array) {
		Queue<Integer> q = new LinkedList<Integer>();
		Queue<Integer> result = new LinkedList<>(Integer);

		// 큐에 indegree가 0인 노드 담기
		for(int i=1; i<n+1; i++) {
			if(indegree[i] == 0) q.offer(i);
		}

		/*
		* 1. 큐에서 값을 꺼내며 해당 노드가 가리키는 노드의 indegree를 1 감소(간선 제거)
		* 2. 만약 indegree가 0이 된다면 큐에 넣기
		* 3. 큐가 빌 때까지 반복
		 */
		
		while(!q.isEmpty()) {
			int node = q.poll();
			result.offer(node) ;
			
			for(Integer i : array.get(node)) {
				indegree[i]--;
				
				if(indegree[i] == 0) q.offer(i);
			}
		}
		
		System.out.println(result);
	}

jason9319.tistory.com/93