22.4 Topological Sort

Directed acyclic graph

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

책안의 구조

DFS 사용 Cormen et al. (2001); Tarjan (1976)이 제안

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
std::stack<int> topologicalsort(const Graph& G)
{
    const int n = G.size();
    std::vector<bool> visit(n, false);
    stack<int> S; // 실제 정렬된값이 역순으로 들어가있다.
    for (std::size_t i = 1; i < n; i++)
    {
        if (visit[i] != true)
        {
            DFS_TS(G, visit, S, i);
        }
    }
    return S;
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//recursion
void DFS_TS(const Graph& G, std::vector<bool>& visit,
    stack<int>& S, int x)
{
    visit[x] = true;
    //std::cout << x << ' '; // 순회출력
    for(int next : G[x])
    {
        if (visit[next] != true)
        {
            DFS_TS(G, visit, S, next);
        }
    }
    S.push(x);
}

//for with stack
void DFS_TS(Graph& G, std::vector<bool>& visit,
    stack<int>& S, int x)
{
    visit[x] = true;

    std::stack<int> sub_s;
    sub_s.push(x);

    //std::cout << sub_s.top() << ' '; // 순회출력

    while (!sub_s.empty())
    {
        int y = sub_s.top();
        for (std::size_t i = 0; i < G[y].size(); i++)
        {
            int next = G[y][i];
            if (visit[next] != true)
            {
                visit[next] = true;
                sub_s.push(next);
                //std::cout << sub_s.top() << ' '; // 순회출력
                i = -1;
                y = sub_s.top();
            }

        }
        S.push(sub_s.top());
        sub_s.pop();
    }
}
함수 스택이 가장 빠르다.

기존 DFS와 차이는 마지막 sub_s.pop()하기전에 값을 S에 넣는 것이다.

해당 알고리즘의 개선은 다음의 코드들을 참고.

https://www.acmicpc.net/source/14181460

https://www.acmicpc.net/source/14181554

https://www.acmicpc.net/source/14181784

재귀 https://www.acmicpc.net/source/14192056

반복 https://www.acmicpc.net/source/14193108

Kahn's algorithm

참고 : https://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221236874984&proxyReferer=https%3A%2F%2Fwww.google.com%2F

https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
std::vector<int> topologicalsort(const Graph &G, int v)
{
    std::vector<int> indegree(v + 1);
    std::queue<int> qu;
    std::vector<int > DAG;
    for (int i = 1; i <= v; i++)
    {
        for(int j : G[i])
        {
            indegree[j]++;
        }
    }

    for (int i = 1; i <= v; i++)
    {
        if (indegree[i] == 0)
        {
            qu.push(i);
        }
    }
    for (int i = 1; i <= v; i++)
    {
        if (qu.empty())
        {
            return DAG;
        }
        int x = qu.front();
        qu.pop();
        DAG.push_back(x);

        for(int y : G[x])
        {
            indegree[y]--;
            if (indegree[y] == 0)
            {
                qu.push(y);
            }
        }
    }
    return DAG;
}