数据结构中的图搜索

我们知道图是一种非线性数据结构。在这种数据结构中，我们将一些值放入节点中，并且节点通过不同的边连接起来。由于我们可以将数据存储到图结构中，我们也需要从图中搜索元素才能使用它们。

对于图搜索，有两种不同的方法：广度优先搜索和深度优先搜索技术。

广度优先搜索 (BFS)

广度优先搜索 (BFS) 遍历是一种用于访问给定图的所有节点的算法。在此遍历算法中，选择一个节点，然后逐个访问所有相邻节点。完成所有相邻顶点后，它将进一步检查另一个顶点并再次检查其相邻顶点。要实现此算法，我们需要使用队列数据结构。当所有相邻顶点都完成后，所有相邻顶点都添加到队列中，从队列中移除一个项目并再次开始遍历该顶点。

深度优先搜索 (DFS)

深度优先搜索 (DFS) 是一种图遍历算法。在此算法中，给定一个起始顶点，当找到一个相邻顶点时，它首先移动到该相邻顶点并尝试以相同的方式遍历。它尽可能地深入遍历，之后回溯以到达之前的顶点以查找新的路径。

要以迭代方式实现 DFS，我们需要使用堆栈数据结构。如果我们想递归地执行它，则不需要外部堆栈，可以使用内部堆栈进行递归调用。

更新于：2020年8月10日

2K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告