[2022 1학기] 9주차 - 위상정렬

1. 위상정렬(Topological Sort)이란?

방향 그래프에서 선후관계에 따라 적절한 순서를 찾는 알고리즘

전체 순서가 아닌 일부 순서가 주어진 경우 여러가지 경우로 줄을 세울 수 있다

 

-문제 유형

어떤 작업ㄷ르에 대한 순서가 주어졌을 때

자신보다 선행되어야 할 일을 다 끝내야 작업에 들어갈 수 있게 주어졌을 때

 

 

2. 동작 원리

방향은 존재하지만 사이클은 존재해선 안 된다. (순서를 명확히 정할 수 없기 때문)

 

-bfs 방식 위상정렬

indegree가 0인 노드를 큐에 넣어준다

큐의 front(현재 정점)을 방문한다

front()에 연결되어있는 다음 정점들을 방문하고 indegree[next]를 1씩 감소시킨다

감소시켰을 때 indegree가 0이라면 큐에 넣어준다

 

-dfs 방식 위상정렬

방문하지 않은 점점에서 dfs시작

탐색이 끝나면 그 정점을 스택(벡터)에 넣는다

탐색 종료 후 스택에 쌓은 것을 출력한 순서가 위상정렬

 

3. 코드

//BFS 방식 위상정렬

	while (M--) {
		int a, b;
		cin >> a >> b;

		adj[a].push_back(b);
		indegree[b]++;
	}


	queue<int> q;
	for (int i = 1; i <= N; i++) {
		if (!indegree[i]) { //indegree가 0인 정점 큐에 삽입
			q.push(i);
			ans.push_back(i);
		}
	}


	while (!q.empty()) {
		int now = q.front();
		q.pop();
		
		for (auto next : adj[now]) {
			indegree[next]--;

			if (indegree[next] == 0) {
				q.push(next);
				ans.push_back(next);
			}
		}
	}
    
     if (ans.size() != N) {
		printf("사이클 존재");
		return 0;
	}

    
//BFS 방식 위상정렬 사이클 찾기2
	for (int i = 0; i < N; i++) {
		if (q.empty()) {
			printf("사이클 존재");
			return 0;
		}

		int now = q.front();
		q.pop();

		for (auto next : adj[now]) {
			indegree[next]--;

			if (indegree[next] == 0) {
				q.push(next);
				ans.push_back(next);
			}
		}
	}

//DFS 방식 위상정렬

stack<int> s;
int visited[32001]; //0: 미방문, 1: 방문중, 2: 방문완료
vector<int> adj[32001];

void dfs(int now) {
	visited[now] = 1;

	for (auto next : adj[now]) {
		if (visited[next] == 0) {
			dfs(next);
		}
		else if (visited[next] == 1) {
			printf("사이클 존재");
			return;
		}
	}

	visited[now] = 2;
	s.push(now);
}

int main() {

	cin >> N >> M;


	while (M--) {
		int a, b;
		cin >> a >> b;

		adj[a].push_back(b);
	}

	for (int i = 0; i < N; i++) {
		if (!visited[i]) {
			dfs(i);
		}
	}

	while (s.size()) {
		printf("%d ", s.top());
	}

}

 

※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!