首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何在不遍历所有图(有向图)的情况下找到导致节点A的节点

问如何在不遍历所有图(有向图)的情况下找到导致节点A的节点
EN

Stack Overflow用户
提问于 2020-05-15 22:33:27
回答 3查看 700关注 0票数 1

如何在不遍历所有图的情况下找到导致某些其他节点的所有节点?(有向图)

有办法做这个吗?

是否有一些技术或算法可以帮助执行此任务而不必遍历所有图表?

更新

假设你的图有3条可以到达A的路径,你如何在不遍历所有图的情况下找到这3条路径?我不想要其中的一条路,而是所有的树。我来自关系数据库,在我看来,索引是索引,但是图表是不同的,所以我想问的是,是否有一种方法可以在不遍历所有图的情况下找到通向A的所有节点。或者在最坏的情况下,只遍历一次,然后我就可以查询结构中的路径。

从SQL的角度来看,这类似于:

代码语言:javascript
复制
SELECT nodes.id 

FROM Graph 

WHERE node.destination = "A";

node.destination必须考虑到间接路径。

所以这就是我想要的。一种快速获取所有可以到达节点A的节点的方法

EN

回答 3

Stack Overflow用户

发布于 2020-05-15 23:22:17

懒惰的方式

如果您没有时间复杂度限制,我建议使用的懒惰方式。大多数garaph库,比如jgrapht,都实现了这个算法。您可以检查Dijkstra是否找到了从图中的每个节点到要检查的节点的(最短)路径。

票数 1
EN

Stack Overflow用户

发布于 2020-05-16 04:49:28

有许多搜索算法搜索路径,而不一定要遍历所有图:

  • DFS是一个简单的。它找到的路不一定是最短的。
  • BFS也很简单,可以找到最短的路径。
  • Dijkstra是一种增强的BFS,它能找到最短的路径,并且比BFS更容易横向移动。
  • A*是一种增强的Dijkstra,它能找到最短的路径,并且比Dijkstra更容易横越更少的节点。

这里可以找到更多的信息以及各种搜索算法的可视化演示。

编辑:

假设你的图有3条可以到达A的路径,你如何在不遍历所有图的情况下找到这3条路径?

如果您想要找到从节点A到节点B的所有路径,就必须研究整个图,因为您不知道哪条路径通向目标,哪条路径是死胡同。

票数 1
EN

Stack Overflow用户

发布于 2020-05-17 06:44:29

查找所有能导致给定目标节点的节点可能需要遍历完全图。图是否被遍历是邻接和选择目标节点的函数。

由于您对路径感兴趣,而不一定是最短的,因此可以使用DFS/BFS。您可以从目标节点和DFS/BFS开始,方法是跟踪传入边缘(而不是输出边缘)。根据您的查询,您只需要节点ids,而不是甚至路径,因此也不需要跟踪遍历序列。如果查询是重复出现的,并且图形邻接不太频繁的话,索引和缓存肯定会有所帮助。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/61829392

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档