如何在不遍历所有图形的情况下找到通向某些其他节点的所有节点？(有向图(
有没有办法做到这一点？
是否有技术或算法可以帮助执行此任务而无需遍历所有图形？
更新
想象一下，你的图有 3 条可以到达 A 的路径，你如何在不遍历所有图的情况下找到这 3 条路径？我不想要其中一条路，而是所有的树。我来自关系数据库，我想到的是索引，但图形是不同的，所以我问是否有办法在不遍历所有图形的情况下找到导致 A 的所有节点。或者在最坏的情况下只遍历一次，从那里我可以查询路径的结构。
在SQL术语中，它类似于：
SELECT nodes.id
FROM Graph
WHERE node.destination = "A";
node.destination 必须考虑间接路径。
所以这就是我想要的。 获取所有可以到达节点 A 的节点的快速方法
懒惰的方式
如果你没有时间复杂度限制，我建议使用Dijkstra-Algorithmus的懒惰方式。大多数 garaph 库，如 jgrapht，都实现了这个算法。您可以检查 Dijkstra 是否找到从图形中的每个节点到您要检查的节点的(最短(路径。
有许多搜索算法可以搜索路径，而不必遍历所有图形：
- DFS很简单。它找到的路径不一定是 最短的一个。
- BFS也很简单，可以找到最短的路径。
- Dijkstra，是一个增强的BFS，它找到最短的 路径，并且可能比BFS横跨的节点更少。
- A* 是一个 增强的Dijkstra，它找到最短的路径，并且很可能 横向节点比Dijkstra少。
更多信息以及各种搜索算法的可视化演示可以在这里找到。
编辑：
想象一下，你的图有 3 条可以到达 A 的路径，你如何在不遍历所有图的情况下找到这 3 条路径？
如果要查找从节点 A 到节点 B 的所有路径，则必须探索整个图形，因为您不知道哪条路径通向目标，哪条路径是死胡同。
查找所有可能导致给定目标节点的节点可能涉及遍历完整的图形。是否遍历完整图是邻接和所选目标节点的函数。
由于你对路径感兴趣，不一定是最短的，你可以使用DFS/BFS。您可以从目标节点和 DFS/BFS 开始，方法是跟踪传入边(而不是出出边(。根据您的查询，您只需要节点 ID 甚至不需要路径，因此也不需要跟踪遍历序列。如果查询是重复的，并且图形邻接关系不会经常更改，则索引和缓存绝对会有所帮助。