전체 도달 가능성을 테스트하는 가장 좋은 방법

Question

노드 집합이 있는데 각 노드는 적어도 하나의 다른 노드에 연결되어 있습니다.각 노드가 서로 연결될 수 있도록 연결되어 있는지 알고 싶습니다.예를 들어:

1--2
   |
3--4

대:

1--2

3--4

나는 이러한 종류의 도달 가능성 테스트가 다음과 같은 측면에서 예상될 수 있다고 확신합니다. 정확한 표지 문제, 그러나 나는 그렇게 하는 방법에 대해 내 머리를 감쌀 수 없는 것 같습니다.이 작업을 수행하는 방법에 대한 지침, 문서, 웹 사이트 등이 있는 사람이 있습니까?예는 매우 귀중한 것입니다.

업데이트: 이런 종류의 테스트에는 훨씬 더 효율적인 알고리즘이 있는 것처럼 보였기 때문에 나의 무지가 나를 배반했습니다.혹시 갖고 계신다면 저에게 알려주세요.

Answer 1

• 모든 노드에서 시작하여 깊이/너비 첫 번째 트래버스를 수행합니다.
• 방문한 노드 수를 계산하십시오 (물론, 노드를 두 번 방문하지 마십시오!)
• 계수 숫자를 총 숫자와 비교하십시오

Answer 2

동적으로 연결을 유지하기 위한 빠르고(그러나 매우 복잡한) 알고리즘도 있습니다(예:가장자리 삽입/삭제 아래), 이 문서에 나와 있습니다. 연결성, 최소 스패닝 트리, 2-에지 및 이중 연결성을 위한 다중 로그 결정론적 완전 동적 알고리즘

기본 아이디어는 스패닝 트리를 유지하는 것입니다.쉬운 경우는 가장자리를 삽입하고 비연결 트리 가장자리를 삭제하는 것입니다.문제는 스패닝 트리 가장자리를 삭제할 때입니다. 이제 연결이 보장되지 않기 때문입니다. 끊어진 부분을 연결하기 위해 대체 경로를 효율적으로 검색해야 합니다. 그렇지 않으면 그래프 연결이 끊어집니다.