경로 기반 강력한 구성요소 알고리즘

Path-based strong component algorithm

그래프 이론에서 지시된 그래프의 강하게 연결된 구성요소는 두 개의 스택과 함께 깊이 우선 검색을 사용하는 알고리즘을 사용하여 찾을 수 있다. 하나는 현재 구성요소의 정점을 추적하기 위한 것이고, 다른 하나는 현재 검색 경로를 추적하기 위한 것이다.[1]이 알고리즘의 버전은 푸르돔(1970), 문로(1971), 디즈크스트라(1976), 체리얀&멜혼(1996), 가보우(2000)에 의해 제안되어 왔으며, 이 중 디즈크스트라의 버전은 가장 먼저 선형 시간을 달성했다.[2]

설명

알고리즘은 주어진 그래프 G의 깊이 우선 검색을 수행하여 S와 P를 두 스택(재귀 함수에 대한 정상적인 호출 스택에 더하여)으로 유지한다.스택 S는 깊이 첫 번째 검색이 정점에 도달하는 순서로, 아직 강하게 연결된 구성 요소에 할당되지 않은 모든 정점을 포함한다.스택 P는 서로 강하게 연결된 서로 다른 구성요소에 속한다고 아직 결정되지 않은 정점을 포함한다.또한 지금까지 도달한 정점 수의 카운터 C를 사용하여 정점의 사전 순서 번호를 계산한다.

깊이 첫 번째 검색이 정점 v에 도달하면 알고리즘은 다음 단계를 수행한다.

  1. v의 예약 주문 번호를 C로 설정하고, C를 증분하십시오.
  2. V를 S에 밀어넣고 P에도 밀어 넣는다.
  3. v에서 인접 정점 w까지 각 에지에 대해:
    • 사전 주문 번호 w가 아직 할당되지 않은 경우(가장자리가 트리 가장자리임) w;
    • 그렇지 않은 경우, w가 아직 강하게 연결된 구성 요소에 할당되지 않은 경우(가장자리가 전방/후방/십자각 에지임):
      • P의 상단 요소가 w의 사전 주문 번호보다 작거나 같은 사전 주문 번호를 가질 때까지 P에서 정점을 반복해서 표시한다.
  4. v가 P의 상위 요소인 경우:
    • S에서 v가 펑크날 때까지의 pop 정점을 표시하고, 펑크 난 정점을 새 구성 요소에 할당한다.
    • P의 팝 v.

전체 알고리즘은 그래프의 정점을 통과하는 루프로 구성되며, 아직 사전 주문 번호가 할당되지 않은 각 정점에 대해 이 재귀 검색을 호출한다.

관련 알고리즘

이 알고리즘처럼 타르잔의 강하게 연결된 구성요소 알고리즘도 먼저 깊이 검색을 스택과 함께 사용하여 아직 구성요소에 할당되지 않은 정점을 추적하고, 구성요소의 최종 정점 확장을 마치면 이러한 정점을 새로운 구성요소로 이동시킨다.그러나, 스택 P 대신에 타르잔의 알고리즘은, 깊이 우선 검색에서 정점이 처음 방문되는 순서로 할당된, 정점 색인화된 사전 주문 번호 배열을 사용한다.사전 주문 배열은 새 구성요소를 형성할 시기를 추적하기 위해 사용된다.

메모들

  1. ^ 세지윅(2004년).
  2. ^ 강력한 구성요소를 위한 경로 기반 DFS의 역사, Harold N. Gabow는 2012-04-24에 접속했다.

참조

  • Cheriyan, J.; Mehlhorn, K. (1996), "Algorithms for dense graphs and networks on the random access computer", Algorithmica, 15 (6): 521–549, doi:10.1007/BF01940880, S2CID 8930091.
  • Dijkstra, Edsger (1976), A Discipline of Programming, NJ: Prentice Hall, Ch. 25.
  • Gabow, Harold N. (2000), "Path-based depth-first search for strong and biconnected components", Information Processing Letters, 74 (3–4): 107–114, doi:10.1016/S0020-0190(00)00051-X, MR 1761551.
  • Munro, Ian (1971), "Efficient determination of the transitive closure of a directed graph", Information Processing Letters, 1 (2): 56–58, doi:10.1016/0020-0190(71)90006-8.
  • Purdom, P., Jr. (1970), "A transitive closure algorithm", BIT, 10: 76–94, doi:10.1007/bf01940892, S2CID 20818200.
  • Sedgewick, R. (2004), "19.8 Strong Components in Digraphs", Algorithms in Java, Part 5 – Graph Algorithms (3rd ed.), Cambridge MA: Addison-Wesley, pp. 205–216.