스패닝 트리와 스패닝 트리가 아닌 가장자리가 주어지면 사이클베이스를 형성하는 방법은 무엇입니까?

Question

Edge가있는 그래프가 있습니다 E 그리고 vertex V, 나는 스패닝 트리를 사용하여 찾을 수 있습니다 Kruskal 알고리즘 (또는 기타 트래버스 백 트랙 트래버스 가게의 알고리즘), 이제 나는 그 스패닝 트리와 트리가 아닌 가장자리, 가장자리, 내가 할 수있는 알고리즘을 사용하여 생성 된 모든 사이클베이스를 찾고 싶습니다. 그게 무차별 인력 검색 외에?

물론, 스패닝되지 않은 나무 가장자리의 한 정점에서 시작하여 모든 가장자리를 가져오고, 모든 모서리를 탐색하고, 막 다른 골목을 찾으면 철회합니다. 그러나 이것은 조금, 잘못 ... 잔인합니다. 다른 아이디어가 있습니까?

Answer 1

그래프에서주기를 찾는 데 사용하는 간단한 알고리즘 :

각 노드에 부모가있는 깊이 우선 스패닝 트리를 만듭니다. 트리를 가로 지르면 중고 노드의 레코드를 만듭니다. 모서리가 이전에 사용 된 노드를 가리키면 주기적 가장자리로 저장하십시오. 스패닝 트리가 완료되면 순환 모서리의 수는 사이클 수를 제공합니다. 각각의 순환 가장자리에 대해 공통 조상이 발견 될 때까지 두 노드의 조상을 통해 되풀이됩니다. 그것은 정확히 사이클을 줄 것입니다.

주기적 가장자리 노드의 모든 조상의 인덱스 (Hashtable)를 갖는 것이 유용하여 공통 조상을 빠르게 찾을 수 있습니다.

이것이 최고의 알고리즘이라고 의심하지만 상당히 빠릅니다.

편집하다 Spanning 트리의 각 노드에 주석을달라고 Repsonse에서는 부모가 있습니다. 순환 가장자리의 노드에 도달하면 조상 목록을 계산합니다. (List<Node>이 목록은 속도를 위해 색인화 될 수 있습니다 (예 : contatians ()은 < O(n)). 두 개의 노드가있는 주기적 가장자리 (n1, n2) 그런 다음 조상을 통해 반복합니다 n1, n1.ancestorList (목록이 이미 생성 된 이후 신속하게) 조상이 n2.ancestorList. 그 경우 (commonAncestor), 그리고 정확히 횡단 된 조상은 사이클에 해당합니다. 그런 다음 도달 할 때까지 N2를 반복하십시오 commonAncestor (빠른). 시간은 목록의 조회와 결합 된 순환 가장자리의 수에 따라야합니다 (아마도 O(logN) 그러나 싸구려). 그래프를 다시 탐색 할 필요가 없으며 역 추적이 없습니다.

Answer 2

스패닝 트리를 구성한 후 트리에 있지 않은 모든 가장자리 (A, B)에서 반복 하고이 가장자리의 노드에 대해 가장 낮은 공통 조상 (LCA)을 찾으면주기

이 링크를 사용할 수 있습니다.http://www.topcoder.com/tc?module=static&d1=Tutorials&d2=LOWESTCOMMONANCESTOR효율적인 최저 공통 조상 알고리즘 구현을 위해.