图的广度优先和深度优先遍历(bfs和dfs)

2020/10/04

图:一般作为一种模型来定义对象之间的关系和联系。对象由顶点(V)表示,而对象之间的关系或者关联则通过边(E)来表示。一般用G=(V,E) 来表示图

遍历算法包含广度优先搜索 (BFS) 和 深度优先遍历(DFS)

DFS(深度优先搜索)

深度优先搜索的步骤:1.递归下去 2回溯上来 。 顾名思义,深度优先是以深度为准则,先一条路走到底,知道达到目标。这里称之为递归下去

采用递归得形式,用到栈结构,先进后出

BFS(广度优先搜索)

广度优先搜索和深度优先得区别, 深度优先是一条路走到底,广度优先是面临一个路口时,把所有的岔路口都记下来。

BFS选取状态用队列得形式,先进先出

DFS适合目标确认,BFS适合大范围查找

参考:

搜索思想——DFS & BFS(基础基础篇)

Post Directory