我想要查找DAG中两个节点之间的路径数。 O(V^2)和O(V + E)是可接受的。 O(V + E)提醒我以某种方式使用BFS或DFS,但我不知道如何使用BFS或DFS,但我不知道如何使用BFS或DFS。 有人可以帮忙吗?DAG中两个节点之间的路径数
10
A
回答
17
做一个拓扑排序的DAG,然后将目标的顶点向后扫描到源。对于每个顶点v
,保留从v
到目标的路径数量。当你到达源头时,计数值就是答案。那是O(V+E)
。
6
从节点u到v的不同路径的数量是从节点x到v的不同路径的总和,其中x是u的直接后裔。
存储每个节点(临时设置为0)的目标节点v的路径数量,使用相反方向从v(此处值为1)开始,并为每个节点重新计算此值(将所有子节点的值)直到你到达你。
如果按拓扑顺序处理节点(又是相反的方向),则可以保证在访问给定节点时已经计算了所有直接后代。
希望它有帮助。
相关问题
- 1. 如何查找DAG中两个顶点之间的最大权重路径?
- 2. 两个节点之间的最短路径数
- 3. 查找两个顶点(节点)之间的所有路径
- 4. 搜索XQuery中两个图形节点之间的路径
- 5. Neo4j:找到两个节点之间有多个路径
- 6. GraphViz,找到两个节点之间的最短路径
- 7. 查找两个节点之间的所有路径
- 8. 在两个节点之间创建专用路径的算法
- 9. 使用BFS查找两个节点之间的所有路径
- 10. 使用DFS查找两个节点之间的所有路径
- 11. 两个图形节点之间的固定长度路径
- 12. 找到任意两个节点之间最长的路径
- 13. 诱导子图;两个节点之间的路径存在
- 14. xquery - BFS查找两个节点之间的所有路径
- 15. Neo4j - 如何找到两个节点之间的最短路径
- 16. 计算DAG中通过节点的最短路径数
- 17. 复制一个节点路径 - CYPHER(查询两个节点之间的所有路径)
- 18. 查找图中两个节点之间固定跳数的最短路径
- 19. 两点之间最长的路径
- 20. 绘制两点之间的路径
- 21. 基于不同条件的图中两个节点之间的最短路径
- 22. 如何找到两个节点之间的循环图中最长的路径?
- 23. 获取两个节点之间的路径并使用它来匹配两个其他类型的节点
- 24. 如何确保两个节点之间的路径通过中间节点的所有连接?
- 25. 未加权图/树中两个给定节点之间的最短路径
- 26. 如何找到Lisp中两个节点之间最长的路径?
- 27. 图中任意两个节点之间的最长最短路径
- 28. 使用BFS和DFS查找图表中两个节点之间的路径
- 29. 查找大图中两个节点之间的所有可能路径
- 30. 找到Tinkerpop中两个节点之间最短路径的最佳方法3.1
这是功课吗? – 2011-03-02 07:57:52
这应该转向理论 – 2013-03-28 18:13:50