3
지금은 무차별 및 비가 중 그래프에서 두 노드 간의 모든 경로를 검색하기 위해 재귀 DFS를 작업하고 있습니다. 경로를 저장하는 동안 노드와 그 인접 노드에서 시작 W 끝 노드와 DFS를] 복적으로 사용합니다. 모든 경로를 찾는 더 효율적인 방법이 있는지 궁금합니다.두 노드 사이의 모든 경로를 찾는 효율적인 알고리즘
A
답변
3
단순한 경로의 지수가 있습니다. DFS는 기본적으로 모두 0을 작성하므로 시간이 많이 걸리지 만 접근 방식은 정확합니다 (그러나 이것은 알고리즘이 아니라 문제 자체의 일부입니다).
그래프 노드에서 대상 노드가없는 경우이를 제거하여 비트 맵을 최적화 할 수 있습니다. 이러한 노드를 계산하기 전에 불완전한 검색을 효과적으로 줄입니다.
그래프에 사이클이있는 경우 - 무한 수의 경로가있을 수 있음을 유의하십시오 (의 간단한 번호는 경로 임). 무한 루프를 피하고 모든 간단한 경로를 얻으려면 DFS가 경로마다 수정되는 visited 집합을 유지해야합니다 (일단 "발견"하여 노드가 설정을 삽입하면 스택에서 터지면 제거 그것은 집합에서).
1
당신은 ... 당신은 모든 경로를 찾으려면 또한 당신이 그들 모두를 걸어야, A Recursive Algorithm to Find all Paths Between Two Given Nodes
+0
이미 제공 한 알고리즘과 비슷한 재귀 알고리즘을 이미 수행했습니다. 그러나 Dijkstra 's Algorithm을이 목적에 어떻게 적용 할 수 있습니까? – Ever
관련 문제
- 1. xquery - 두 노드 사이의 모든 경로를 찾는 BFS
- 2. OWL 온톨로지에서 두 노드 사이의 모든 경로를 찾는 쿼리
- 3. 그리드에서 2 노드 사이의 경로를 찾는 가장 효율적인 방법
- 4. 두 노드 사이의 모든 경로를 찾으십시오.
- 5. 두 노드 사이의 모든 경로를 가져옵니다. neo4j
- 6. 두 객체 간의 최단 경로를 찾는 알고리즘
- 7. 무 방향성 그래프에서 임의의 두 노드 사이의 경로를 찾는 효율적인 방법
- 8. 가중치가 부여 된 그래프에서 두 노드 간의 최단 경로를 찾는 가장 효율적인 (Big O) 알고리즘
- 9. 모든 "문자 등호"문자열을 찾는 효율적인 알고리즘?
- 10. 텍스트의 모든 키워드를 찾는 효율적인 알고리즘
- 11. 두 매트릭스 사이의 변환 매트릭스를 찾는 알고리즘.
- 12. 모든 도시에 대한 경로를 찾는 알고리즘
- 13. XQuery에서 두 그래프 노드 사이의 경로를 검색합니다.
- 14. TraversalDescription이있는 neo4j의 두 노드 사이의 모든 경로가 잘못된 경로를 반환합니다.
- 15. 무 방향성 그래프에서 두 노드 사이의 가능한 모든 경로를 찾으십시오.
- 16. 연결된 목록에서 두 노드 사이의 모든 경로를 검색하는 방법 그래프
- 17. QuickGraph를 사용하여 두 꼭지점 사이의 모든 경로를 찾는 방법
- 18. 미로에서 움직이는 엔티티를 찾는 알고리즘
- 19. 노드 간 모든 단순 경로를 찾는 데 문제가 있습니까?
- 20. 문자열 오버랩을 찾는 효율적인 알고리즘
- 21. 관련 제출물을 찾는 효율적인 알고리즘
- 22. DAG에서 해밀턴 경로를 찾는 알고리즘
- 23. 거대한 그래프를 메모리에로드하여 주어진 두 노드 사이의 최단 경로를 반복적으로 찾는 방법?
- 24. 트리에서 두 노드 사이의 경로 길이를 찾는 방법은 무엇입니까?
- 25. 무향 그래프 경로를 찾는 알고리즘
- 26. 자유 트리에서 두 노드 사이의 최장 거리를 찾는 선형 시간 알고리즘?
- 27. 한계가있는 경계가없는 가중치가있는 undirected 그래프에서 두 노드 사이의 모든 경로
- 28. 그래프의 모든 컷을 찾는 알고리즘
- 29. 고도를 사용하여 최단 경로를 찾는 그래프 알고리즘
- 30. BFS를 사용하여 두 노드 사이의 거리를 찾는 방법은 무엇입니까?
를 참조 익스트라의 알고리즘을 적용 할 수 방금 경로의 수를 찾으시겠습니까? 그런 다음 더 빠른 방법이있을 수 있습니다. – irrelephant
숫자에만 관심이 있다면 더 효율적인 알고리즘이있을 수 있습니다. –
@irrelephant 각 경로의 노드에서 일부 작업을 수행하고 싶습니다. 따라서 모든 경로를 찾아서 그 번호를 저장해야합니다. – Ever