1
나는 유향 그래프의 두 특정 노드 사이의 모든 노드를 찾는 알고리즘을 찾고 있습니다. 예를 들어 아래 그래프에서 노드 "a"와 "j"사이의 노드는 다음과 같습니다.유향 그래프의 두 특정 꼭지점 사이의 모든 노드 찾기
b c d e f g h i
P.S. 그래프는 방향이 지정되고 가장자리는 위 (아래에서 위로)입니다.
A
답변
2
당신은 시작 노드의 노드에 도달 할 수 있으며, 해당 노드가 목적지 노드 t에 도달 할 수있는 노드 세트를 찾고 있습니다. 이를 수행하는 한 가지 방법은 s에서 도달 가능한 모든 노드를 찾기 위해 D에서 D를 수행하고 t에서 역 DFS를 찾아 t에 도달 할 수있는 모든 노드를 찾은 다음 해당 두 세트의 교집합을 취하는 것입니다. 노드 자체에 마크 비트를 저장하여 세트를 유지 관리하는 경우 선형 시간으로 실행됩니다.
희망이 도움이됩니다.
관련 문제
- 1. 유향 그래프의 특정 노드를 포함하는 경로 찾기
- 2. 유향 그래프의 최단 경로 찾기
- 3. 두 개의 꼭지점 사이의 무향 그래프에서 특정 모서리 찾기
- 4. 노드가 유향 그래프의 노드 경로에 있는지 확인하십시오.
- 5. 그래프 - 유향 그래프의 사각형
- 6. 유향 그래프의 최단 경로 인쇄
- 7. 유향 그래프에서 두 노드 사이에있는 모든 노드를 효율적으로 찾습니다
- 8. 그래프의 모든 노드 탐색
- 9. 특정 레이블이있는 모든 노드 찾기
- 10. 그래프의 두 개의 분리 된 하위 집합에 속한 임의의 두 노드 사이의 최단 경로 찾기
- 11. 그래프의 모든 노드 쌍에서 모든 최단 경로 찾기
- 12. 알고리즘은 유향 그래프의 문제에 대한
- 13. 두 노드 사이의 최단 경로 찾기 (정점)
- 14. DFS가있는 그래프의 모든 경로 찾기
- 15. 두 개의 다른 노드 사이의 거리를 최소화하는 그래프에서 노드 찾기
- 16. 유향 그래프의 리더 선출 알고리즘
- 17. 베지에 곡선의 꼭지점 찾기
- 18. QuickGraph를 사용하여 두 꼭지점 사이의 모든 경로를 찾는 방법
- 19. 유향 그래프의 데이터 처리를위한 스레딩 모델
- 20. 두 인접한 노드 사이의 거리가 최소가되도록 그래프의 노드를 주문하는 방법
- 21. 연결된 그래프의 두 노드 사이의 이격 정도를 계산합니다.
- 22. 두 날짜 사이의 특정 날짜 찾기 PHP
- 23. DFS가있는 두 노드 간의 모든 경로 찾기
- 24. C++ 맵에서 그래프의 시작 노드 찾기
- 25. 다중 가장자리가있는 유향 그래프의 순환 열거
- 26. 두 노드 사이의 모든 경로를 찾으십시오.
- 27. 두 노드 사이의 모든 경로를 가져옵니다. neo4j
- 28. 알고리즘은 유향 그래프에
- 29. 이 알고리즘은 유향 그래프의 사이클을 올바르게 감지합니까?
- 30. 가중 가장자리와 유향 그래프 기븐 유향 그래프
이것은 너무 광범위합니다. 지금까지 시도한 것은 무엇입니까? –
"a"에 도달하면 DFS가 중단되지 않습니다. 그러나 "a"에 대한 경로가없는 "p"와 같은 노드를 포함합니다. 이미 이러한 노드를 포함하도록 그래프를 편집했습니다. – user3684042