자료구조 - 위상 정렬

[위상 정렬(Topological Sort)]

방향성 비순환 그래프(DAG: Directed Acyclic Graph)의 정점을 순서대로 나열하는 알고리즘입니다.

상 정렬은 그래프의 각 간선 (u, v)에 대해 정점 u가 v보다 먼저 나오는 순서를 찾습니다.

 

 

위상 정렬은 DFS 기반의 방법과 Kahn's Algorithm 방법이 있습니다.

 

위상 정렬의 의사코드(Kahn's Algorithm)

1. 초기화:
   • 각 정점의 진입 차수를 계산하여 배열에 저장합니다.
   • 진입 차수가 0인 모든 정점을 큐에 넣습니다.
2. 큐 처리:
   • 큐에서 정점을 하나씩 꺼내서 결과 리스트에 추가합니다.
   • 꺼낸 정점의 모든 인접 정점의 진입 차수를 1씩 감소시킵니다.
   • 감소된 진입 차수가 0이 된 정점을 큐에 추가합니다.
3. 사이클 검출:
   • 결과 리스트의 길이가 정점의 총 개수와 같지 않으면 사이클이 존재한다고 판단합다.

함수 topologicalSort(graph):
    in_degree = [0] * 정점의 수(graph)
    for 각 정점 u in graph:
        for 각 정점 v in 인접 리스트(u):
            in_degree[v] += 1  // 진입 차수 계산

    queue = []
    for 각 정점 u in graph:
        if in_degree[u] == 0:
            queue에 u 추가  // 초기 큐 설정

    top_order = []
    while queue가 비어있지 않으면:
        u = queue에서 꺼냄
        top_order에 u 추가
        for 각 정점 v in 인접 리스트(u):
            in_degree[v] -= 1  // 진입 차수 감소
            if in_degree[v] == 0:
                queue에 v 추가

    if top_order의 길이 != 정점의 수(graph):
        오류 "그래프에 사이클이 존재합니다."

    반환 top_order

 

위상 정렬의 예시 코드(Khan's Algorithm)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 위상 정렬 함수를 정의
vector<int> topologicalSort(int V, vector<vector<int>>& adj)
{
    vector<int> in_degree(V, 0);  // 각 정점의 진입 차수를 저장할 벡터

    // 각 정점의 진입 차수를 계산
    for (int u = 0; u < V; u++) 
    {
        for (int v : adj[u]) 
        {
            in_degree[v]++;  // 인접 리스트를 통해 각 정점의 진입 차수를 증가
        }
    }

    queue<int> q;
    // 진입 차수가 0인 모든 정점을 큐에 삽입
    for (int i = 0; i < V; i++) 
    {
        if (in_degree[i] == 0) 
        {
            q.push(i);
        }
    }

    vector<int> top_order;
    // 큐에서 정점을 하나씩 꺼내어 결과 리스트에 추가
    while (!q.empty()) 
    {
        int u = q.front();
        q.pop();
        top_order.push_back(u);

        // 해당 정점의 인접한 정점들의 진입 차수를 감소시키고, 새로 진입 차수가 0이 된 정점을 큐에 삽입
        for (int v : adj[u]) 
        {
            if (--in_degree[v] == 0) 
            {
                q.push(v);
            }
        }
    }

    // 만약 정렬된 정점의 수가 V와 다르면 사이클이 존재
    if (top_order.size() != V) 
    {
        throw runtime_error("그래프에 사이클이 존재합니다.");
    }

    return top_order;  // 위상 정렬된 결과 반환
}

int main() 
{
    int V = 6;  // 정점의 수
    vector<vector<int>> adj(V);

    // 간선 추가 (예시: 유방향 그래프)
    adj[5].push_back(2);
    adj[5].push_back(0);
    adj[4].push_back(0);
    adj[4].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(1);

    try 
    {
        vector<int> result = topologicalSort(V, adj);
        cout << "위상 정렬 결과: ";
        for (int v : result) 
        {
            cout << v << " ";
        }
        cout << endl;
    } 
    catch (const runtime_error& e) 
    {
        cout << e.what() << endl;
    }

    return 0;
}

 

 

 

 

 

위상 정렬의 의사코드(DFS)

1. 초기화:
   • 모든 정점을 방문하지 않은 상태로 표시합니다.
   • 빈 스택을 하나 준비합니다.
2. DFS 수행:
   • 방문하지 않은 정점에서 DFS를 시작합니다.
   • DFS 방문 중, 방문을 완료한 정점을 스택에 삽입합니다.
3. 결과 출력:
   • 스택에 저장된 정점들을 꺼내면 위상 정렬의 결과가 됩니다.

function topologicalSort(graph):
    visited = [false] * number_of_vertices(graph)
    stack = []

    function dfs(u):
        visited[u] = true
        for each vertex v in neighbors(u):
            if not visited[v]:
                dfs(v)
        push(stack, u)

    for each vertex u in graph:
        if not visited[u]:
            dfs(u)

    top_order = []
    while not is_empty(stack):
        append(top_order, pop(stack))
    
    return top_order

 

 

 

위상 정렬의 예시 코드(DFS)

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfs(int u, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& Stack)
{
    visited[u] = true;  // 현재 정점을 방문 표시

    // 인접한 모든 정점을 탐색
    for (int v : adj[u]) 
    {
        if (!visited[v]) 
        {
            dfs(v, adj, visited, Stack);  // 방문하지 않은 정점에 대해 DFS 수행
        }
    }
    Stack.push(u);  // 모든 인접 정점을 방문한 후에 스택에 현재 정점을 삽입
}

// 위상 정렬 함수
vector<int> topologicalSort(int V, vector<vector<int>>& adj)
{
    vector<bool> visited(V, false);  // 모든 정점을 방문하지 않은 상태로 초기화
    stack<int> Stack;  // 정점을 저장할 스택

    // 모든 정점에 대해 DFS 수행
    for (int i = 0; i < V; i++) 
    {
        if (!visited[i]) 
        {
            dfs(i, adj, visited, Stack);
        }
    }

    vector<int> top_order;
    // 스택에서 정점을 꺼내어 위상 정렬 순서로 저장
    while (!Stack.empty()) 
    {
        top_order.push_back(Stack.top());
        Stack.pop();
    }

    return top_order;  // 위상 정렬된 결과 반환
}

int main() 
{
    int V = 6;  // 정점의 수
    vector<vector<int>> adj(V);

    // 간선 추가 (예시: 유방향 그래프)
    adj[5].push_back(2);
    adj[5].push_back(0);
    adj[4].push_back(0);
    adj[4].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(1);

    vector<int> result = topologicalSort(V, adj);
    cout << "위상 정렬 결과: ";
    for (int v : result) 
    {
        cout << v << " ";
    }
    cout << endl;

    return 0;
}