-
0 votesanswersviews
凯文培根游戏的最短路径图遍历
我一直在尝试为流行的凯文培根游戏创建一个图形表示 . 我已经创建了图形和顶点类，但是在创建宽度第一搜索方法来遍历图形并找到从凯文培根到演员的最短路径时遇到了一些麻烦，并在路上打印出边缘 . 用户应该输入一个演员，程序应该找到从凯文培根到该演员的最短路径 . 然后用户将继续进入演员，并且将获取到该演员的最短路径，并打印出凯文培根数字，否则它将打印出来 . 有一个顶点和图表类 . 顶点类是一个字典，它... -
15 votesanswersviews
有效地找到大图中的最短路径
我正在寻找一种方法来实时找到巨大图形中节点之间的最短路径 . 它有数十万个顶点和数百万个边 . 我知道之前已经问过这个问题，我想答案是使用广度优先搜索，但我更感兴趣的是知道可以用什么软件来实现它 . 例如，如果已经存在用于在无向图中执行bfs的库（使用python绑定！），那将是完全完美的 . -
2 votesanswersviews
网格中的最短路径
我有一个二维矩阵 A......... ##....##.. .####...## .......... .......### B......... ####...### #...#.###. 其中' . ' represents path and ' # '代表墙 . 我必须找到从点 A 到点 B 的最短路径 . 我熟悉 BFS 算法，它似乎是一个合理的算法 . 但是我觉得在网格上应用... -
4 votesanswersviews
仅返回实际最短路径中的顶点
我知道 Headers 有点乱，但我不知道如何更好地解释它 . What I'm trying to do: 使用文本文件中的图形，找到并打印从顶点A到顶点B的最短路径（最小顶点数量） . 注意：使用广度优先搜索，而不是Dijkstra . What I've got: 一种在图上应用BFS的工作算法，但没有实际打印出最短路径的好方法 . 我很难 distinguishing a vertex i... -
7 votesanswersviews
迷宫解决广度优先搜索
有人可以解释我怎样才能使用广度优先搜索来解决迷宫问题？我需要使用广度优先搜索来找到迷宫中的最短路径，但我很困惑 . 这是我书中的伪代码： void breadth_first_search(tree T) { queue!; node u, v; initialize(Q); v = root of T; visit v; enqueue(Q, v); while ... -
3 votesanswersviews
Java-Maze广度优先搜索最短路径
我似乎在理解如何检索我正在实现的广度优先搜索算法发现的最短路径时遇到问题 . 目前，算法可以正常工作，因为它可以找到迷宫的出口，如果它可以到达它 . 在另一篇文章中，有人提到在节点被标记为已访问后保持对父进程的攻击 . 我尝试了一个简单的实现，试图通过在Point结构中包含一个父Point来跟踪父项，但是当我在Grid上标记路径时它标记了它迄今为止已经过去的所有路径，我相信我可能搞砸了以某种方式跟... -
0 votesanswersviews
从未加权的无向图计算具有精确长度l的边的另一图
什么是制作另一个图形的方法，该图形的特征是只能从原始未加权（假设边长度为1）和无向图 G=(V,E) 的每个顶点 V 获得边长为l的顶点 . 我想出了一个解决方案，它只使用每个顶点上的深度优先搜索来搜索每个分支中的每个分支，直到找到每个顶点的路径长度为l的所有顶点 . 这给出了 O(V^(l+1)) 的运行时间，所以当然，这不是最佳解决方案 . 任何人都可以帮助我找到一个更好的渐近运行时更好的解决... -
24 votesanswersviews
如何在有向图和线性时间中找到两个顶点之间不同最短路径的数量？
这是练习： 令v和w为有向图G =（V，E）中的两个顶点 . 设计线性时间算法以找到v和w之间的不同最短路径（不一定是顶点不相交）的数量 . 注意：G中的边缘未加权 对于这个消费税，我总结如下： 这是一个有向图 它要求 the number of different shortest paths . 首先，路径应该是最短的，然后可能存在不止一条这样的最短路径，其长度相同 .在v和w... -
1 votesanswersviews
在图中找到最少彩色的路径
我试图解决的问题是： 给定图G =（V，E）使得每个 edge 以10种颜色中的一种颜色和两个顶点着色：s，t . 我需要找到一种算法，它可以产生从s到t的（最短）路径，该路径可以通过最少量的颜色 . 我的想法是将图表复制10次： 第一个副本将仅包含一种颜色的边 第二个将仅包括两种颜色的边缘......依此类推 . 此外，我将外部节点：s'连接到每个副本中的每个“s”节点 . 但是，我已经想到，对... -
92 votesanswersviews
如果广度优先搜索（BFS）可以更快地做同样的事情，为什么要使用Dijkstra的算法？
两者都可用于从单一来源找到最短路径 . BFS在 O(E+V) 中运行，而Dijkstra在 O((V+E)*log(V)) 中运行 . 另外，我见过Dijkstra在路由协议中使用了很多 . 因此，如果BFS可以更快地做同样的事情，为什么要使用Dijkstra的算法呢？ -
1 votesanswersviews
从广度优先搜索转换到深度优先限制搜索
作为搜索算法的所有新手，我正在研究旧时尚8问题拼图的一个例子，我已经完成了广泛的第一个算法，它在下面的代码中，我想知道如何将它转换为深度第一个限制搜索 . 如何从广度优先算法转换为深度优先限制搜索算法？ 代码： class BFS { int[] GoalState = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; private Queue... -
6 votesanswersviews
在回溯方面解释BFS和DFS
Wikipedia about Depth First Search: 深度优先搜索（DFS）是用于遍历或搜索树，树结构或图的算法 . 一个从根开始（在图形情况下选择一个节点作为根）并在回溯之前尽可能地沿着每个分支进行探索 . So what is Breadth First Search? “选择起始节点的算法，检查所有节点回溯，选择最短路径，选择邻居节点回溯，选择最短路径，最终找到最佳路... -
0 votesanswersviews
广度和深度首先在具有返回边的图上搜索
我确实理解深度和广度优先搜索，但是这个图让我感到困惑，因为存在指向图中前面节点的节点 . 所以，让我们立即说 N 是一个目标状态，然后使用我们将拥有的深度优先搜索 A B E J K L F G M N 所以我们这样正确吗？我不重复 A ，因为它是在右边之前访问过的 . 使用广度优先搜索我会逐级进行，所以我会 A B C D E F G H I J K L M N 它是否正确 ？ 如果我们将目标状... -
0 votesanswersviews
深度优先搜索可能的节点
我试图找到一个可能的顺序，在执行深度优先搜索和广度优先搜索时可以访问给定的图节点 . 做深度首先搜索我得到FACBDE并做广度优先搜索我得到了FACDEB Please Click here to see the image但我不确定这是否是正确的答案 . 有人可以检查一下，告诉我我的答案是对的吗？ -
-1 votesanswersviews
Code Chef解决方案动态编程
这是代码厨师6月挑战问题（比赛已经结束） 厨师喜欢游戏！但他喜欢发明自己的 . 现在他玩游戏“数字跳” . Chef具有数字序列S1，S2，...，SN， . 他留在第一个数字（S1）并希望以最小的跳跃次数到达最后一个数字（SN） . 当保留在索引i（数字Si）的某个数字x时，Chef可以跳转到索引为i-1（Si-1）和i 1（Si 1）的数字，但是他不能跳出序列 . 或者他可以跳到任何具有相同... -
0 votesanswersviews
广度优先搜索可用于有向无环图吗？
可以在 Directed Acyclic Graph 上使用广度优先搜索吗？ 例如，你从根节点开始（假设它有3个连接的节点，边缘都从根指向它们），在BFS之后，你在有向边缘之后从根访问第一个连接节点，你必须回来到根节点并访问第二个连接节点，如果它是一个无向图，但你不能在有向图的情况下，所以我假设BFS不能用于有向无环图？ 此外，一行节点 1 -> 2 -> 3 -> 4 可以被认... -
25 votesanswersviews
深度优先搜索和广度优先搜索理解
我正在将俄罗斯方块作为一个有趣的侧面项目（不是家庭作业），并希望实现AI，以便计算机可以自己玩 . 我听说这样做的方法是使用BFS搜索可用的位置，然后创建最合理的放置位置的总分... 但我无法理解BFS和DFS算法 . 我学得最好的方法是把它画出来......我的图纸是否正确？ 谢谢！ -
23 votesanswersviews
广度优先搜索时间复杂度分析
遍历顶点的每个相邻边的时间复杂度是 O(N) ，其中N是相邻边的数量 . 因此，对于V个顶点，时间复杂度变为 O(V*N) = O(E) ，其中E是图中边的总数 . 由于从队列中删除和添加顶点是 O(1) ，为什么将它添加到BFS的总时间复杂度为 O(V+E) . -
12 votesanswersviews
随机优先搜索？
遍历图形的两种最常用方法是breadth-first search和depth-first search . 这两种搜索算法都遵循一个通用模板： 创建一个工作清单W，用起始节点s播种 . 虽然工作清单不是空的： 删除工作清单的第一个元素;叫它v . 如果未访问v： Mark v as visited . 对于直接连接到v的每个节点，将u添加到W. 在广度优先搜索中，工作... -
0 votesanswersviews
通过选择根节点来减小广度优先树的深度
如果可以在图形中随机选取根节点，是否存在选择根节点的现有算法，使得生成的广度优先树具有最小的深度或高度？ 我有一种预感，我应该选择具有最大扇出的节点作为根节点 . 让我举一个例子 . 有一个循环有向图{（0,1），（1,2），（1,5），（1,6），（2,3），（3,4），（4,2），（ 5,2），（6,0）} 如果节点0被选为根，则广度优先树为{（0,1），（1,2），（1,5），（1,6）... -
3 votesanswersviews
使用广度优先搜索从图中生成树？
我正在尝试使用广度优先搜索来创建一个（跨越）树自然地来自遍历图形（未定向和连接），但是我在修改算法时遇到了困难，因此它会生成一棵树 . 我正在使用Java . 这是我的BFS算法 . public void traverse(Node node){ Queue queue= new Queue(); node.visited= true; //Maybe do someth... -
2 votesanswersviews
在clojure中使用广度优先搜索的最短路径
我代表一棵树 A / \ B C /\ D E 像一个clojure矢量中的 [A [B [D] [E]] [C]] . 我需要使用广度优先搜索来找到目标的最短路径 . 我的实际矢量看起来像这样 - ["33L" ["32R" ["31L" ["30R" [false]] [&qu... -
1 votesanswersviews
图形与BFS和DFS树的等价性
我有这个问题，我无法证明 . 有人可以提供一些洞察这个问题 我们有一个连通图G =（V，E），并且作为特定顶点u∈V . 假设我们计算一个以u为根的深度优先搜索树，并获得一个包含G的所有节点的树T.假设我们然后计算以u为根的广度优先搜索树，获得相同的树T.证明G = T.（换句话说，如果T既是深度优先搜索树又是以u为根的广度优先搜索树，那么G不能包含任何不属于T的边 . ） -
149 votesanswersviews
广度优先与深度优先
遍历树/图时，广度优先和深度之间的区别首先是什么？任何编码或伪代码示例都会很棒 . -
8 votesanswersviews
广度优先或深度优先搜索
我知道这个算法是如何工作的，但是不能决定何时使用哪种算法？ 是否有一些指导方针，哪一个比其他或任何考虑更好？ 非常感谢 . -
4 votesanswersviews
在图中查找所有可能的路径
我正在寻找一些 algorithm ，这将帮助我在图表中找到 all possible 路径 . 到目前为止我发现的一切并不完全令人满意 . 让我们假设我们有一个像这样的图形（树）： 让我们使用像 Breadth-First Search 或 Depth-First Search 这样的算法 . 作为回报，我们会得到类似的东西 1, 2, 4, (2), 5, (2), 6, (2), (1),... -
9 votesanswersviews
如何在功能上生成树广度优先 . （使用Haskell）
假设我有以下Haskell树类型，其中“State”是一个简单的包装器： data Tree a = Branch (State a) [Tree a] | Leaf (State a) deriving (Eq, Show) 我还有一个函数“expand :: Tree a - > Tree a”，它接受一个叶子节点，并将它扩展为一个... -
246 votesanswersviews
什么时候使用深度优先搜索（DFS）与广度优先搜索（BFS）是否可行？
我理解DFS和BFS之间的区别，但我很想知道何时使用一个而不是另一个更实用？ 任何人都可以提供任何有关DFS如何胜过BFS的例子，反之亦然？ -
9 votesanswersviews
广度优先搜索Java中的8x8网格
我要做的是计算使用最短路径到达目标需要多少动作 . 必须使用广度优先搜索来完成 . 我将8x8网格放入一个2d数组，其中填充了四个字符之一，E表示空（可以移动到这些点），B表示阻塞（无法移动到这里），R表示机器人（起始点）或G为了目标 . 该算法必须按顺序向上，向左，向右，然后向下检查可移动空间，我相信我已经正确完成了 . 检查节点后，将其内容更改为“B” . 如果无法达到目标，则应返回0 . 我... -
0 votesanswersviews
为什么要为节点着色而不是在数据结构中跟踪它们？
我正在比较两本书之间的图形遍历材料：CLRS的算法导论，第3版（简称为CLRS）和RN的人工智能：现代方法，第3版（简称为AIMA） . 在广度优先搜索和深度优先搜索的两个部分中，我注意到CLRS通过分别对白色，灰色和黑色着色来跟踪未访问的节点，边界节点和访问节点，同时AIMA跟踪未访问的，边界和访问的通过跟踪图形及其节点外部的数据结构来跟踪边界和受访节点 . 似乎AIMA中使用数据结构来跟踪边界...