[알고리즘/그래프] 위상 정렬

위상 정렬

Directed Acyclic Graph(DAG, 비순환 방향 그래프)에서 정점들을 순서대로 나열하는 알고리즘

 

 

위상 정렬의 기본 개념

진입 차수: 특정 노드로 들어오는 간선의 수

위상 정렬의 조건: DAG에서만 가능, 만약 사이클이 있다면 위상 정렬 불가

 

순서

1. 그래프의 각 정점에 대해 진입 차수를 계산합니다.
2. 진입 차수가 0인 정점들을 큐에 넣습니다.
3. 큐에서 정점을 하나씩 꺼내며 그 정점과 연결된 다른 정점들의 진입 차수를 감소시킵니다.
4. 진입 차수가 0이 된 정점은 다시 큐에 넣고, 큐가 비어지면 알고리즘을 종료합니다.

시간 복잡도

• O(V + E)
  • V: 정점 수
  • E: 간선 수

 

코드 (백준: 2252)

https://www.acmicpc.net/problem/2252

 

int main()
{
    static int N, M;
    std::cin >> N >> M;
    std::vector<std::vector<int>> edges(N+1);
    std::vector<int> indegree(N + 1);

    for (int i = 0; i < M; ++i) 
    {
        int start, end;
        std::cin >> start >> end;
        edges[start].push_back(end);
        indegree[end]++;
    }
    std::queue<int> queue;

    for (int i = 1; i <= N; ++i) 
    {
        if (indegree[i] == 0) 
        {
            queue.push(i);
        }
    }
    while (!queue.empty()) 
    {
        int now = queue.front();
        queue.pop();
        std::cout << now << " ";
        for (int next : edges[now]) 
        {
            indegree[next]--;
            if (indegree[next] == 0) 
            {
                queue.push(next);
            }
        }
    }
}