Tarjan의 강력하게 연결된 구성 요소 알고리즘

Tarjan의 강력하게 연결된 구성 요소 알고리즘

타르잔의 알고리즘 애니메이션
자료구조	그래프
최악의 경우 성능	${\displaystyle O( V + E )}$

Tarjan의 강하게 연결된 성분 알고리즘은 그래프 이론에서 방향 그래프의 강하게 연결된 성분(SCC)을 찾는 알고리즘입니다.Kosaraju의 알고리즘과 경로기반 강성분 알고리즘을 포함한 대안적인 방법에 대한 시간 경계를 일치시키며 선형시간으로 실행됩니다.이 알고리즘은 발명가 로버트 타잔의 이름을 따서 지어졌습니다.^[1]

개요

알고리즘은 방향 그래프를 입력으로 받아 그래프의 꼭짓점의 분할을 그래프의 강하게 연결된 구성 요소로 만듭니다.그래프의 각 정점은 강하게 연결된 성분 중 하나에 정확히 나타납니다.방향이 지정된 주기에 있지 않은 모든 정점은 그 자체로 강하게 연결된 구성 요소를 형성합니다. 예를 들어 in-degree 또는 out-degree가 0인 정점 또는 비순환 그래프의 임의의 정점입니다.

알고리즘의 기본 개념은 다음과 같습니다. DFS(depth-first search)는 임의의 시작 노드에서 시작됩니다(이후 깊이 우선 검색은 아직 발견되지 않은 노드에서 수행됩니다).깊이 우선 검색의 경우와 마찬가지로 검색은 그래프의 모든 노드를 한 번만 방문하며 이미 방문한 노드는 다시 방문하지 않습니다.따라서 검색 트리의 컬렉션은 그래프의 스패닝 포리스트입니다.강력하게 연결된 구성 요소는 이 포리스트의 특정 하위 트리로 복구됩니다.이러한 하위 트리의 뿌리를 강력하게 연결된 구성 요소의 "뿌리"라고 합니다.강력하게 연결된 구성 요소의 노드는 검색을 통해 검색된 구성 요소의 첫 번째 노드일 경우 루트 역할을 할 수 있습니다.

스택 불변량

노드는 방문한 순서대로 스택에 배치됩니다.깊이 우선 검색이 노드를 재귀적으로 방문할 때v그리고 그 하위 노드인 이 재귀적 호출이 반환될 때 해당 노드가 반드시 스택에서 팝업되지는 않습니다.중요한 불변 특성은 입력 그래프에 노드에서 스택의 이전 노드로 가는 경로가 존재하는 경우에만 노드가 방문된 후 스택에 남아 있다는 것입니다.즉, DFS에서 노드는 연결된 모든 경로를 통과한 후에만 스택에서 제거됩니다.DFS가 역추적되면 단일 경로의 노드를 제거하고 루트로 돌아가 새로운 경로를 시작합니다.

방문하는 통화가 끝날 때v그리고 그 후손들은, 우리가 알고 있는 것은v그 자체는 스택의 이전 노드에 대한 경로를 가지고 있습니다.만약 그렇다면, 콜은 되돌아오고, 떠나는 것입니다.v불변성을 유지하기 위해 스택에 저장합니다.그렇지 않다면.v다음으로 구성된 강력하게 연결된 구성 요소의 루트여야 합니다.v보다 나중에 스택의 노드와 함께v(이러한 노드는 모두 다음으로 되돌아오는 경로를 가집니다.v그러나 이전 노드에는 없습니다. 왜냐하면 만약 그들이 이전 노드로 가는 경로를 가지고 있다면.v또한 이전 노드에 대한 경로도 있습니다. 이는 거짓입니다.연결된 구성 요소가 다음 위치에 있습니다.v그러면 스택에서 팝업되어 반환되며, 다시 불변성을 보존합니다.

경리

각노드v고유한 정수가 할당됩니다.v.index, 노드가 발견된 순서대로 연속적으로 번호를 매기는 것입니다.또한 값을 유지합니다.v.lowlink이는 스택에서 도달 가능한 것으로 알려진 노드 중 가장 작은 인덱스를 나타냅니다.v통해.v의 DFS 하위 트리는 다음과 같습니다.v그 자체.그러므로v다음과 같은 경우 스택에 남겨져야 합니다.v.lowlink < v.index, 반면에 v는 강력하게 연결된 구성 요소의 루트로서 제거되어야 합니다.v.lowlink == v.index. 값을v.lowlink깊이 우선 검색 동안 계산됩니다.v, 이것이 도달할 수 있는 노드를 찾으므로v.

low link는 low point와 다른데, low point는 low point에서 도달할 수 있는 가장 작은 인덱스입니다.v그래프의 어느 ^{[1]: 156 [2]}부분을 통해서도

의사코드의 알고리즘

알고리즘 tarjan 입력: 그래프 G = (V, E) 출력: 강하게 연결된 구성 요소 집합(꼭짓점 집합) 인덱스 : = 0 S : = v.index가 정의되지 않은 경우 v의 각 v에 대한 빈 스택: strongconnect(v) 함수 strongconnect(v) // v에 대한 깊이 인덱스를 사용되지 않는 가장 작은 인덱스 v.index : = 인덱스 v.lowlink : = 인덱스 : = 인덱스 + 1 S.push(v)v.onStack := true // w.index가 정의되지 않은 경우 E do의 각 (v, w)에 대해 v의 계승자를 고려하십시오. w.index가 정의되지 않은 경우 // Successor w가 아직 방문하지 않은 경우 // successor w가 stack S에 있는 경우 // successor w가 stack S에 있는 경우 (v, w)w)  는 이미 발견된 SCC를 가리키는 에지이므로 무시해야 합니다. // 참고: 다음 행은 이상해 보일 수 있지만 정확합니다. // w.index not w.lowlink로 표시됩니다. 이는 의도적이며 원본 v.lowlink := min(v.lowlink, w.index) // v가 루트 노드인 경우 스택을 팝업하고 v.lowlink = v.index인 경우 강력하게 연결된 구성 요소 반복 w := S.pop() w를 새로 시작합니다.onStack := false w를 현재 강하게 연결된 구성 요소에 추가하는 동안 ≠ v는 현재 강하게 연결된 구성 요소를 출력합니다.

그indexvariable은 깊이 우선 검색 노드 번호 카운터입니다.S는 노드 스택입니다. 노드 스택은 비어 있는 상태로 시작하여 탐색했지만 아직 강력하게 연결된 구성 요소에 커밋되지 않은 노드의 기록을 저장합니다.검색이 트리를 반환할 때 노드가 팝업되지 않으므로 일반적인 깊이 우선 검색 스택이 아닙니다. 강력하게 연결된 전체 구성 요소가 발견된 경우에만 노드가 팝업된 노드는 일반적인 깊이 우선 검색 스택이 아닙니다.

최외곽 루프는 아직 방문하지 않은 각 노드를 검색하여 첫 번째 노드에서 도달할 수 없는 노드가 최종적으로 횡단되도록 보장합니다.함수를strongconnect그래프에 대한 단일 깊이 우선 검색을 수행하여 노드에서 모든 계승자를 찾습니다.v, 해당 하위 그래프의 강력하게 연결된 모든 구성 요소를 보고합니다.

각 노드가 재귀를 완료할 때 낮은 링크가 여전히 인덱스로 설정되어 있으면 스택 위의 모든 노드에 의해 형성된 강력하게 연결된 구성 요소의 루트 노드가 됩니다.알고리즘은 스택을 현재 노드까지 팝업하고 이 모든 노드를 강력하게 연결된 구성 요소로 표시합니다.

참고:v.lowlink := min(v.lowlink, w.index)업데이트하는 방법이 정확합니다.v.lowlink한다면w스택에 있습니다.왜냐면w이미 스택에 저장되어 있고,(v, w)는 DFS 트리의 백엣지이므로w의 하위 트리에 있지 않습니다.v.왜냐면v.lowlink하위 트리의 노드를 통해서만 도달할 수 있는 노드를 고려합니다.v우리는 멈추어야만 합니다.w사용.w.index대신에w.lowlink.

복잡성

시간 복잡도:Tarjan 프로시저는 각 노드에 대해 한 번씩 호출되며, forall 문은 최대 한 번에 각 에지를 고려합니다.따라서 알고리즘의 실행 시간은 G의 에지 및 노드 수, 즉 $O{\displaystyle (V}$+ ${\displaystyle E)}$ ${\displaystyle O(V$+ E $)}$의 선형입니다$.$

이러한 복잡성을 달성하기 위해, 다음과 같은 여부에 대한 검정.w스택에 있습니다. 일정한 시간 내에 수행해야 합니다.예를 들어 각 노드에 스택에 있는지 여부를 나타내는 플래그를 저장하고 플래그를 검사하여 이 테스트를 수행할 수 있습니다.

공간 복잡도:Tarjan 절차는 다음을 위해 정점당 두 단어의 보충 데이터를 필요로 합니다.index그리고.lowlink필드, 및 하나의 비트를 포함합니다.onStack그리고 언제를 결정하기 위한 또 다른 것.index정의되지 않았습니다.또한 각 스택 프레임에 하나의 단어가 있어야 고정할 수 있습니다.v그리고 edge list의 현재 위치에 대해 other.마지막으로, 스택의 최악의 경우 크기S${\displaystyle V}$ $displaystyle V}$이어야 합니다($$즉, 그래프가 하나의 거대 성분인 경우).$O{\displaystyle (V}$⋅$)){\displaystyle O(V \cdot(2+5w))$의 최종 분석을 제공합니다.$}$여기서$$ $w{\displaystyle }$ ${\displaystyle w}$는 컴퓨터 단어 크기입니다.Nuutila와 Soisalon-Soinen의 변형으로 인해 이 $값$은 O$V$⋅${\displaystyle (}$${\displaystyle 1}$ ${\displaystyle +}$ ${\displaystyle 4}$ w${\displaystyle ))}${\$displaystyle O($V \$cdot (1$+ $4w))}$로 줄었고, 그 다음에는 Pearce의 것만 $O{\displaystyle (V}$ ⋅${\displaystyle (1}$+ ${\displaystyle \mathrm{3w}))}$ ${\displaystyle O( V \cdot (1$+ $3w))}$만 필요로 합니다$.$

추가 비고

강력하게 연결된 각 구성 요소 내의 노드 순서에 대해 특별한 것은 없지만, 알고리즘의 유용한 특성 중 하나는 강력하게 연결된 구성 요소가 그 후속 요소보다 먼저 식별되지 않는다는 것입니다.따라서, 강하게 연결된 구성요소가 식별되는 순서는 강하게 연결된 구성요소에 의해 형성되는 DAG의 역위상 유형을 구성합니다.^[5]

Donald Knuth는 The Stanford GraphBase라는 책에서 Tarjan의 SCC 알고리즘을 그가 가장 좋아하는 구현 중 하나로 묘사했습니다.^[6]

그는 다음과 같이 썼습니다.^[7]

이 문제를 위해 그가 고안한 데이터 구조는 놀라울 정도로 아름다운 방식으로 함께 들어맞기 때문에 방향 그래프를 탐색할 때 필요한 양은 항상 마법처럼 손끝에 있습니다.그리고 그의 알고리즘은 부산물로서 위상 정렬도 합니다.

참고문헌

외부 링크

• 다른 언어로 구현된 로제타 코드
• Tarjan의 강력하게 연결된 컴포넌트 알고리즘의 PHP 구현
• Tarjan의 강력하게 연결된 컴포넌트 알고리즘의 자바스크립트 구현