一,DFS
DFS算法(深度优先搜索算法)是一种用于遍历或搜索树或图的算法。
深度优先搜索(DFS)算法的递归版本框架如下:
1,创建一个集合 S,用于存储已经访问过的节点。树或是无环图则无需集合S。
2,传入起始node,进入dfs函数
3,先判断node是否被访问过,如果被访问过,直接返回。
4,将当前node保存到集合 S中。
5,如果当前结点不是目标结点,则递归搜索每个相连结点。
6,叶子结点递归结束,回溯到当前结点的上一个结点,并继续搜索其未访问的相邻结点。
7,重复步骤5和6,直到所有结点被访问或是找到目标结点。
以下是使用C++语言的DFS递归框架示例:
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
void dfs(vector<vector<int>>& graph, int start, unordered_set<int>& visited)
{
if (visited.find(neighbor) != visited.end()) { // node被访问过,直接return
return;
}
visited.insert(start); // 标记为已访问
cout << start << " "; // 输出访问的节点
for (int neighbor : graph[start]) {
dfs(graph, neighbor, visited); // 递归调用dfs函数
}
}
int main() {
vector<vector<int>> graph = {
{1, 2}, {3}, {3}, {}};
unordered_set<int> visited;
dfs(graph, 0, visited); // 从节点0开始进行深度优先搜索
return 0;
}
二,BFS
广度优先搜索(BFS)是一种用于遍历或搜索树或图的算法。这种算法从根节点开始,探索最近的节点,然后逐渐向外探索。BFS 是一种相对简单和直观的算法,其基本思想如下:
1. 创建资源,一个队列 Q,并将起始节点放入队列中; 一个集合 S,用于存储已经访问过的节点。
2,传入起始node,进入bfs函数,并将其添加到队列 Q中和集合S中。
3. 当队列非空时,从队列中取出一个节点,并检查该节点。如果该节点是目标节点,那么算法结束。
4. 如果该节点不是目标节点,则将该节点的所有未访问的邻居节点添加到队列中。
5. 将这些邻居节点添加到集合 S 中,以确保它们只被访问一次。
6. 重复步骤 3-5,直到队列为空。
使用 C++ 实现的 BFS 算法框架:
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_set>
using namespace std;
// 假设图使用邻接列表表示
vector<vector<int>> adjList;
void bfs(int startNode)
{
// 创建一个集合来存储已访问的节点
unordered_set<int> visited;
// 创建一个队列并将起始节点放入队列中
queue<int> q;
q.push(startNode);
visited.insert(startNode);
while (!q.empty()) {
int currentNode = q.front();
q.pop();
cout << currentNode << " "; // 处理当前节点(这里简单地打印了节点)
// 将所有未访问的邻居节点添加到队列中
for (int neighbor : adjList[currentNode]) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
q.push(neighbor);
}
}
}
}