강력하게 연결된 구성 요소 Algo를 사용하여 정점에 도달 할 수 있는지 확인

Question

주어진 정점, V0에 그래프 G의 다른 모든 정점이 도달 할 수 있는지보고 싶습니다.
각 요소를 통과 할 수 있다는 것을 알고 있습니다. 버텍스를 그래프에 표시하고 BFS/DFS를 실행하여 V0에 도달 할 수 있는지 확인합니다.
그러나 이것은 매우 비효율적 인 것으로 보입니다.

그래프에서 SCC algo를 수행하고 v0이 모든 scc의 일부인지 궁금한 점은 v0가 모든 꼭지점을 통해 도달 할 수 있다고 결론을 내릴 수 있습니까? 이것은 SCC의 비용이 Tarjan의 경우 O (V + E)이고 v0가 scc인지 여부를 확인하기 때문에 선형 시간 비용이 들기 때문에 위대한 결과를 얻을 수 있습니다.

SCC는 꼭지점에 도달 할 수 있으므로 의미가 있다고 생각합니다. 이 논리에 대한 어떤 확인?

또는 이에 대한 효율적인 접근 방법은 무엇입니까?

Answer 1

V0는 SCC에 속하지 않을 수 있지만 다른 모든 꼭지점을 통해 도달 할 수 있습니다. 예를 들어, 다이어그램의 정점 d에 다른 모든 정점에서 연결할 수 있지만 중요하지 않은 SCC는 정점 a, b, c을 포함하며 꼭지점 d을 포함하지 않습니다. V0 다른 모든 정점으로 도달 할 수 있는지

다른 모든 정점이 있는지 확인하기 위해, V0부터 시작, 다음 사용하면 (선형 시간) 모든 에지의 방향을 반대로 할 수 BFS/DFS를 확인하려면 V0에서 도달 할 수 있습니다 (또한 선형 시간으로).

Answer 2

다른 모든 정점에 도달 할 수있는 정점, 즉 비스타 정점을 호출합시다. 그래프에 비스타 버텍스가있는 경우 (두 소스 SCC는 에 도달 할 수 없기 때문에) 하나의 소스 SCC 만 있어야하며 비스타 버텍스가 있어야합니다 (다른 SCC에서는 SCC에 경로가 없음 비스타 버텍스에서 소스 SCC로). 또한,이 경우 소스 SCC에있는 모든 정점이 비스타 정점이됩니다. 그런 다음 알고리즘은 모든 노드에서 시작하는 DFS로 간단히 가장 높은 완료 시간 인 으로 정점을 표시합니다. 이것은 출처 SCC에 있어야합니다. 이 꼭지점에서 DFS를 다시 실행하여 모든 노드에 도달 할 수 있는지 확인합니다. 알고리즘은 단지 SCC와 DFS로 분해를 사용하기 때문에, 실행 시간은 선형이다. 이 알고리즘은 정확합니다. 단지 SCC 소스가 인 경우에만 비스타 버텍스가 존재합니다. 소스 SCC의 모든 정점은 동일한 SCC에있는 다른 정점 인 에 의해서만 접근 할 수 있으므로 두 개의 고유 한 소스 SCC에서 정점에 도달 할 수있는 정점이 없습니다. 또한 하나의 소스 SCC 만있는 경우 해당 SCC의 모든 정점은 각각 기타에서 모두 도달 할 수 있으므로 비스타 정점입니다. 특정 SCC에서 시작하는 DFS는 모든 SCC에서 도달 할 수있는 모든 SCC가 검색 될 때까지 완료되지 않습니다. 이것은 최종 노드가 SCC 에 있고 다른 SCC, 즉 소스 SCC로부터 도달 할 수 없다는 것을 의미합니다. 따라서 우리의 알고리즘의 첫 번째 부분에서 소스 SCC에서 노드를 찾습니다. DFS를 수행함으로써 비스타의 버텍스인지 아닌지 정확하게 결정할 것이며 비스타의 버텍스가 아니면 그래프에 아무 것도 존재하지 않는다는 것을 알게됩니다.