Tarjan의주기 감지 : 누락 된주기

Question

http://learn.yancyparedes.net/2012/03/strongly-connected-components-using-tarjans-algorithm/에서 구현 된주기 탐지를 위해 Tarjan 알고리즘을 사용해 보았습니다. 다음 그래프는 실험에 사용 하였다 :
AB
에게 AC
BA
BC
CD
DA
을 난 다음과 같은 결과를 얻었다 출력 같이 설정 0 : C, B, A, D]

제 문제는 모든 사이클이 필요하므로이 결과에서 Sets [a, b] 및 [a, c, d]가 누락되었습니다. 모든주기를 얻기 위해 구현을 수정하는 방법이 있다면 지금 받으시겠습니까? 또는이 알고리즘에 다른 알고리즘이 있습니까?

감사합니다.

Answer 1

Tarjan 알고리즘이 모든주기를 찾지 못합니다. 그것은 똑같은 것은 아니지만 강하게 연결된 모든 구성 요소를 찾습니다. 일반적인 경우에 모든 사이클을 효율적으로 찾을 수는 없습니다 (전체 그래프의 경우 출력 크기가 지수 함수입니다. 또한 가장 긴 사이클을 찾는 것은 이미 NP 하드입니다). 물론 역 추적을 사용할 수 있습니다.