与其他算法相比,深度优先搜索是一个更好的解决方案,用于统计图中连接组件的数量?
问题描述:
我找过方法来计算没有。的在线连接组件。我注意到在大多数网站中,使用的算法是深度优先搜索。我相信你可以做到同样的事情广度优先搜索和联盟找到。那么为什么人们更喜欢使用DFS来查找连接组件的数量呢?与其他算法相比,深度优先搜索是一个更好的解决方案,用于统计图中连接组件的数量?
答
主要是因为两个原因:
- 它的简单和短期。没有数据结构是必需的(很好,我们需要一个堆栈,但递归处理)
- 它是内存友好型,Breath First Search的内存复杂度为
O(V)
(V
是节点数)。另一方面DFS有O(h)
(h
是递归树的最大深度)。
答
在复杂性方面它不会更好,因为在所有情况下,您只需访问一次节点。在内存使用方面,您将始终需要知道访问了哪些节点以及哪些节点已找到并且尚未访问。深度优先将在孩子的兄弟姐妹之前接受孩子节点并访问其后代,而宽度优先将在孩子之前拜访兄弟姐妹。深度优先是更短,更简单,可以说是更直观,这可能是其在教程,书籍和演示中比其他人更频繁选择的原因。
在很多情况下,要使用的堆栈是通过递归来处理的,但这不一定是个好主意,尤其是在大图的情况下。
我想你是在研究竞争性的编程资源。在那里,简单性赢了,DFS通常需要更少的代码。在现实世界中,它可能不是最好的解决方案。 –