가중 된 비순환 그래프에서 소스 노드에서 다른 모든 노드까지의 최단 경로를 찾기 위해 BFS를 (가장 최적의 방법으로) 사용할 수 있습니까?

위상 정렬을 사용하여 O (V + E)에서 수행 할 수 있음을 알고 있습니다. 그러나 BFS를 사용하여 동일한 복잡성으로도 수행 할 수 있다고 생각합니다.가중 된 비순환 그래프에서 소스 노드에서 다른 모든 노드까지의 최단 경로를 찾기 위해 BFS를 (가장 최적의 방법으로) 사용할 수 있습니까?

출처

2017-04-23 Aditya Joshee

(가장 최적의 방법으로) 무엇을 의미합니까? 만약 당신이 의미하는 것이 복잡하다면 그렇습니다. 토폴로지 종류는 O (V + E)의 복잡성을 갖는 DFS의 적용입니다. "BFS를 사용하여 토폴로지를 정렬 할 수 있습니까?"라는 질문은 더 자연스러운 것 같습니다. 이 질문은 이미 질문되었습니다. – Abdulhakeem

나는 토폴로지 순서로 노드를 방문하는 대신 BFS를 사용할 수 있다는 것을 의미했습니다. –

토폴로지 정렬은 하나의 DFS 실행을 제외하고는 아무 것도 아닙니다. 그런 다음 각 정점이 완료되면 링크 된 목록의 맨 위에 놓습니다. 실행 시간은 O (V + E)입니다. 전에 말했듯이 "BFS를 사용하여 토폴로지를 정렬 할 수 있습니까?"라는 질문은 자연스러운 것 같습니다. 이것은 이미 묻고 대답했습니다.

만약 당신이 의미하는 것이 단순한 BFS라면, 나는 아니오라고 말할 것입니다. 이것 좀 봐 example. 토폴로지 정렬은 모든 정점의 선형 순서이므로 그래프 G에 모서리 (u, v)가 있으면 u가 순서 지정 전에 v 앞에 나타납니다. 이 예제에서 c에서 d까지의 가장자리가 있지만 c 앞에는 d가 나타납니다. 토폴로지 종류를 찾기 위해 BFS를 업데이트 할 수 있다고 생각하지만 다시 DFS를 실행하는 것과 동일한 복잡성이 있습니다. 이 게시물을 보길 권합니다. Using BFS for topological sort

출처

2017-04-25 16:42:24 Abdulhakeem

얼마 동안 토폴로지 정렬을 잊어 버리자. 소스 노드 s에서 시작하여 DAG에 대한 너비 우선 탐색을 사용하면 거리 배열을 유지하고 (무한대로 초기화 됨) O (V + E) 시간에 다른 모든 노드까지의 최단 거리를 찾을 수 있습니다. 노드에 대해 현재 저장된 값보다 작은 값을 얻습니다. 그래서 원래의 질문으로 돌아가서 DAG의 노드를 통과하는 최단 경로를 찾기 위해 토폴로지 순서를 사용하는 것과 같은 복잡성에 대한 접근 방식이 아닙니까? –

가중 된 비순환 그래프에서 소스 노드에서 다른 모든 노드까지의 최단 경로를 찾기 위해 BFS를 (가장 최적의 방법으로) 사용할 수 있습니까?

답변

관련 문제