行走有向图
我有一个有向无环图，在该图中有一个原点v。
我如何访问从v可达的所有顶点，这样，如果我访问v1，我就已经访问了所有有v1的顶点了？
示例：
/-----V
A->B->C
从a开始，必须在B之后访问C。
我尝试只执行一个BFS并检查每个顶点的父级，如果没有访问它们，则稍后重新添加它，但这证明太慢了，我相信可以是O(V^2)。
知道图是二进制的可能会有帮助，每个顶点将被最多两个顶点指向。在另一个方向上，每个顶点指向很多顶点。
共有1个答案
您可能正在寻找拓扑排序。
首先做一个拓扑排序，根据这个排序得到图中顶点的顺序，设为v1,v2,...,vn。
使用BFS，您可以只保留可从v到达的顶点（过滤掉其他顶点），并按照拓扑排序的顺序迭代它们。
这是O(V+E)，在您的情况下是O(V)（松弛每个顶点将被最多两个顶点指向建议E<=2V，因此O(V+E)<=OV+2V)=O(3V)=O(V)
-
我正在使用google maps api V2开发一个android应用程序。问题是谷歌地图显示的方向取决于道路路线，即使它是一个空地。例如，以这两个LatLng LatLng1:-33.891143,151.224473 LatLng2:-33.891580,151.225336 有什么办法可以做到这一点吗？提前致谢
-
我的游戏循环中有以下代码： 它做它应该做的事情：当你按下A时，它逆时针转动。按D键时，它会顺时针转动。当你按W时，它向前，当你按S时，它向后。然而，如果我拿着W和D，一开始它会像应该的那样绕一个圈，但它会慢慢地开始向左上角的方向移动。我该怎么解决这个问题？
-
2006年，GNOME与KDE都站在一个全新的起点，获得商业公司和更多自由程序员支持的GNOME踌躇满志，将超越的目光放在Mac OSX系统。也许你认为WindowsVista的半透明和三维界面将Linux远远抛在后面，那么我们告诉你这是绝对的误解，GNOME目前已经可以实现类似的效果，Novell在前几个月就向外界作过详细的演示。当前的KDE也可支持相当不错的半透明和阴影特效，技术上毫不落后于G
-
问题内容： 我正在尝试转换为。当您有许多异步任务并且需要获得所有异步任务的结果时，这非常有用。 如果它们中的任何一个失败，那么最终的未来将失败。这就是我实现的方式： 要运行它： 如果其中任何一个失败，则失败。即使有一百万个期货，它也能提供预期的输出。我的问题是：假设如果有超过5000个期货，并且其中任何一个失败，我都会得到： java.util.concurrent.CompletableFutu
-
我正准备将Neo4j社区实例转换为Neo4j Enterprise上的HA设置。 谢谢
-
有一个有趣的游戏叫一个人游戏。它在网格上播放。每个网格单元格中都有一个非负整数。你从0分开始。不能输入含有整数0的单元格。你可以在你想要的任何单元格开始和结束游戏（当然单元格中的数字不能是0）。在每一步中，您可以向上、向下、向左和向右移动到相邻的网格单元格。你最后能得到的分数是你路径上的数字之和。但每个单元格最多只能输入一次。 游戏的目的是让你的分数尽可能高。 输入: 第一行输入是一个整数测试用例