강력하게 연결된 구성 요소를 찾으십니까?

Question

내 책은 선형 시간에 유향 그래프의 강하게 연결된 구성 요소를 찾는 방법을 정의합니다. 또한 강하게 연결된 구성 요소 (예 : Tarjan의 알고리즘)를 찾는 데 사용할 수있는 몇 가지 알고리즘은 또한 선형 시간으로 구성 요소를 찾을 수 있습니다.

그러나 모든 알고리즘은 그래프의 정점이 포스트 값 (정점이 남아있는 시간)으로 감소하도록 정렬해야합니다. Mergesort와 같은 공통 순서 알고리즘은 O (n log n) 시간이 소요됩니다.

따라서 어떻게 시간 (N 로그 n)이 알고리즘 값이 O 소요 우편으로 정점의 목록을 주문하는 경우, 선형 시간에 강하게 연결 구성 요소의 위치를 ​​완료하기 위해 관리합니까?

Answer 1

"시간"(사후 값을 측정하는 종류)은 시간의 함수 (깊이 우선 검색 프로그램에서 실행 한 단계 수)에 따라 단조롭게 감소하지 않기 때문에 각 노드를 순회 직후의리스트는 그것을 남겨둔다. 순회가 끝나면 목록은 정렬 된 순서로 표시됩니다. 대안 적으로, 사후 값은 다항식으로 경계가 정해진 정수이기 때문에, 일부 머신 모델에서는, 예를 들어, 선형 모델을 사용하여 선형 시간으로 정렬 할 수있다. 기수 정렬.