如何在不遍历所有图的情况下找到导致某些其他节点的所有节点?(有向图)
有办法做这个吗?
是否有一些技术或算法可以帮助执行此任务而不必遍历所有图表?
更新
假设你的图有3条可以到达A的路径,你如何在不遍历所有图的情况下找到这3条路径?我不想要其中的一条路,而是所有的树。我来自关系数据库,在我看来,索引是索引,但是图表是不同的,所以我想问的是,是否有一种方法可以在不遍历所有图的情况下找到通向A的所有节点。或者在最坏的情况下,只遍历一次,然后我就可以查询结构中的路径。
从SQL的角度来看,这类似于:
SELECT nodes.id
FROM Graph
WHERE node.destination = "A";node.destination必须考虑到间接路径。
所以这就是我想要的。一种快速获取所有可以到达节点A的节点的方法
发布于 2020-05-15 23:22:17
懒惰的方式
如果您没有时间复杂度限制,我建议使用的懒惰方式。大多数garaph库,比如jgrapht,都实现了这个算法。您可以检查Dijkstra是否找到了从图中的每个节点到要检查的节点的(最短)路径。
发布于 2020-05-16 04:49:28
有许多搜索算法搜索路径,而不一定要遍历所有图:
这里可以找到更多的信息以及各种搜索算法的可视化演示。
编辑:
假设你的图有3条可以到达A的路径,你如何在不遍历所有图的情况下找到这3条路径?
如果您想要找到从节点A到节点B的所有路径,就必须研究整个图,因为您不知道哪条路径通向目标,哪条路径是死胡同。
发布于 2020-05-17 06:44:29
查找所有能导致给定目标节点的节点可能需要遍历完全图。图是否被遍历是邻接和选择目标节点的函数。
由于您对路径感兴趣,而不一定是最短的,因此可以使用DFS/BFS。您可以从目标节点和DFS/BFS开始,方法是跟踪传入边缘(而不是输出边缘)。根据您的查询,您只需要节点ids,而不是甚至路径,因此也不需要跟踪遍历序列。如果查询是重复出现的,并且图形邻接不太频繁的话,索引和缓存肯定会有所帮助。
https://stackoverflow.com/questions/61829392
复制相似问题