有向图中的顶点，使得从这个顶点到每一个顶点都有一条路径
我怎样才能找到一个有向图中的所有顶点，这样每一个顶点都可以从这个顶点到达呢？现在我只能“发明”O(v^3)ALGO--从每个顶点得到一个DFS/BFS，但我确信，有一个更快的方法来解决这个问题。
谢谢你！
共有1个答案
运行强连通组件算法将图折叠为其强连通组件的有向无环图。必须至少有一个没有传入边的强连通组件。如果确实有一个，那么该组件中的节点就是您要查找的节点。如果有多个强连接的组件没有传入边，则不存在所有其他节点都可从其到达的节点。
-
下面的堆栈溢出问题 我尝试了在语句中使用两个重复的多个构造，但无法为每个起始顶点获得独立的。我也在使用平台，因此它限制了Gremlin的使用，其中不允许使用循环/脚本。所有gremlin查询必须以并由与链接在一起的命令组成 https://docs.aws.amazon.com/neptune/latest/userguide/access-graph-gremlin-differences.ht
-
枚举任意图中两个顶点之间的所有简单路径通常需要指数时间，因为顶点之间可能存在指数数量的简单路径。但是如果我们只对两个endpoint顶点之间至少一条简单路径上的顶点感兴趣呢？ 也就是说：给定一个无向图和两个不同的顶点，是否有多项式时间算法可以找到两个顶点之间至少一条简单路径上的每个顶点？这与连通性不同；不包括死胡同和死胡同。然而，分支和连接路径是允许的。 我发现编写一个看起来可以解决这个问题的算法
-
给定一些无向边加权图，什么算法可以用来找到从某个顶点v到另一个顶点w的最短路径？ 对于有向边加权图，可以使用Dijkstra的最短路径算法，但我使用的是无向图，所以它不起作用。 对于非边加权的图，可以使用广度优先搜索（BFS），但我使用的是边加权图，所以它不起作用。 既然它是无向和边加权的，一般最短路径法是什么？
-
一个简单的背景：我正在构建一个语义图，使用带有邻接表的BGL有向图： 我需要做的事情之一，是处理一个较小的图（子图）到我的主图。 暗示我的lambda捕获参数应该是一对（我猜是一个实际的边？）。 所以，我的问题是：我怎样才能发现在顶点的外边中是否存在类似的边呢？
-
所以我正在研究这个问题： 这是我目前所掌握的 首先，我想对我的答案再作核实。我对有向图不是那么熟悉，对算法的效率/复杂度也不是特别熟练。我想我做得对，但如果我需要的话，我想要一些帮助。我也在寻找任何想法，使它更有效率。这些是我脑海中最先出现的算法，所以我觉得可能有更好的方法来实现它。 谢谢
-
我对vert.x非常陌生，我有一个非常基本的问题:假设一个顶点包括一些顶点。通常说一个顶点是单线程的。这是否意味着，如果一个顶点正在被处理，那么属于同一顶点的另一个顶点将不得不等待，直到第一个顶点结束，然后它(另一个顶点)将能够开始它的工作？我的意思是在同一个顶点中的顶点之间没有上下文切换。