BFS在最短路径搜索中的性能
有一个最多有10,000个节点的图，每个节点最多可以有4个相邻节点。图是无权无向的。任务是寻找从节点A到节点B的最短路径，路径长度是路径中访问的节点数。BFS算法能在不到一秒钟的时间内找到路径并使用少于64MB的内存吗？
最初的问题是网格（最多100*100)和可以访问的地方，开始的地方，结束的地方，和不能访问的地方。我的第一个猜测是将其简化为使用BFS搜索在未加权图中寻找最短路径。但是，我不确定大图解决方案的速度和内存使用情况。
共有1个答案
空间复杂性
因此，您有10,000个节点，每个节点最多可以连接4个其他节点。顶点的最大数目是40000。在形容词列表中，它需要内存中的O(v+e)=50000空间。每个变量将需要32位来表示它在列表中。最大内存量为40000*32/(1000*1000*8)=0.16Mbytes。如果使用相邻矩阵，则需要O(v^2)=40000*40000/(1000*1000*8)=200Mbytes。
时间复杂度
维基百科：
在最坏的情况下，每个顶点和每个边都将被搜索，时间复杂度可用O(V+E)表示。注意：O(E)可能在O(V)和O(V^2)之间变化，这取决于输入图的稀疏程度（假设图是连通的）。
因此，在最坏的情况下，时间复杂度将是O(V+E)=40000+10000=50000。用一台现代计算机，在1秒内计算不成问题。
-
范围查询。将距离特定节点3跳以内的所有me节点（及其距离） 带来特定节点和一组节点之间的最短路径(BFS)距离（因为图是无向且未加权的）。 带来特定节点和所有其他图节点之间的最短路径(BFS)距离。 如果这些类型的查询实际上是可能的，没有递归类型实现，而是直接来自Cypher，那么我应该期望什么样的性能（几秒钟、几秒钟或几分钟）？
-
我试图通过一个节点图进行广度优先搜索遍历，然后我将尝试找到一个节点和另一个节点之间的最短距离。这就是维基百科的BFS算法： 我有自己的节点类，节点的距离设置为最大。我的版本基于第一个代码的风格： 我试图让这段代码也能找到一个节点和另一个节点之间的最短路径。例如 我如何修改BFS代码来实现这一点？如果在这个循环中是不可能的，那么还有什么其他的方法呢？ 如果我的代码或我的要求有任何混淆，请通知我。非常
-
我试图用BFS找到无向加权图的单源最短路径算法。 我想出了一个解决方案，将每个边权重转换成顶点之间的x边，每个新边权重为1，然后运行BFS。我会得到一棵新的BFS树，因为它是一棵树，所以从根节点到每个其他顶点只有1条路径。 我遇到的问题是试图对以下算法进行分析。每个边都需要访问一次，然后根据其权重划分为相应数量的边。然后我们需要找到新图的BFS。 访问每条边的成本是O（m），其中m是每一条边访问一
-
是否缺少配置设置？
-
问题内容： 我正在上图上进行广度优先搜索，以找到从到的最短路径。 我的密码 我需要跟踪BFS算法所经过的节点。遍历以到达节点6，例如。为此，我创建了一个名为＆的列表，并尝试存储所访问节点的先前节点，以获取节点列表。被推荐 但这似乎不起作用。最短的路径是 在列表中我得到的是 这是部分正确的，但可以提供额外的收益。 If I again start from the first element of
-
我正在上面的图上运行广度优先搜索，查找从到的最短路径。 我的代码 我需要追踪BFS ALGO通过的节点。遍历以到达节点6，如。为此，我创建了一个名为的列表&试图存储访问节点的前一个节点，以获得节点列表。转介