遍历图的两种最常见的方法是广度优先搜索和深度优先搜索.这两种搜索算法都遵循一个通用模板:
在广度优先搜索中,工作列表W实现为FIFO队列,而在深度优先搜索中,它是LIFO堆栈.如果W是优先级队列,则会获得统一成本搜索.
不久前,我问了一个关于从包中选择随机元素的数据结构的问题.如果您使用此随机包实现上述工作清单W,那么您将获得一个"随机优先搜索"算法,该算法从初始节点开始随机探索图中的节点.
我的问题是:有没有已知的算法使用这种类型的搜索？也就是说,是否有算法通过以这种方式生成图的随机生成树来工作？
random algorithm graph breadth-first-search depth-first-search
枚举任意图中两个顶点之间的所有简单路径通常需要指数时间,因为顶点之间可能存在指数个简单路径.但是,如果我们只对两个端点之间的至少一条简单路径上的顶点感兴趣呢？
那就是:给定一个无向图和两个不同的顶点,是否有一个多项式时间算法,它找到位于两个顶点之间的至少一条简单路径上的每个顶点？这与连接不同; 死胡同和死胡同被排除在外.但是,分支和连接路径是允许的.
我发现编写一个看起来像是解决了这个问题的算法非常容易,但在某些情况下要么失败,要么在病态情况下需要指数运行时间.
更一般地说:给定图中两个不相交的顶点集,是否存在多项式时间算法,该算法找到位于从一个集合中的顶点到另一个集合中的顶点的简单路径上的所有顶点？
(请原谅我,如果有一个非常明显的解决方案.当然感觉应该有.)
language-agnostic algorithm graph breadth-first-search depth-first-search
这里有一些伪代码(无视我的风格)
从v1开始(入队):
function BFS(queue Q)
v2 = dequeue Q
enqueue all unvisited connected nodes of v2 into Q
BFS(Q)
end // maybe minor problems here
由于图中有V个顶点,并且这些V顶点连接到E边,并且访问连接节点(相当于访问连接边)是在内部循环中(外部循环是递归本身),在我看来复杂性应该是O(V*E)而不是O(V + E).有人能为我解释一下吗？
我知道堆栈溢出中存在类似的问题,其中一个人问过,为什么BFS/DFS的时间复杂度不仅仅是O(V).
给出的适当答案是在完整图的情况下E可以与V ^ 2一样大,因此在时间复杂度中包括E是有效的.
但是,如果V不能大于E + 1.那么,在那种情况下,时间复杂度中没有V,应该有效吗？
graph breadth-first-search time-complexity depth-first-search
任何人都可以提供代码,伪代码,甚至提供在纯JavaScript(无JQuery或任何帮助库)中实现DFS和BFS的良好链接？我一直试图理解如何实现任一遍历,但我似乎无法真正区分BFS和DFS实现的区别.
如果我们想要一个具体问题作为一个例子:我想在给定节点遍历DOM,并获取所有类名.
(我能想到遍历的唯一方法是遍历每个父节点,从该节点得到我需要的东西,在这个例子中是类名,然后看看他们是否有孩子,为每个孩子递归.我相信这是DFS ？同样,我很难理解DOM遍历实现中的差异!)
最后,对不起,如果这是重复.我到处寻找好的,明确的例子,但没有找到任何好的答案!如果那里有一个很好的答案,请告诉我:)
javascript dom traversal breadth-first-search depth-first-search
关于深度优先搜索的维基百科:
深度优先搜索(DFS)是用于遍历或搜索树,树结构或图的算法.一个从根开始(在图形情况下选择一个节点作为根)并在回溯之前尽可能地沿着每个分支进行探索 .
那么什么是广度优先搜索？
"选择起始节点,检查所有节点回溯,选择最短路径,选择邻居节点回溯,选择最短路径,最终找到最佳路径的算法,因为由于连续回溯而遍历每条路径.
正则表达式find的修剪 - 回溯？
由于其使用的多样性,回溯一词令人困惑.UNIX find修剪SO用户解释了回溯.如果您不限制正则表达式的范围,Regex Buddy使用术语"灾难性回溯".它似乎是一个过于广泛使用的伞形术语.所以:
[添加]
关于回溯和示例的良好定义
我要做的是计算使用最短路径到达目标需要多少动作.必须使用广度优先搜索来完成.我将8x8网格放入一个2d数组,其中填充了四个字符之一,E表示空(可以移动到这些点),B表示阻塞(无法移动到此处),R表示机器人(起始点)或G为了目标.该算法必须按顺序向上,向左,向右,然后向下检查可移动空间,我相信我已经正确完成了.检查节点后,它将其内容更改为"B".如果无法达到目标,则应返回0.
我已经改变了我的代码来实现Kshitij告诉我的内容,并且它的工作非常精彩.我太累了,看不到我在每个新数据集后都没有初始化我的队列.谢谢您的帮助!
public static int bfSearch(){
Queue <int []> queue = new LinkedList <int []> ();
int [] start = {roboty,robotx,0};
queue.add(start);
while (queue.peek() != null){
int [] array = queue.remove();
if(array[0]-1 >= 0 && grid[array[0]-1][array[1]] != 'B'){
if (grid[array[0]-1][array[1]] == 'G'){
return array[2]+1;
}
else{
grid[array[0]-1][array[1]] = 'B';
int [] temp = {array[0]-1, array[1], array[2]+1};
queue.add(temp);
}
}
if(array[1]-1 >= 0 && grid[array[0]][array[1]-1] != 'B'){
if (grid[array[0]][array[1]-1] == 'G'){
return array[2]+1;
}
else{
grid[array[0]][array[1]-1] = 'B';
int [] temp …Can Breadth first Search可用于查找图中顶点和强连通组件的拓扑排序吗？
如果是的话怎么做？如果不是为什么不呢？
我们通常在这些问题中使用深度优先搜索,但如果我尝试使用BFS实现会有什么问题？
这样的代码会起作用吗？
def top_bfs(start_node):
queue = [start_node]
stack = []
while not queue.empty():
node = queue.dequeue()
if not node.visited:
node.visited = True
stack.push(node)
for c in node.children:
queue.enqueue(c)
stack.reverse()
return stack
在回溯中,我们使用bfs和dfs.Even在分支和绑定中我们使用bfs和dfs以及最低成本搜索.
所以我们何时使用回溯,何时使用分支和绑定
使用分支和绑定会减少时间的复杂性吗？
什么是分支机构中的最低成本搜索？
如果我错了,请纠正我
谢谢
breadth-first-search backtracking depth-first-search branch-and-bound
我想知道如何使用功能编程在Scala中实现广度优先搜索.
这是我的第一个不纯的代码:
def bfs[S](init: S, f: S => Seq[S], finalS: S => Boolean): Option[S] = {
val queue = collection.mutable.Queue[S]()
queue += init
var found: Option[S] = None
while (!queue.isEmpty && found.isEmpty) {
val next = queue.dequeue()
if (finalS(next)) {
found = Some(next)
} else {
f(next).foreach { s => queue += s }
}
}
found
}
虽然我只使用局部可变性(a var和可变Queue),但它不是纯粹的功能.
我想出了另一个版本:
case class State[S](q: Queue[S], cur: S)
def update[S](f: S => Seq[S])(s: State[S]) : State[S] …algorithm ×4
graph ×4
backtracking ×2
dom ×1
java ×1
javascript ×1
maze ×1
random ×1
scala ×1
traversal ×1