위상 정렬(Topological Sorting)

• 그래프 순서 정렬
  • 모든 정점을 일렬로 나열하되, 정점 x에서 정점 y로 가는 간선이 있으면 x는 반드시 y보다 앞에 위치한다.
  • 일반적으로 임의의 유향 그래프에 대해 복수의 위상순서가 존재한다.
• 조건 : 방향성이 있으나 사이클은 없는 그래프 : DAG(Directed Qcyclic Graph) 여야 함
  • A -> B : O
  • A -> B, B -> A : X
• 구현 방법
  • DFS
  • indegree 배열
• 시간 복잡도 : O(V + E)
  • 정점의 개수 + 간선의 개수만큼 소요됨

1) indegree 배열

변수	용도
List<List> array	그래프의 관계를 표현하는 2차원 인접 리스트
int[] indegree	해당 노드는 가리키고 있는 간선의 개수를 담음
Queue visit	indegree가 0이 된 노드들을 담기 위한 배열

• indegree가 0인 노드 부터 방문
  • = 자신을 가르키는 노드(간선)이 없어졌기 때문에
  • = 선행 노드 이미 방문 완료했다는 의미

int N = 10;	// 노드의 개수
int M = 7; // 관계의 개수

// 해당 노드를 가르키는 간선의 개수 담음
int[] indegree = new int[N + 1];

// 그래프의 관계를 나타냄
ArrayList<ArrayList<Integer>> nodes = new ArrayList<ArrayList<Integer>>();

// 방문 순서
Queue<Integer> visit = new LinkedList<Integer>();

// 그래프 초기화
for (int i = 0; i < N + 1; i++) {
	nodes.add(new ArrayList<Integer>());
}

for (int i = 0; i < M; i++) {
	int[] info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

	nodes.get(info[0]).add(info[1]);
	indegree[info[1]] += 1;
}


// 선행 노드가 없는 노드부터 차례대로 방문하려 담음
for (int i = 1; i < N + 1; i++) {
	if (indegree[i] == 0) {
		ques.add(i);
	}
}

while (!ques.isEmpty()) {
	int before = ques.poll();

	for (int after : nodes.get(before)) {
    // 간선의 개수 감소시켜줌
		indegree[after]--;

		if (indegree[after] == 0) {
			ques.add(after);
		}
	}
}

2) DFS

변수	용도
List<List> array	그래프의 관계를 표현하는 2차원 인접 리스트
boolean[] visited	노드 방문 체크 여부
ArrayList sorted	위상 정렬 노드 저장 알고리즘 끝나면 연결 리스트에 노드들이 위상정렬된 순서로 들어있음

public void topologicalSort() {
  for (int i = 0; i < array.length; i++) {
    // 방문하지 않은 노드에 대한 DFS
    if (!visited[i]) {
      dfs(i);
    }
  }
}

public void DFS(int start) {
  // 방문 여부 체크
  visited[start] = true;
  
  // 현재 노드와 인접해있는 노드 탐색하여 DFS
  for (int end : array.get(start)) {
    if (!visited[end]) {
      DFS(end);
    }
  }
  
  // 연결 리스트의 맨 앞에 노드 삽입
  // 한 노드에서 재귀가 다 끝나야지만 추가 가능
  sorted.add(start);
}