广度优先与深度优先类似吗? - Mario

20-11-01 banq

主要的两个图遍历算法:

  • -广度优先搜索(BFS)
  • -深度优先搜索(DFS)

您知道它们本质上是相同的算法吗?主要区别在于:BFS使用队列,而DFS使用堆栈。

基础数据结构完全更改遍历顺序。

 

最初,它们看起来完全不同,因为DFS通常是通过递归实现的。但是,如果您使用堆栈来迭代实现,那么您会意识到它几乎与BFS完全相同 

 

这两个例子很好地说明了数据结构的巧妙用法!令人难以置信的是,两种行为看起来如此不同的算法实际上是相同的,只是使用了不同的数据结构。

 

BFS和DFS就像是更通用的“模板”(可以这么说),但是您可以在算法的每个步骤上做额外的工作和保持值以解决特定问题(例如Dijkstra和Minimum的最短路径)如果是Prim's,则为生成树)。

 

         

猜你喜欢