为什么使用 DFS 而不是 BFS 来查找图中的循环
DFS 主要用于查找图中的循环，而不是 BFS。有什么理由吗？两者都可以查找节点是否已经存在 遍历树/图时访问过。
Predominantly DFS is used to find a cycle in graphs and not BFS. Any reasons? Both can find if a node has already been
visited while traversing the tree/graph.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（13）
深度优先搜索比广度优先搜索更节省内存，因为您可以更快地回溯。如果使用调用堆栈，实现起来也更容易，但这依赖于不会溢出堆栈的最长路径。
此外，如果您的图表是有向，那么您不仅需要记住是否访问过某个节点，还有你是如何到达那里的。否则你可能会认为你已经找到了一个循环，但实际上你拥有的只是两条单独的路径 A->B，但这并不意味着存在一条路径 B->A。
< /a>
例如，
如果从
0开始进行BFS，它会检测到存在循环，但实际上没有循环。通过深度优先搜索，您可以在下降时将节点标记为已访问，并在回溯时取消标记。请参阅有关此算法的性能改进的评论。
对于有向图中检测循环的最佳算法 你可以看看Tarjan的算法。
Depth first search is more memory efficient than breadth first search as you can backtrack sooner. It is also easier to implement if you use the call stack but this relies on the longest path not overflowing the stack.
Also if your graph is directed then you have to not just remember if you have visited a node or not, but also how you got there. Otherwise you might think you have found a cycle but in reality all you have is two separate paths A->B but that doesn't mean there is a path B->A.
For example,
If you do BFS starting from
0, it will detect as cycle is present but actually there is no cycle.With a depth first search you can mark nodes as visited as you descend and unmark them as you backtrack. See comments for a performance improvement on this algorithm.
For the best algorithm for detecting cycles in a directed graph you could look at Tarjan's algorithm.
我不知道为什么这么老的问题会出现在我的提要中，但是之前的所有答案都很糟糕，所以...
DFS 用于在有向图中查找循环，因为它有效。
在 DFS 中，每个顶点都被“访问”，其中访问顶点意味着：
访问从该顶点可达的子图。这包括跟踪从该顶点可到达的所有未跟踪边，以及访问所有可到达的未访问顶点。
顶点完成。
关键特征是在顶点完成之前跟踪从顶点可到达的所有边。这是DFS的特点，而不是BFS的特点。事实上这就是DFS的定义。
由于这个特性，我们知道当循环中的第一个顶点开始时：
因此，如果存在环，那么我们就保证找到一条通往已开始但未完成的顶点的边（2），如果找到这样的边，那么就保证存在环（3）。
这就是为什么使用 DFS 来查找有向图中的循环。
BFS 不提供这样的保证，所以它不起作用。 （尽管有非常好的循环查找算法，包括 BFS 或类似的子过程）
另一方面，无向图只要任何一对顶点之间存在两条路径（即，当它不是树时）就有一个循环。这在 BFS 或 DFS 期间很容易检测到——追踪到新顶点的边形成一棵树，任何其他边都表示一个循环。
I don't know why such an old question popped up in my feed, but all the previous answers are bad, so...
DFS is used to find cycles in directed graphs, because it works.
In a DFS, every vertex is "visited", where visiting a vertex means:
The subgraph reachable from that vertex is visited. This includes tracing all untraced edges that are reachable from that vertex, and visiting all reachable unvisited vertexes.
The vertex is finished.
The critical feature is that all edges reachable from a vertex are traced before the vertex is finished. This is a feature of DFS, but not BFS. In fact this is the definition of DFS.
Because of this feature, we know that when the first vertex in a cycle is started:
So, if there is a cycle, then we are guaranteed to find an edge to a started-but-unfinished vertex (2), and if we find such an edge, then we are guaranteed that there is a cycle (3).
That's why DFS is used to find cycles in directed graphs.
BFS provides no such guarantees, so it just doesn't work. (notwithstanding perfectly good cycle-finding algorithms that include BFS or similar as a sub-procedure)
An undirected graph, on the other hand, has a cycle whenever there are two paths between any pair of vertexes, i.e., when it's not a tree. This is easy to detect during either BFS or DFS -- The edges traced to new vertexes form a tree, and any other edge indicates a cycle.
如果图是无向的，则 BFS 可能是合理的（请客座演示使用 BFS 的有效算法，该算法将报告有向图中的循环！），其中每个“交叉边”定义一个循环。如果交叉边为
{v1, v2}，并且包含这些节点的根（在BFS树中）为r，则循环为r ~ v1 - v2 ~ r（~是一条路径，-是一条边），几乎可以像在 DFS 中一样轻松报告。使用 BFS 的唯一原因是，如果您知道（无向）图将具有长路径和小路径覆盖（换句话说，深且窄）。在这种情况下，BFS 的队列需要的内存比 DFS 的堆栈要少（当然两者仍然是线性的）。
在所有其他情况下，DFS 显然是赢家。它适用于有向图和无向图，并且报告循环很简单 - 只需将任何后边连接到从祖先到后代的路径即可，你就得到了循环。总而言之，对于这个问题，比 BFS 更好、更实用。
A BFS could be reasonable if the graph is undirected (be my guest at showing an efficient algorithm using BFS that would report the cycles in a directed graph!), where each "cross edge" defines a cycle. If the cross edge is
{v1, v2}, and the root (in the BFS tree) that contains those nodes isr, then the cycle isr ~ v1 - v2 ~ r(~is a path,-a single edge), which can be reported almost as easily as in DFS.The only reason to use a BFS would be if you know your (undirected) graph is going to have long paths and small path cover (in other words, deep and narrow). In that case, BFS would require proportionally less memory for its queue than DFS' stack (both still linear of course).
In all other cases, DFS is clearly the winner. It works on both directed and undirected graphs, and it is trivial to report the cycles - just concat any back edge to the path from the ancestor to the descendant, and you get the cycle. All in all, much better and practical than BFS for this problem.
BFS 不适用于有向图寻找循环。将 A->B 和 A->C->B 视为图中从 A 到 B 的路径。 BFS 会说，沿着 B 被访问过的路径之一走完之后。当继续走下一条路径时，会说再次找到了标记的节点B，因此，存在一个循环。显然这里不存在循环。
BFS wont work for a directed graph in finding cycles. Consider A->B and A->C->B as paths from A to B in a graph. BFS will say that after going along one of the path that B is visited. When continuing to travel the next path it will say that marked node B has been again found,hence, a cycle is there. Clearly there is no cycle here.
如果将循环放置在树中的随机位置，则 DFS 往往会在覆盖大约一半树时遇到循环，并且有一半的时间它已经遍历了循环所在的位置，而一半的时间则不会（并且平均会在树的其余一半中找到它），因此它将平均评估树的大约 0.5*0.5 + 0.5*0.75 = 0.625 。
如果将循环放置在树中的随机位置，则只有在评估该深度的树层时，BFS 才会倾向于命中该循环。因此，您通常最终必须评估平衡二叉树的叶子，这通常会导致评估树的更多部分。特别是，有 3/4 的时间至少两个链接之一出现在树的叶子中，在这些情况下，您必须平均评估树的 3/4（如果有一个链接）或 7/树的 8 个（如果有两个），所以您已经达到了搜索 1/2*3/4 + 1/4*7/8 = (7+12)/32 = 21/32 = 的预期0.656... 的树，甚至没有增加搜索带有远离叶节点的循环的树的成本。
另外，DFS比BFS更容易实现。因此，除非您对循环有所了解，否则就可以使用它（例如，循环可能靠近您搜索的根，此时 BFS 会给您带来优势）。
If you place a cycle at a random spot in a tree, DFS will tend to hit the cycle when it's covered about half the tree, and half the time it will have already traversed where the cycle goes, and half the time it will not (and will find it on average in half the rest of the tree), so it will evaluate on average about 0.5*0.5 + 0.5*0.75 = 0.625 of the tree.
If you place a cycle at a random spot in a tree, BFS will tend to hit the cycle only when it's evaluated the layer of the tree at that depth. Thus, you usually end up having to evaluate the leaves of a balance binary tree, which generally results in evaluating more of the tree. In particular, 3/4 of the time at least one of the two links appear in the leaves of the tree, and on those cases you have to evaluate on average 3/4 of the tree (if there is one link) or 7/8 of the tree (if there are two), so you're already up to an expectation of searching 1/2*3/4 + 1/4*7/8 = (7+12)/32 = 21/32 = 0.656... of the tree without even adding the cost of searching a tree with a cycle added away from the leaf nodes.
In addition, DFS is easier to implement than BFS. So it's the one to use unless you know something about your cycles (e.g. cycles are likely to be near the root from which you search, at which point BFS gives you an advantage).
当您想要找到有向图中包含给定节点的最短循环时，您必须使用 BFS。
例如：
如果给定节点为 2，则它属于三个循环 -
[2,3,4]、[2,3, 4,5,6,7,8,9]&[2,5,6,7,8,9]。最短的是[2,3,4]为了使用 BFS 实现此目的，您必须使用正确的数据结构显式维护访问节点的历史记录。
但对于所有其他目的（例如：找到任何循环路径或检查循环是否存在），由于其他人提到的原因，DFS 是明确的选择。
You'll have to use
BFSwhen you want to find the shortest cycle containing a given node in a directed graph.Eg:
If the given node is 2, there are three cycles where it is part of -
[2,3,4],[2,3,4,5,6,7,8,9]&[2,5,6,7,8,9]. Shortest is[2,3,4]For implementing this using BFS, you have to explicitly maintain history of visited nodes using proper data structures.
But for all other purposes (eg: to find any cyclical path or to check if a cycle exists or not),
DFSis the clear choice for reasons mentioned by others.要证明图是循环的，您只需证明它有一个循环（直接或间接指向自身的边）。
在 DFS 中，我们一次获取一个顶点并检查它是否有循环。一旦找到循环，我们就可以省略检查其他顶点。
在 BFS 中，我们需要同时跟踪许多顶点边，并且通常在最后发现它是否有循环。随着图的大小增长，与 DFS 相比，BFS 需要更多的空间、计算和时间。
To prove that a graph is cyclic you just need to prove it has one cycle(edge pointing towards itself either directly or indirectly).
In DFS we take one vertex at a time and check if it has cycle. As soon as a cycle is found we can omit checking other vertices.
In BFS we need to keep track of many vertex edges simultaneously and more often than not at the end you find out if it has cycle. As the size of the graph grows BFS requires more space, computation and time compared to DFS.
我发现BFS和DFS都可以用来检测循环。
有些问题提到BFS不能与有向图一起使用。我谦虚地不同意。
在BFS-Queue中，我们可以跟踪父节点列表/集合，如果再次遇到相同的节点（除了直接父节点），我们可以将其标记为一个循环。所以这样 BFS 也应该适用于有向图。
尽管与 DFS 相比，这会导致内存效率非常低，这就是我们主要使用 DFS 的原因。
I found that both BFS and DFS can be used to detect a cycle.
Some questions mentioned that BFS can not be used with directed graph. I humble disagree.
In BFS-Queue we can keep track of parent node list/set, and if the same node is encountered again(except immediate parent) we can mark it a cycle. So this way BFS should work with directed graph also.
Although this will be highly memory inefficient in comparison to DFS and that is the reason we mainly use DFS.
这在某种程度上取决于您是在谈论递归还是迭代实现。
递归 DFS 访问每个节点两次。迭代 BFS 访问每个节点一次。
如果要检测循环，则需要在添加邻接之前和之后调查节点 - 无论是在节点“开始”时还是在节点“结束”时。
这需要迭代 BFS 做更多的工作，因此大多数人选择递归 DFS。
请注意，使用 std::stack 进行迭代 DFS 的简单实现与迭代 BFS 具有相同的问题。在这种情况下，您需要将虚拟元素放入堆栈中以跟踪您何时“完成”节点上的工作。
有关迭代 DFS 如何需要额外工作来确定何时“完成”节点的更多详细信息，请参阅此答案（在 TopoSort 的上下文中回答）：
使用不带递归的 DFS 进行拓扑排序
希望这可以解释为什么人们在需要确定何时“完成”处理节点的问题时青睐递归 DFS。
It sort of depends if you are talking about recursive or iterative implementations.
Recursive-DFS visits every node twice. Iterative-BFS visits every node once.
If you want to detect a cycle, you need to investigate the nodes both before and after you add their adjacencies -- both when you "start" on a node and when you "finish" with a node.
This requires more work in Iterative-BFS so most people choose Recursive-DFS.
Note that a simple implementation of Iterative-DFS with, say, std::stack has the same problem as Iterative-BFS. In that case, you need to place dummy elements into the stack to track when you "finish" working on a node.
See this answer for more details on how Iterative-DFS requires additional work to determine when you "finish" with a node (answered in the context of TopoSort):
Topological sort using DFS without recursion
Hopefully that explains why people favor Recursive-DFS for problems where you need to determine when you "finish" processing a node.
您可以使用两者中的任何一个来完成任务。
但很多人更喜欢 DSF，因为它有助于进一步的图算法，而且 DFS 也易于实现。
与 BFS 相比，DFS 也是空间优化的方式。但这完全取决于你的选择。
you can use either of one both are able to do task.
but many people more prefer DSF because it help in further graph algorithms and also DFS in easy to implement.
also DFS is space optimized way compare to BFS. but it's totally depend on you what you choose.
我认为这个问题的答案很简单。
如果你比较一些显示 dfs 和 bfs 的东西。
那么你就明白为什么我们使用 dfs 而不是 bfs 来进行循环检测了。
首先，内存效率 DFS 通常比 BFS 需要更少的内存，因为它只需要存储从根到当前节点的路径，而 BFS 需要存储当前正在探索的整个节点级别。
算法的实现也很重要，DFS 通常比 BFS 更容易实现，尤其是递归形式。当检测到循环时，在 DFS 中回溯会更容易。
DFS 在深入探索图形时本质上会检测循环。当它遇到以前访问过的节点时，如果该节点不是遍历中的直接父节点，它就知道存在循环。
空间也很重要，虽然两种算法对于循环检测具有相同的最坏情况时间复杂度（O(V+E)，其中 V 是顶点数，E 是边数），
但 DFS 通常具有更好的空间复杂度，因为它不需要像 BFS 那样存储每个级别的所有节点。
我们还可以使用 BFS 进行循环检测，所有事物都有其 2 面。
根据您的要求，您选择那个东西。就像在这个例子中，
DFS 通常用于内存受限的场景或图太大而无法容纳的情况。
一般来说，这种优势会投票给 DFS 来代替 BFS 来进行循环检测。
I Think this question answer is easy.
if you compare some things that show dfs Vs bfs.
then you got it why we use dfs and not bfs for cycle detection.
First, Memory Efficiency DFS usually requires less memory than BFS because it only needs to store the path from the root to the current node, whereas BFS needs to store the entire level of nodes currently being explored.
Implementation of Algorithm also matter, DFS is often simpler to implement than BFS, especially in recursive form. It's easier to backtrack in DFS when a cycle is detected.
DFS inherently detects cycles as it explores deeper into the graph. When it encounters a previously visited node, it knows that there's a cycle if that node is not the direct parent in the traversal.
Space also matter, While both algorithms have the same worst-case time complexity for cycle detection (O(V+E) where V is the number of vertices and E is the number of edges),
BUT DFS generally has better space complexity because it doesn't need to store all the nodes at each level like BFS does.
We Can also do Cycle detection using BFS, all thing have it's 2 side.
based on your requirements you select that thing. like in this case,
DFS is often used in scenarios where memory is a constraint or when the graph is too large to fit.
Generally this advantages vote to DFS to use for cycle detection instead of BFS.
DFS 是比 bfs 更优化的方法。
DFS is optimized approach then bfs.