위상정렬 (Topological Sort)

위상정렬은 주어진 유향 그래프를 일정한 순서로 배치하였을때, 모든 간선이 오른쪽으로만 향하도록 하는 배치를 의미한다.

위상정렬을 하기 위해선 주어진 그래프에 사이클이 없음, 즉 DAG 여야 함이 보장되어야 한다.

위상정렬을 하는 방법은 크게 2가지 방법이 있다.

 

SOL 1)

위상정렬에서 가장 먼저 오는 점은 indegree의 값이 무조건 0이라는 관찰을 해주면 된다.

각 정점에서의 indegree 값을 갖고 있고, indegree가 0인 정점을 큐에 넣어준 후, 그 정점과 연결된 간선들을 삭제해주는 과정을 반복하면 된다. 

간선을 삭제하는 방법은 단순히 도착 정점의 indegree 를 감소시키면 된다.

 

만약 큐에 값이 2개 이상 들어가는 시간이 있으면, 위상정렬의 결과가 2개이상 가능한 것이고, 

큐에 값이 없으면 위상정렬이 불가능 ( 사이클이 존재한다 )는 것이다.

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 32000;

int n, m;
vector<int> adj[MAXN+10], ans;
int indeg[MAXN+10];

int main()
{
    int i, j;

    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        indeg[v]++;
    }

    queue<int> Q;
    for(i=1; i<=n; i++) if(indeg[i]==0) Q.push(i);
    while(!Q.empty())
    {
        int now=Q.front(); Q.pop();
        ans.push_back(now);
        for(int nxt : adj[now])
        {
            indeg[nxt]--;
            if(indeg[nxt]==0) Q.push(nxt);
        }
    }
    for(int it : ans) printf("%d ", it);
}

 

SOL 2)

두번째 방법은 바로 DFS를 이용하는 것이다.

u에서 시작하는 DFS는 u에서 직, 간접적으로 방문할 수 있는 방문할 수 있는 모든 정점들을 방문한다.

따라서, 위상 정렬 순서는 dfs 종료 역순이다.

엄밀한 증명은 귀류법을 사용하여 남은 간선이 트리 간선일때, 순방향 간선일 때, 교차 간선일 때 각각 고려해주면 된다.

 

Let's assume that the graph is acyclic, i.e. there is a solution. What does the depth-first search do? When started from some vertex vv, it tries to run along all edges outgoing from vv. It fails to run along the edges for which the opposite ends have been visited previously, and runs along the rest of the edges and starts from their ends.

Thus, by the time of the call dfs(v) is ended, all vertices that are reachable from either directly (via one edge) or indirectly are already visited by the search. Therefore, if at the time of exit from dfs(v) we add vertex vv to the beginning of a certain list, in the end this list will store a topological ordering of all vertices.

These explanations can also be presented in terms of time of exit from DFS routine. Exit time for vertex vv is the time at which dfs(v)finished work (the times can be numbered from 11 to nn). It is easy to understand that exit time of any vertex v is always greater than exit time of any vertex reachable from it (since they were visited either before the call dfs(v) or during it). Thus, the desired topological ordering is sorting vertices in descending order of their exit times.

 

결론은 dfs를 돌면서 함수가 종료할때 답에 추가해 주고, 마지막에 뒤집어 주면 된다.

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 32000;

int n, m;
vector<int> adj[MAXN+10], ans;

bool vis[MAXN+10];
void dfs(int now)
{
    vis[now]=true;
    for(int nxt : adj[now]) if(!vis[nxt]) dfs(nxt);
    ans.push_back(now);
}

int main()
{
    int i, j;

    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
    }

    for(i=1; i<=n; i++) if(!vis[i]) dfs(i);
    reverse(ans.begin(), ans.end());
    for(int it : ans) printf("%d ", it);
}