TIL - Tarjan의 알고리즘

일부 경쟁 프로그래밍을 연습하는 동안 그래프 이론 - 강력하게 연결된 구성 요소(SCC)의 흥미로운 하위 섹션을 발견했습니다.

유향 그래프에서 강하게 연결된 구성 요소는 SCC의 각 노드가 SCC의 다른 모든 노드에 대한 경로를 가질 수 있도록 에지가 있는 노드입니다. 이러한 SCC를 찾는 데 도움이 되도록 Tarjan의 알고리즘이라는 것을 사용할 수 있습니다!

Tarjan의 알고리즘은 하나의 DFS 패스 O(V+E) 시간과 스택 O(V) 공간만을 사용하여 유향 그래프에서 SCC를 찾을 수 있는 알고리즘입니다. 여기서 V는 노드 수이고 E는 에지 수입니다.



작동 방식은 노드 수의 길이인 두 개의 목록discovery과 low_link를 추적하는 것입니다. Tarjan의 알고리즘은 스택을 사용하여 SCC에서 계산된 노드를 기억하기 때문에 올바르게 작동합니다. 이것이 없으면 실제로 그래프에 있는 것보다 적은 SCC를 찾는 순서대로 그래프에서 DFS를 실행할 수 있습니다.

스택은 지금까지 SCC에 이미 포함된 노드를 추적하는 데 사용되므로 스택에 있는 노드를 만나면 현재 SCC의 일부여야 합니다.

알고리즘에 대한 높은 수준의 개요는 다음과 같습니다.

방문하지 않은 경우 노드에서 DFS를 실행하여 for 루프를 사용하여 모든 노드를 통과합니다.

노드를 방문하면 노드를 방문한 것으로 표시하고 각 노드에 ID를 표시하고 해당 노드의 discovery 및 low_link를 노드 ID와 동일하게 설정하는 카운터가 있습니다. 또한 노드를 스택에 푸시하고 노드가 스택에 있음을 기억하십시오.
이 알고리즘은 노드의 검색 시간과 low_link 값이 방문한 순서와 같다는 생각을 사용합니다. 이 순서는 알고리즘이 가장 낮은 공통 조상을 찾는 방법입니다.

방문하지 않은 노드에서 DFS를 실행하는 경우 노드의 모든 이웃을 통해 루프합니다.

재귀에서 돌아온 후 현재 노드의 값low_link을 자신과 이웃 사이의 최소값과 동일하게 설정합니다.

또한 이웃이 스택에 있는지 확인하고 있으면 SCC의 일부임을 의미합니다. low_link 값을 자신과 이웃의 검색 시간 사이의 최소값으로 설정합니다.

모든 이웃을 확인한 후 현재 노드의 discovery 값이 low_link 값과 같은지 확인하십시오. 이는 SCC에 대한 루트 노드를 의미합니다. 현재 노드를 포함하여 모든 노드를 팝합니다.

마지막에는 low_link 목록에 모든 SCC가 있어야 합니다!

이론적 특성

분명히 이 알고리즘은 SCC가 어떤 면에서 최대라는 사실에서 작동합니다. 즉, SCC를 찾으면 그 안에 다른 SCC가 없을 것임을 보장합니다. 알고리즘의 또 다른 유용한 속성은 SCC가 후속 작업보다 먼저 식별되지 않는다는 것입니다.

구현

Tarjan의 알고리즘 구현은 다음과 같습니다!

class TarjansGraph {
    public:
        inline static int UNVISITED = -1;
        vector<int> *adj_list;
        int n;

        TarjansGraph(int size) {
            this -> n = size;
            adj_list = new vector<int>[size];
        }

        void addEdge(int u, int v) {
            adj_list[u].push_back(v);
        }

        void dfs(int at, vector<int> &ids, vector<int> &low_list, vector<bool> &onStack, stack<int> &myStack) {
            ids[at] = at;
            low_list[at] = at;
            onStack[at] = true;
            myStack.push(at);

            for(auto iter : adj_list[at]) {
                if(ids[iter] == UNVISITED){
                    dfs(iter, ids, low_list, onStack, myStack);
                    low_list[at] = min(low_list[at], low_list[iter]);
                }
                else if (onStack[iter]) {
                    low_list[at] = min(low_list[at], ids[iter]);
                }
            }

            if (ids[at] == low_list[at]) {
                while(myStack.top() != at){
                    int stack_node = myStack.top();
                    cout << stack_node << " ";
                    onStack[stack_node] = false;
                    myStack.pop();
                }

                int at_stack_node = myStack.top();
                cout << at_stack_node << endl;
                onStack[at_stack_node] = false;
                myStack.pop();
            }
        }

        void findSCCs() {
            vector<int> ids(this -> n, TarjansGraph::UNVISITED);
            vector<int> low_list(this -> n, 0);
            vector<bool> onStack(this -> n, false);
            stack<int> myStack;

            for(int i = 0; i < this -> n; i++){
                if (ids[i] == TarjansGraph::UNVISITED) {
                    dfs(i, ids, low_list, onStack, myStack);
                }
            }
            cout << "\n\n\n LOW LIST VALUES: ";
            for (int i = 0; i < this -> n; i++){
                cout << low_list[i] << " ";
            }
            cout << endl;
        }

};