图论之常用算法

大家好，欢迎来到IT知识分享网。

• 💂 个人主页:风间琉璃
• 🤟 版权: 本文由【风间琉璃】原创、在CSDN首发、需要转载请联系博主
• 💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦

前言

提示：这里可以添加本文要记录的大概内容：

一、图的遍历

1️⃣深度优先搜索（dfs）

DFS深度优先搜索基本思想：

(1)访问顶点v；
(2)从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
(3)重复上述两步，直到图中所有和v有路径相通的顶点都被访问到。

 std::vector<std::vector<int>> graph; // 邻接矩阵，存储图 std::vector<bool> visited; // 访问标记数组，记录每个顶点是否被访问过 int n; // 顶点数量 // DFS函数 v当前处理的顶点 void dfs(int v) { 
       std::cout << v << ' '; // 输出当前访问的顶点 for (int i = 1; i <= n; ++i) { 
       // 遍历所有顶点 if (!visited[i] && graph[v][i]) { 
       // 如果顶点i未被访问，并且与顶点v有边连接 visited[i] = true; dfs(i); // 递归访问顶点i } } } 

邻接表DFS：

std::vector<std::vector<std::pair<int, int>>> edges; // 用于存储图的邻接表，每个顶点都有一个vector来存储与其相连的边 std::vector<bool> visited; // 用于标记顶点是否被访问过 int n, m; // 顶点数和边数 // DFS函数 void dfs(int v) { 
       std::cout << v << ' '; // 输出当前访问的顶点 for (const auto& edge : edges[v]) { 
       int w = edge.first; // 获取边的终点 pair ：{顶点，权重} if (!visited[w]) { 
       visited[w] = true; dfs(w); // 顶点v没有被访问则递归访问v } } } 

2️⃣广度优先搜索（bfs）

BFS广度优先搜索基本思想：

邻接矩阵BFS：

// BFS函数 void bfs(int v) { 
       std::queue<int> q; //定义队列，用于BFS遍历 q.emplace(v); // 访问顶点v, v emplace入队 visited[v] = true; while (!q.empty()) { 
       // 当队列不为空时继续遍历 v = q.front(); q.pop(); std::cout << v << ' '; // 输出队首元素 for (int i = 1; i <= n; ++i) { 
       if (!visited[i] && graph[v][i]) { 
       // 如果与v有边连接的顶点i未被访问  visited[i] = true; // 标记顶点i被访问 q.emplace (i); // 顶点i入队 } } } } 

邻接表BFS：

// BFS函数 void bfs(int v) { 
       std::queue<int> q; // 队列用于BFS q.emplace(v); // 起始点v入队 visited[v] = true; // 标记起始点v已经被访问 while (!q.empty()) { 
       int u = q.front(); q.pop(); std::cout << u << ' '; // 出队输出当前访问的节点  for (const auto& edge : edges[u]) { 
       // 遍历与顶点u相连的所有边 int w = edge.first; // 获取边的终点w if (!visited[w]) { 
       // 如果w没有被访问 visited[w] = true; q.emplace(w); // 将w入队 } } } } 

3️⃣回溯搜索算法

DFS回溯：

std::vector<std::vector<int>> result; std::vector<int> path; void backtracking(int x, int n){ 
       // x当前操作的点, n为操作节点的数量 if (path.size() == n) { 
       // 找到符合条件的一条路径 result.push_back(path); return; } for (int i = 1; i <= n; i++) { 
       // 遍历节点x链接的所有节点 if (graph[x][i] == 1 && !visited[i]) { 
       // 找到 x链接的节点 visited[i] = true; // 标记为已访问 path.push_back(i); // 遍历到的节点加入到路径中来 backtracking(i, n); // 进入下一层递归 path.pop_back(); // 回溯，撤销本节点 // visited[i] = false; // 回溯，撤销访问标记 可打印出所有路径 } } } 

邻接矩阵源程序：

#include <iostream> #include <cstring> #include <queue> /* 图邻接矩阵存储的遍历：DFS和BFS以及回溯算法 */ /* 请输入顶点数量： 4 输入邻接矩阵信息： 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 DFS遍历结果: 1 4 2 3 BFS遍历结果: 1 4 2 3 回溯结果： 1 4 2 3 */ std::vector<std::vector<int>> graph; // 邻接矩阵，存储图 std::vector<bool> visited; // 访问标记数组，记录每个顶点是否被访问过 int n; // 顶点数量 // DFS函数 v当前处理的顶点 void dfs(int v) { 
       std::cout << v << ' '; // 输出当前访问的顶点 for (int i = 1; i <= n; ++i) { 
       // 遍历所有顶点 if (!visited[i] && graph[v][i]) { 
       // 如果顶点i未被访问，并且与顶点v有边连接 visited[i] = true; dfs(i); // 递归访问顶点i } } } // 回溯算法 std::vector<std::vector<int>> result; std::vector<int> path; void backtracking(int x, int n){ 
       // x当前操作的点, n为操作节点的数量 if (path.size() == n) { 
       // 找到符合条件的一条路径 result.push_back(path); return; } for (int i = 1; i <= n; i++) { 
       // 遍历节点x链接的所有节点 if (graph[x][i] == 1 && !visited[i]) { 
       // 找到 x链接的节点 visited[i] = true; // 标记为已访问 path.push_back(i); // 遍历到的节点加入到路径中来 backtracking(i, n); // 进入下一层递归 path.pop_back(); // 回溯，撤销本节点 // visited[i] = false; // 回溯，撤销访问标记 可打印出所有路径 } } } // BFS函数 void bfs(int v) { 
       std::queue<int> q; //定义队列，用于BFS遍历 q.emplace(v); // 访问顶点v, v emplace入队 visited[v] = true; while (!q.empty()) { 
       // 当队列不为空时继续遍历 v = q.front(); q.pop(); std::cout << v << ' '; // 输出队首元素 for (int i = 1; i <= n; ++i) { 
       if (!visited[i] && graph[v][i]) { 
       // 如果与v有边连接的顶点i未被访问  visited[i] = true; // 标记顶点i被访问 q.emplace (i); // 顶点i入队 } } } } int main() { 
       // 取消同步流，加快输入输出 std::cin.tie(nullptr)->sync_with_stdio(false); std::cout << "请输入顶点数量："<<std::endl; std::cin >> n; // 初始化邻接矩阵和访问标记数组 graph.resize(n + 1, std::vector<int>(n + 1, 0)); // 多分配一行一列，以支持从1到n的索引 visited.resize(n + 1, false); std::cout << "输入邻接矩阵信息："<<std::endl; for (int i = 1; i <= n; ++i) { 
       for (int j = 1; j <= n; ++j) { 
       std::cin >> graph[i][j]; } } // 邻接矩阵的DFS遍历 std::fill(visited.begin(),visited.end(),false); visited[1] = true; std::cout << "DFS遍历结果:" << std::endl; dfs(1); // 从顶点1开始进行DFS遍历  std::cout << '\n'; std::cout << '\n'; // 邻接矩阵的BFS遍历 std::fill(visited.begin(),visited.end(),false); visited[1] = true; std::cout << "BFS遍历结果: " << std::endl; bfs(1); std::cout << '\n'; std::cout << '\n'; // 回溯 std::fill(visited.begin(), visited.end(), false); path.push_back(1); // 初始化路径，起点是1 visited[1] = true; // 标记起点为已访问 std::cout << "回溯结果：" <<std