주어진 그래프 G가 주어지면 v에서 v의 모든 다른 정점까지의 경로가 존재하도록 정점 v를 찾는 가장 좋은 방법은 무엇입니까?지시 된 그래프 연결성
이 알고리즘은 선형 시간으로 실행되어야합니다. 이 문제를 해결하는 기존 알고리즘이 있습니까? 그렇지 않은 경우 선형 시간으로 어떻게 해결할 수 있는지에 대한 통찰력을 얻을 수 있습니다 (선형 시간을 확실히 고려하지 않는 솔루션 만 생각할 수 있습니다).
모든 정점의 목록 L을 만듭니다.
하나를 선택하십시오. 그것을 V라고 부르십시오. V에서 그래프를 보면서 이동하면서 목록에서 점을 제거하고, 방문하지 않은 모서리의 스택을 유지하십시오. 루프를 찾으면 (방문한 일부 정점은 목록에 없음) 스택의 가장자리 중 하나를 튀어 나오고 계속 진행합니다.
스택이 비어 있고 L이 비어 있지 않은 경우 L에서 새 정점을 선택하고 V로 호출 한 다음 이전과 같이 진행합니다.
L이 마침내 비어 있으면 마지막에 선택한 V가 대답입니다.
그래프에서 실제로 조건을 만족하는 것이 없더라도 일부 노드를 반환합니다. OP와 관련이 있는지 모르겠지만 언급해야한다고 생각합니다. – svick
네, 맞습니다. 나는 당신이 처음부터 모든 그래프를 다시 마킹한다고 생각할 때만 그래프가 시작되는 것을 시도함으로써 답이 충분한지를 확인할 수 있다고 생각한다. 이것은 여전히 선형 일 것입니다, 나는 믿습니다. 그리고 테스트가 실패하면 해결책이 없습니다. –
이것은 선형 시간으로 가장자리 수에서 수행 할 수 있습니다.
나는 정확한 대답을 가지고 있다고 생각합니다.
이것은 충분하고 필요한 조건입니다.
Skienna의 "알고리즘 설계 매뉴얼"을 확인하십시오. 그것은 그래프에 관한 좋은 장을 가지고 있습니다. – duffymo