我理解DFS和BFS之间的区别,但是我很想知道何时使用一个比另一个更实用？
任何人都可以举例说明DFS如何胜过BFS,反之亦然？
algorithm graph-theory breadth-first-search depth-first-search graph-algorithm
遍历树/图时,广度优先和深度之间的区别首先是什么？任何编码或伪代码示例都会很棒.
algorithm breadth-first-search tree-traversal depth-first-search
主要是DFS用于在图中找到循环而不是BFS.有什么原因？两者都可以在遍历树/图时查找是否已访问过节点.
algorithm tree graph breadth-first-search depth-first-search
我编写了一个递归DFS算法来遍历图:
void Graph<E, N>::DFS(Node n)
{
std::cout << ReadNode(n) << " ";
MarkVisited(n);
NodeList adjnodes = Adjacent(n);
NodeList::position pos = adjnodes.FirstPosition();
while(!adjnodes.End(pos))
{
Node adj = adjnodes.ReadList(pos);
if(!IsMarked(adj))
DFS(adj);
pos = adjnodes.NextPosition(pos);
}
}
然后我用堆栈编写了迭代DFS算法:
template <typename E, typename N>
void Graph<E, N>::IterativeDFS(Node n)
{
Stack<Node> stack;
stack.Push(n);
while(!stack.IsEmpty())
{
Node u = stack.Read();
stack.Pop();
if(!IsMarked(u))
{
std::cout << ReadNode(u) << " ";
MarkVisited(u);
NodeList adjnodes = Adjacent(u);
NodeList::position pos = adjnodes.FirstPosition();
while(!adjnodes.End(pos))
{
stack.Push(adjnodes.ReadList(pos));
pos = adjnodes.NextPosition(pos);
}
} …为什么BFS和DFS O(V + E)的运行时间,特别是当有一个节点具有可以从顶点到达的节点的有向边时,就像在以下站点中的此示例中一样
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm
graph breadth-first-search time-complexity depth-first-search data-structures
请注意,图表表示为邻接列表.
我听说有两种方法可以在图表中找到一个循环:
保留一个布尔值数组,以跟踪您之前是否访问过某个节点.如果你的新节点用完了(没有点击你已经存在的节点),那么只需回溯并尝试不同的分支.
来自Cormen的CLRS或Skiena的那个:对于无向图中的深度优先搜索,有两种类型的边,树和背.当且仅当存在后沿时,该图具有循环.
有人可以解释一下图的后边缘是什么,以及上述两种方法之间的差异是什么.
谢谢.
更新: 这是在两种情况下检测周期的代码.Graph是一个简单的类,为了简单起见,将所有图形节点表示为唯一编号,每个节点都有其相邻的相邻节点(g.getAdjacentNodes(int)):
public class Graph {
private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};
public int[] getAdjacentNodes(int v) {
return nodes[v];
}
// number of vertices in a graph
public int vSize() {
return nodes.length;
}
}
用于检测无向图中的循环的Java代码:
public class DFSCycle {
private boolean marked[];
private int s;
private Graph g;
private boolean hasCycle;
// s - starting node
public DFSCycle(Graph g, int s) {
this.g = g;
this.s = …我一直在阅读有关迭代深化的内容,但我不明白它与深度优先搜索的区别.
我知道深度优先搜索越来越深入.
在迭代深化中,您建立一个级别的值,如果该级别没有解决方案,则递增该值,然后从头开始(根).
这不会与深度优先搜索相同吗？
我的意思是你会继续增加和增加,直到找到解决方案.我认为这是同样的事情!我会走同一个分支,因为如果我从头开始,我会像以前一样走下同一个分支.
algorithm search artificial-intelligence depth-first-search iterative-deepening
好吧,我花了很多时间在这个问题上.但是,我只能找到树的非递归方法的解决方案:树的非递归,或图的递归方法,图的递归.
许多教程(我不在这里提供这些链接)也没有提供方法.或者教程完全不正确.请帮我.
更新:
这很难描述:
如果我有一个无向图:
1
/ | \
4 | 2
3 /
1-- 2-- 3 - 1是一个循环.
在这一步: push the neighbors of the popped vertex into the stack
WHAT'S THE ORDER OF THE VERTEXES SHOULD BE PUSHED?
如果推送的顺序是2 4 3,则堆栈中的顶点是:
| |
|3|
|4|
|2|
_
弹出节点后,我们得到了结果:1 - > 3 - > 4 - > 2而不是1 - > 3 - > 2 - > 4.
这是不正确的.我应该添加什么条件来阻止这个场景？
通常认为A*是解决寻路问题的最佳算法.
当A*不是找到解决方案的最佳算法时,是否存在任何情况？
与BFS,DFS,UCS等相比,A*有多好？
无论是使用堆栈还是DFS或BFS的队列,我总是混淆.有人可以提供一些关于如何记住哪种算法使用哪种数据结构的直觉？