Tarjan 알고리즘과 Kosaraju 알고리즘 비교

Tarjan의 알고리즘은 유향 그래프에서 강하게 연결된 구성 요소를 찾기 위한 것입니다. Robert Tarjan은 1972년에 Tarjan의 알고리즘이라는 그래프 탐색 기술을 만들었습니다. 이전에 처리된 노드를 순회하는 대신 깊이 우선 검색 전략과 스택 데이터 구조를 사용하여 관련성이 높은 각 구성 요소를 효율적으로 찾고 처리합니다. 이 알고리즘은 컴퓨터 과학 및 그래프 이론에서 자주 사용되며 알고리즘 생성, 네트워크 분석, 데이터 마이닝 등 다양한 용도로 사용됩니다.

코사라주의 알고리즘은 두 번의 그래프 순회로 구성됩니다. 첫 번째 패스에서는 그래프가 역순으로 탐색되고 각 노드에 "완료 시간"이 할당됩니다. 두 번째 패스에서는 완료 시간 순서대로 노드를 방문하고 강하게 연결된 각 구성 요소를 식별하고 레이블을 지정합니다.

Tarjan 알고리즘 방법

이 예제에서 Graph 클래스는 프로그램 시작 부분에 정의되고 해당 생성자는 그래프의 정점 수를 기반으로 인접 목록 배열을 초기화합니다. addEdge 함수는 소스 정점의 인접 목록에 대상 정점을 포함시켜 그래프에 간선을 추가합니다.

SCCUtil 메소드는 SCC 메소드에서 SCC를 발견하는 데 사용되는 DFS 기반 재귀 함수이며, 이 프로그램의 기초를 형성합니다. 현재 정점 u, 발견 횟수 디스크의 배열, low 값의 배열 low, 정점 스택 st의 배열, 그리고 정점이 스택에 있는지 추적하는 부울 값의 배열 stackMember, 이 함수에 대한 입력입니다.

이 프로세스는 현재 정점을 스택에 넣고 먼저 검색 시간과 낮은 값을 할당한 후 stackMember 값을 true로 변경합니다. 그 후, 근처의 모든 정점의 낮은 값을 현재 정점으로 재귀적으로 업데이트합니다.

이 기술은 발견되지 않은 정점 vs를 반복적으로 방문하여 u의 낮은 값을 수정합니다. v가 이미 스택에 있는 경우 이 메서드는 v가 발견된 시간을 기준으로 u의 하한 값을 수정합니다.

Tarjan 알고리즘

• 초기화 알고리즘

• 차트 탐색을 시작하세요

• 강하게 연결된 구성요소 확인

• 모든 노드를 방문할 때까지 반복

• 강하게 연결된 구성요소 반환

이 메서드는 현재 정점 u가 팝될 때까지 스택에서 모든 정점을 팝하고 팝된 정점을 인쇄하며, u가 헤드 노드인 경우(즉, 낮은 값이 검색 시간과 같은 경우) stackMember 값을 false로 설정합니다.

예

으아아아

출력

으아아아

방법 2 - 코사라주

코사라주 알고리즘

• 방문한 노드 컬렉션과 시작 시 빈 스택을 만듭니다.

• 아직 방문하지 않은 그래프의 첫 번째 노드부터 깊이 우선 검색을 시작합니다. 검색을 통해 방문한 각 노드를 스택에 푸시합니다.

• 각 그래픽 가장자리의 방향이 바뀌어야 합니다.

• 스택이 여전히 노드로 가득 차 있으면 스택에서 노드를 팝합니다. 해당 노드를 방문하지 않은 경우 해당 노드에서 깊이 우선 검색이 수행됩니다. 검색 중에 방문한 각 노드를 현재 고도로 연결된 구성 요소의 구성원으로 표시합니다.

• 모든 노드를 방문할 때까지 반복하세요

.

• 프로그램이 끝날 때마다 고도로 연결된 모든 구성 요소가 식별되고 주석이 추가됩니다.

다음 C++ 코드는 Kosaraju의 알고리즘을 사용하여 방향성 그래프에서 SCC(Strongly Connected Components)를 찾습니다. 소프트웨어는 다음과 같은 멤버 함수를 갖는 Graph라는 클래스를 정의합니다.

Graph(int V): 생성자, 정점 수 V를 입력하고 그래프의 인접 목록을 초기화합니다.

Void addEdge(int v, int w): 두 개의 정수 v와 w를 입력으로 사용하여 이 메서드는 그래프의 정점 v와 정점 w를 연결하는 모서리를 생성합니다.

void printSCCs() 함수는 Kosaraju 알고리즘을 사용하여 그래프의 각 SCC를 인쇄합니다.

Graph getTranspose() 메소드는 그래프의 전치를 제공합니다.

재귀 함수 void fillOrder(int v, bool Visited[, stack& Stack], int v)를 사용하여 완료 시간 순서대로 스택에 정점을 추가합니다.

예 2

으아아아

출력

으아아아

결론

요약하면 Tarjan과 Kosaraju 방법의 시간 복잡도는 O(V + E)입니다. 여기서 V는 그래프의 꼭지점 집합을 나타내고 E는 그래프의 모서리 집합을 나타냅니다. Tarjan 알고리즘의 상수 요소는 Kosaraju 방법의 상수 요소보다 상당히 낮습니다. Kosaraju의 방법은 그래프를 최소한 두 번 순회하므로 상수 요소는 아마도 두 배 더 높을 것입니다. 두 번째 DFS를 완료하면 Kosaraju의 방법을 사용하여 현재 활성화된 SCC를 생성할 수 있습니다. SCC 하위 트리의 헤드가 발견되면 Tarjan 알고리즘을 사용하여 SCC를 인쇄하는 데 시간이 더 오래 걸립니다.

두 방법의 선형 시간 복잡도는 동일하지만 SCC 계산에 사용되는 방법이나 프로세스에는 약간의 차이가 있습니다. Kosaraju의 기술은 그래프에서 두 개의 DFS(또는 원본 그래프를 수정하지 않은 상태로 유지하려는 경우 세 개의 DFS)를 실행하고 그래프의 위상 순서를 결정하는 방법과 매우 유사하지만 Tarjan의 방법은 노드 레코드에만 의존합니다. DFS는 그래프를 분할합니다. .

위 내용은 Tarjan 알고리즘과 Kosaraju 알고리즘 비교의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!