6주차 알고리즘스터디 - 위상정렬(topology sort )

1) 위상정렬의 개념 

갓키백과에 따르면  유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것이라고 한다. 

방향이 있는 그래프에서 그 방향을 따라가며 즉 선후 관계를 지키며 모든 정점을 정렬하는 것이라고 생각한다. 

선후관계 즉 순서가 있어야한다. 그래서 사이클이 존재하면 위상정렬을 사용할 수 없다.

이런 걸 DAG : 사이클이 존재하지 않는 방향 그래프 라고 한다. 

 

고등학교 수학을 수1 > 수2 > 미적1 > 미적2 인걸 예로 들 수 있겠다.

 

2) 위상정렬 원리

스터디장님이 설명해주시는데 진입차수가 대체 뭔지 이해가 안갔다,,,, 내 머리,,,, 

진입차수 : 특정 정점과 연결되어있는 선행되어야 하는 정점들 

 

1. 진입차수가 0인 정점을 큐에 넣는다.
   
   여러 개인 경우 상관없다. 넣고싶은대로 혹은 문제의 조건대로 넣자. 

2. 큐에서 원소를 꺼내어 해당 정점에서 출발하는 간선을 삭제한다.

3. 새롭게 진입차수가 0인 노드를 큐에 넣는다. 

4. 2~3번 과정을 큐가 빌때까지 계속해서 반복한다. 

 

 

만약 모든 원소를 방문하기 전 큐가 빈다면 ? 사이클이 존재한다는 얘기다. 

 

 

 

사이클이 존재한다면 ? 

진입차수가 0인 수가 존재하지 않아 큐가 비게 된다. 

 

3) 시간복잡도 : O( V+E )

정점개수 + 간선개수로 무척 빠른 알고리즘이다.

4)코드 구현 c++

• 위상정렬의 원리에 써있는 1~3을 그대로 따라서 구현하면 된다. 
• 백준 2252번 줄세우기 ( www.acmicpc.net/problem/2252 )를 예제로 풀었다

 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
vector<vector<int>> graph;
vector<int>degree;
vector<int>result;
queue<int>que;

int n, m;
void topology_sort() {
    // 1. 맨 처음 진입차수가 0인 녀석들을 큐에 넣어준다. 
    for (int i = 1; i <= n; i++) {
        if (!degree[i]) que.push(i);
    }
    // 2~3을 큐가 빌 때가지 반복한다. 
    while (!que.empty()) {
    // 2. 큐의 front를 pop한 후 해당 정점에 연결되어있는 간선 삭제
        int num = que.front(); 
        que.pop(); 
        for (int i = 0; i < graph[num].size(); i++) {
            //해당 정점에 연결되어있다면 해당 정점의 graph 배열에 저장되어있음. 그에 해당하는 degree 1씩 감소
            degree[graph[num][i]]--;
            //3. 새로운 진입차수가 0이라면 큐에 넣어줌
            if (!degree[graph[num][i]]) que.push(graph[num][i]);
        }
        result.push_back(num);
    }
}

int main() {
    cin >> n >> m;
    degree.resize(n + 1);
    graph.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        //문제에 학생 A가 학생 B의 앞에 서야한다고 써있다. 즉 A가 선행되어야함 
        graph[a].push_back(b);
        degree[b] +=1;
    }
    topology_sort();
    for (int i = 0; i < result.size(); i++) cout << result[i] <<" " ;
}