devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++面试：熟悉图论算法（dijkstra算法、最小生成树、深度优先搜索等）_迪杰斯特拉和深度搜索

作者：笔触狂放9 | 2024-05-29 05:59:41

赞

踩

迪杰斯特拉和深度搜索

        熟悉图论算法是对于准备C++后台开发岗位面试非常重要的一部分。我将为你概述Dijkstra算法、最小生成树算法以及深度优先搜索（DFS），这些都是图论中常用的算法。

目录

1. Dijkstra算法

代码解释

运行示例

2. 最小生成树算法

    1. Kruskal算法

2. Prim算法

代码解释

3. 深度优先搜索（DFS）

代码解释

4. 广度优先搜索（BFS）

代码解释

运行示例

5. A* 搜索算法

代码解释

运行示例

6. Floyd-Warshall 算法

代码解释

运行示例

7. Tarjan算法

代码解释

运行示例

8. Bellman-Ford 算法

代码解释

运行示例

9. 拓扑排序

10. 网络流算法

代码解释

运行示例

代码解释

运行示例

总结

1. Dijkstra算法

  • 用途: 用于在加权图中找到一个顶点到图中所有其他顶点的最短路径。
  • 原理: 算法采用了贪心的策略，每次找到距离起始点最近的一个顶点，然后以该顶点为中介，更新其余所有顶点的最短路径。
  • 特点: 仅适用于边权重非负的图。

        以下是Dijkstra算法的一个C++实现示例，我将包含详细的注释来解释每个关键部分。这个实现使用了优先队列来优化效率，它适用于边权重非负的图。

  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. // 定义边的结构
  9. struct Edge {
  10.     int to;     // 边指向的顶点
  11.     int weight; // 边的权重
  12.     Edge(int t, int w) : to(t), weight(w) {}
  13. };
  14.  
  15. // 定义用于优先队列的比较函数
  16. class Compare {
  17. public:
  18.     bool operator() (pair<int, int>& p1, pair<int, int>& p2) {
  19.         return p1.second > p2.second;
  20.     }
  21. };
  22.  
  23. void dijkstra(const vector<vector<Edge>>& graph, int start) {
  24.     int n = graph.size();
  25.     vector<int> dist(n, INT_MAX); // 存储起始点到所有点的最短距离
  26.     vector<bool> visited(n, false); // 标记顶点是否访问过
  27.  
  28.     priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
  29.  
  30.     // 从起始点开始
  31.     pq.push({start, 0});
  32.     dist[start] = 0;
  33.  
  34.     while (!pq.empty()) {
  35.         int current = pq.top().first;
  36.         pq.pop();
  37.  
  38.         if (visited[current]) continue;
  39.         visited[current] = true;
  40.  
  41.         // 遍历当前顶点的所有邻接边
  42.         for (const Edge& edge : graph[current]) {
  43.             int next = edge.to;
  44.             int nextDist = dist[current] + edge.weight;
  45.  
  46.             // 如果找到更短的路径，则更新
  47.             if (nextDist < dist[next]) {
  48.                 dist[next] = nextDist;
  49.                 pq.push({next, nextDist});
  50.             }
  51.         }
  52.     }
  53.  
  54.     // 打印最短路径结果
  55.     for (int i = 0; i < n; ++i) {
  56.         if (dist[i] == INT_MAX)
  57.             cout << "Vertex " << i << ": unreachable" << endl;
  58.         else
  59.             cout << "Vertex " << i << ": " << dist[i] << endl;
  60.     }
  61. }
  62.  
  63. int main() {
  64.     // 创建一个示例图
  65.     int n = 5; // 图中顶点数
  66.     vector<vector<Edge>> graph(n);
  67.  
  68.     // 添加边
  69.     graph[0].emplace_back(1, 2);
  70.     graph[0].emplace_back(3, 6);
  71.     graph[1].emplace_back(2, 3);
  72.     graph[1].emplace_back(3, 8);
  73.     graph[1].emplace_back(4, 5);
  74.     graph[2].emplace_back(4, 7);
  75.     graph[3].emplace_back(4, 9);
  76.  
  77.     // 从顶点0开始应用Dijkstra算法
  78.     dijkstra(graph, 0);
  79.  
  80.     return 0;
  81. }
代码解释
  • 数据结构: 使用vector<vector<Edge>>来表示图，每个顶点都有一个边的列表。
  • 边权重: Edge结构体包含了目标顶点和边的权重。
  • 优先队列: 用于存储待访问的顶点及其从起点到该点的路径长度。
  • Dijkstra算法实现:
    • 使用dist数组来跟踪从起点到每个顶点的最短距离。
    • 使用visited数组来标记每个顶点是否已被处理。
    • 通过优先队列优化选择下一个要处理的顶点的过程。
    • 遍历每个顶点的所有邻接边，更新其最短路径。
运行示例
  • 这段代码定义了一个有5个顶点的图，并为其添加了一些边和权重。
  • 应用Dijkstra算法计算从顶点0到所有其他顶点的最短路径，并打印结果。

2. 最小生成树算法

  • 用途: 在一个加权连通图中选取一部分边，构成一棵包含所有顶点的树，并且使边的总权重尽可能小。
  • 常用算法:
    • Kruskal算法: 按照边的权重从小到大的顺序选择边，确保选择的边不会与已选择的边形成环。
    • Prim算法: 从一个顶点开始，每一步添加一条连接已选顶点集合和未选顶点集合的最小权重边。
    1. Kruskal算法

        Kruskal算法使用并查集（Union-Find）结构来避免环的形成。

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct Edge {
  8.     int src, dest, weight;
  9.     bool operator<(Edge const& other) {
  10.         return weight < other.weight;
  11.     }
  12. };
  13.  
  14. struct DisjointSets {
  15.     vector<int> parent, rank;
  16.     int n;
  17.  
  18.     DisjointSets(int n) {
  19.         this->n = n;
  20.         parent.resize(n);
  21.         rank.resize(n);
  22.  
  23.         for (int i = 0; i < n; i++)
  24.             parent[i] = i;
  25.     }
  26.  
  27.     int find(int i) {
  28.         if (parent[i] != i)
  29.             parent[i] = find(parent[i]);
  30.         return parent[i];
  31.     }
  32.  
  33.     void merge(int x, int y) {
  34.         x = find(x), y = find(y);
  35.  
  36.         if (rank[x] > rank[y])
  37.             parent[y] = x;
  38.         else
  39.             parent[x] = y;
  40.  
  41.         if (rank[x] == rank[y])
  42.             rank[y]++;
  43.     }
  44. };
  45.  
  46. void KruskalMST(vector<Edge>& edges, int V) {
  47.     sort(edges.begin(), edges.end());
  48.     DisjointSets ds(V);
  49.  
  50.     vector<Edge> result;
  51.  
  52.     for (auto edge : edges) {
  53.         int x = ds.find(edge.src);
  54.         int y = ds.find(edge.dest);
  55.  
  56.         if (x != y) {
  57.             result.push_back(edge);
  58.             ds.merge(x, y);
  59.         }
  60.     }
  61.  
  62.     // 打印MST
  63.     for (auto e : result)
  64.         cout << e.src << " - " << e.dest << " : " << e.weight << endl;
  65. }
  66.  
  67. int main() {
  68.     int V = 4; // 顶点数量
  69.     vector<Edge> edges = {
  70.         {0, 1, 10},
  71.         {0, 2, 6},
  72.         {0, 3, 5},
  73.         {1, 3, 15},
  74.         {2, 3, 4}
  75.     };
  76.  
  77.     KruskalMST(edges, V);
  78.     return 0;
  79. }

2. Prim算法

        Prim算法使用优先队列来选择最小权重的边。

  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. typedef pair<int, int> iPair; // 用于表示权重和顶点的对
  9.  
  10. void PrimMST(vector<vector<iPair>>& graph, int V) {
  11.     priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
  12.     int src = 0; // 可以从任何顶点开始
  13.  
  14.     vector<int> key(V, INT_MAX);
  15.     vector<bool> inMST(V, false);
  16.     vector<int> parent(V, -1);
  17.  
  18.     pq.push(make_pair(0, src));
  19.     key[src] = 0;
  20.  
  21.     while (!pq.empty()) {
  22.         int u = pq.top().second;
  23.         pq.pop();
  24.  
  25.         inMST[u] = true;
  26.  
  27.         for (auto i : graph[u]) {
  28.             int v = i.first;
  29.             int weight = i.second;
  30.  
  31.             if (!inMST[v] && key[v] > weight) {
  32.                 key[v] = weight;
  33.                 pq.push(make_pair(key[v], v));
  34.                 parent[v] = u;
  35.             }
  36.         }
  37.     }
  38.  
  39.     // 打印构造的MST
  40.     for (int i = 1; i < V; ++i)
  41.         cout << parent[i] << " - " << i << " : " << key[i] << endl;
  42. }
  43.  
  44. int main() {
  45.     int V = 4;
  46.     vector<vector<iPair>> graph(V);
  47.  
  48.     // 构造图
  49.     graph[0].push_back(make_pair(1, 10));
  50.     graph[0].push_back(make_pair(2, 6));
  51.     graph[0].push_back(make_pair(3, 5));
  52.     graph[1].push_back(make_pair(3, 15));
  53.     graph[2].push_back(make_pair(3, 4));
  54.  
  55.     PrimMST(graph, V);
  56.  
  57.     return 0;
  58. }
代码解释
  • Kruskal算法:
    • 使用并查集来维护不同集合，并确保添加的边不会形成环。
    • 将所有的边按照权重进行排序，然后按顺序加入边，如果加入该边不会形成环，则该边是MST的一部分。
  • Prim算法:
    • 使用优先队列来存储和选择当前最小权重的边。
    • 从一个顶点开始，重复选择连接已选择顶点和未选择顶点的最小权重边，直到覆盖所有顶点。

        这两种算法在不同情况下都很有用。Kruskal算法适合边比较稀疏的图，而Prim算法适合边比较密集的图。在准备面试时，理解这两种算法的适用场景和优缺点是很重要的。

3. 深度优先搜索（DFS）

  • 用途: 用于遍历或搜索树或图的结构。深度优先搜索沿着树的深度遍历树的节点，尽可能深地搜索树的分支。
  • 原理: 从一个顶点开始，沿当前顶点的边走到未访问的顶点，当没有未访问的顶点时，回溯到上一个顶点，继续搜索直到所有顶点都被访问。
  • 应用: 解决迷宫问题、路径查找、拓扑排序等。

        深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。它的基本思想是从一个顶点开始，沿着边到达新的顶点，并沿此路径尽可能深地搜索，直到找不到新的未访问顶点为止，然后回溯并继续搜索。以下是DFS算法的C++实现示例，包含详细注释。

  1. #include <iostream>
  2. #include <list>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. class Graph {
  8.     int V;    // 顶点的数量
  9.     list<int> *adj; // 邻接表
  10.  
  11.     // DFS递归辅助函数
  12.     void DFSUtil(int v, vector<bool>& visited) {
  13.         // 标记当前节点为已访问
  14.         visited[v] = true;
  15.         cout << v << " ";
  16.  
  17.         // 递归访问所有未访问的邻接顶点
  18.         for (auto i = adj[v].begin(); i != adj[v].end(); ++i) {
  19.             if (!visited[*i]) {
  20.                 DFSUtil(*i, visited);
  21.             }
  22.         }
  23.     }
  24.  
  25. public:
  26.     Graph(int V) {
  27.         this->V = V;
  28.         adj = new list<int>[V];
  29.     }
  30.  
  31.     // 添加边到图中
  32.     void addEdge(int v, int w) {
  33.         adj[v].push_back(w); // 添加w到v的列表中
  34.     }
  35.  
  36.     // DFS遍历函数
  37.     void DFS(int v) {
  38.         // 初始化所有顶点为未访问
  39.         vector<bool> visited(V, false);
  40.  
  41.         // 从顶点v开始DFS遍历
  42.         DFSUtil(v, visited);
  43.     }
  44. };
  45.  
  46. int main() {
  47.     // 创建一个图
  48.     Graph g(4);
  49.  
  50.     // 添加边
  51.     g.addEdge(0, 1);
  52.     g.addEdge(0, 2);
  53.     g.addEdge(1, 2);
  54.     g.addEdge(2, 0);
  55.     g.addEdge(2, 3);
  56.     g.addEdge(3, 3);
  57.  
  58.     // 从顶点2开始DFS遍历
  59.     cout << "Starting DFS from vertex 2" << endl;
  60.     g.DFS(2);
  61.  
  62.     return 0;
  63. }
代码解释
  • 图的表示：这个示例中，图用邻接表的方式表示。Graph类中的adj是一个指向整数列表的数组，表示图的邻接表。
  • 添加边：addEdge函数用于向图中添加边。
  • DFS实现：
    • DFS函数初始化一个布尔类型的数组来跟踪访问过的顶点。
    • DFSUtil是一个递归函数，用于实际进行DFS遍历。它访问一个顶点，然后对于每一个邻接的未访问顶点，递归调用自身。

        请注意，DFS的特点是它可能不会访问图中的所有顶点，尤其是在图不是完全连通的情况下。要遍历所有顶点，可能需要从不同的顶点分别启动DFS。此外，DFS在实际应用中有多种变体，例如用于路径查找、拓扑排序或解决迷宫问题。在准备面试时，理解这些变体并知道如何实现它们是很有帮助的。

4. 广度优先搜索（BFS）

  • 用途: 主要用于在图中进行层级搜索，适用于找到最短路径问题。
  • 原理: 从一个顶点开始，先访问所有邻接的顶点，再从这些邻接顶点出发，访问它们的邻接顶点，以此类推。

        广度优先搜索（BFS）是图和树的一种遍历算法，它从一个起始顶点开始，先访问所有相邻的顶点，然后再逐层访问更远的顶点。它特别适用于找到从源点到其他顶点的最短路径。以下是广度优先搜索的C++实现，包含详细注释：

  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <list>
  5.  
  6. using namespace std;
  7.  
  8. class Graph {
  9.     int V;    // 顶点的数量
  10.     list<int> *adj; // 邻接表
  11.  
  12. public:
  13.     Graph(int V) {
  14.         this->V = V;
  15.         adj = new list<int>[V];
  16.     }
  17.  
  18.     // 添加边到图中
  19.     void addEdge(int v, int w) {
  20.         adj[v].push_back(w); // 在v的列表中添加w
  21.     }
  22.  
  23.     // BFS遍历函数
  24.     void BFS(int s) {
  25.         // 初始化所有顶点为未访问
  26.         vector<bool> visited(V, false);
  27.  
  28.         // 创建一个队列用于BFS
  29.         queue<int> queue;
  30.  
  31.         // 标记当前节点为已访问并入队
  32.         visited[s] = true;
  33.         queue.push(s);
  34.  
  35.         while (!queue.empty()) {
  36.             // 出队一个顶点并打印
  37.             s = queue.front();
  38.             cout << s << " ";
  39.             queue.pop();
  40.  
  41.             // 获取所有邻接的顶点
  42.             for (auto i = adj[s].begin(); i != adj[s].end(); ++i) {
  43.                 if (!visited[*i]) {
  44.                     visited[*i] = true;
  45.                     queue.push(*i);
  46.                 }
  47.             }
  48.         }
  49.     }
  50. };
  51.  
  52. int main() {
  53.     // 创建一个图
  54.     Graph g(4);
  55.  
  56.     // 添加边
  57.     g.addEdge(0, 1);
  58.     g.addEdge(0, 2);
  59.     g.addEdge(1, 2);
  60.     g.addEdge(2, 0);
  61.     g.addEdge(2, 3);
  62.     g.addEdge(3, 3);
  63.  
  64.     // 从顶点2开始BFS遍历
  65.     cout << "Starting BFS from vertex 2" << endl;
  66.     g.BFS(2);
  67.  
  68.     return 0;
  69. }
代码解释
  • 图的表示：图用邻接表的形式表示。Graph类中的adj是一个指向整数列表的数组，表示图的邻接表。
  • 添加边：addEdge函数向图中添加边。
  • BFS实现：
    • BFS函数初始化一个布尔类型的数组来跟踪访问过的顶点。
    • 使用队列来支持BFS。先将起始顶点加入队列，然后循环直到队列为空。在循环中，从队列中取出一个顶点，访问它的所有未访问的邻接顶点，并将这些邻接顶点加入队列。
运行示例
  • 这个程序创建了一个包含四个顶点的图，并添加了一些边。
  • 然后，它从顶点2开始进行BFS遍历，并打印访问的顶点顺序。

        BFS通常用于找到从一个顶点到另一个顶点的最短路径，尤其是在未加权图中。在准备面试时，理解BFS的工作原理并能够根据需要修改和应用它是很重要的。

5. A* 搜索算法

  • 用途: 用于图中的路径寻找和图遍历，特别是在有成本最小化要求的情况下。
  • 原理: 结合了Dijkstra算法和启发式方法（如曼哈顿距离、欧几里得距离）来找到从起始点到目标点的最低成本路径。

        A搜索算法是一种有效的路径查找和图遍历算法，它结合了Dijkstra算法的确保最短路径的优点和启发式搜索（如贪心算法）的高效性。A算法使用启发式函数来估算从当前节点到目标节点的最佳路径成本，通常用于求解复杂的路径规划问题。以下是A*算法的C++实现示例，包含详细注释： 

  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <cmath>
  5. #include <unordered_map>
  6.  
  7. using namespace std;
  8.  
  9. // 定义坐标点
  10. struct Point {
  11.     int x, y;
  12.     Point(int x, int y) : x(x), y(y) {}
  13. };
  14.  
  15. // 计算两点之间的欧几里得距离，用作启发式函数
  16. double heuristic(Point a, Point b) {
  17.     return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
  18. }
  19.  
  20. // 定义节点，用于A*搜索
  21. struct Node {
  22.     Point point; // 节点的坐标
  23.     double f, g, h; // f = g + h
  24.     Node *parent; // 指向父节点的指针
  25.  
  26.     Node(Point pt, double g, double h, Node *parent = nullptr) 
  27.         : point(pt), g(g), h(h), f(g + h), parent(parent) {}
  28.  
  29.     // 重载<运算符，用于优先队列
  30.     bool operator<(const Node& other) const {
  31.         return f > other.f;
  32.     }
  33. };
  34.  
  35. // A*搜索算法实现
  36. vector<Point> AStarSearch(vector<vector<int>>& grid, Point start, Point end) {
  37.     priority_queue<Node> openSet; // 开放列表
  38.     vector<vector<bool>> closedSet(grid.size(), vector<bool>(grid[0].size(), false)); // 关闭列表
  39.  
  40.     openSet.push(Node(start, 0, heuristic(start, end)));
  41.  
  42.     while (!openSet.empty()) {
  43.         Node current = openSet.top();
  44.         openSet.pop();
  45.  
  46.         // 检查是否到达终点
  47.         if (current.point.x == end.x && current.point.y == end.y) {
  48.             vector<Point> path;
  49.             while (current.parent != nullptr) {
  50.                 path.push_back(current.point);
  51.                 current = *current.parent;
  52.             }
  53.             reverse(path.begin(), path.end());
  54.             return path;
  55.         }
  56.  
  57.         closedSet[current.point.x][current.point.y] = true;
  58.  
  59.         // 检查邻居
  60.         vector<Point> neighbors = {/* 上下左右四个方向的邻居坐标 */};
  61.         for (Point& neighbor : neighbors) {
  62.             if (closedSet[neighbor.x][neighbor.y] || grid[neighbor.x][neighbor.y] == 0) {
  63.                 continue; // 跳过障碍物或已经在关闭列表中的节点
  64.             }
  65.  
  66.             double tentative_g = current.g + heuristic(current.point, neighbor);
  67.  
  68.             // 添加到开放列表
  69.             if (!closedSet[neighbor.x][neighbor.y]) {
  70.                 openSet.push(Node(neighbor, tentative_g, heuristic(neighbor, end), new Node(current)));
  71.             }
  72.         }
  73.     }
  74.  
  75.     return vector<Point>(); // 如果找不到路径，返回空路径
  76. }
  77.  
  78. int main() {
  79.     // 创建网格地图，1表示可通过，0表示障碍物
  80.     vector<vector<int>> grid = {
  81.         {1, 1, 1, 1},
  82.         {1, 0, 1, 1},
  83.         {1, 1, 1, 1},
  84.         {1, 1, 1, 1}
  85.     };
  86.  
  87.     // 设置起点和终点
  88.     Point start(0, 0), end(3, 3);
  89.  
  90.     // 执行A*搜索
  91.     vector<Point> path = AStarSearch(grid, start, end);
  92.  
  93.     // 打印路径
  94.     for (Point p : path) {
  95.         cout << "(" << p.x << ", " << p.y << ") ";
  96.     }
  97.  
  98.     return 0;
  99. }
代码解释
  • 启发式函数：这里使用的是欧几里得距离，你也可以使用曼哈顿距离或其他合适的启发式函数。
  • Node结构：每个节点包含其在网格中的坐标、从起点到该点的实际成本（g）、从该点到终点的估计成本（h）以及两者之和（f）。
  • 开放列表和关闭列表：开放列表（openSet）存储待访问的节点，关闭列表（closedSet）用于跟踪已访问的节点。
  • 邻居节点：算法检查当前节点的所有邻居，然后计算每个邻居的成本，将其添加到开放列表中。
运行示例
  • 这个程序创建了一个简单的网格地图，并设置了起点和终点。
  • 然后，它使用A*搜索算法找到从起点到终点的路径，并打印路径。

        请注意，这个示例是A算法的一个基本实现。在复杂的实际应用中，比如大型地图或动态变化的环境中，可能需要对算法进行优化和调整。在准备面试时，理解A算法的原理和实现方式非常重要。

6. Floyd-Warshall 算法

  • 用途: 解决所有顶点对的最短路径问题。
  • 原理: 通过考虑所有可能的路径中间点，系统地减少最短路径的估计。

        Floyd-Warshall算法是一种计算图中所有顶点对之间最短路径的算法。它能够处理包含负权边的图（但不允许负权回路）。该算法通过动态规划逐步构建每对顶点间的最短路径。以下是Floyd-Warshall算法的C++实现，包含详细注释：

  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4.  
  5. using namespace std;
  6.  
  7. #define INF INT_MAX
  8.  
  9. void FloydWarshall(vector<vector<int>>& graph) {
  10.     int V = graph.size();
  11.     vector<vector<int>> dist = graph;
  12.  
  13.     // 通过每个顶点k，尝试更新每对顶点i和j之间的最短路径
  14.     for (int k = 0; k < V; k++) {
  15.         for (int i = 0; i < V; i++) {
  16.             for (int j = 0; j < V; j++) {
  17.                 // 如果i到k和k到j的路径都存在
  18.                 if (dist[i][k] != INF && dist[k][j] != INF) {
  19.                     // 更新i到j的最短路径
  20.                     dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  21.                 }
  22.             }
  23.         }
  24.     }
  25.  
  26.     // 打印最终的最短路径矩阵
  27.     for (int i = 0; i < V; i++) {
  28.         for (int j = 0; j < V; j++) {
  29.             if (dist[i][j] == INF)
  30.                 cout << "INF ";
  31.             else
  32.                 cout << dist[i][j] << " ";
  33.         }
  34.         cout << endl;
  35.     }
  36. }
  37.  
  38. int main() {
  39.     // 创建一个图的邻接矩阵表示
  40.     vector<vector<int>> graph = {
  41.         {0, 5, INF, 10},
  42.         {INF, 0, 3, INF},
  43.         {INF, INF, 0, 1},
  44.         {INF, INF, INF, 0}
  45.     };
  46.  
  47.     // 执行Floyd-Warshall算法
  48.     FloydWarshall(graph);
  49.  
  50.     return 0;
  51. }
代码解释
  • 图的表示：图用邻接矩阵表示，其中graph[i][j]表示顶点i到顶点j的边的权重，如果i和j之间没有直接的边，则为INF（无穷大）。
  • 初始化距离矩阵：dist数组初始化为图的邻接矩阵。
  • 动态规划：通过三重循环逐渐更新每对顶点之间的最短路径。对于每个顶点k，算法尝试通过顶点k更新所有顶点对i和j之间的最短路径。
  • 输出结果：打印出最终的最短路径矩阵，其中dist[i][j]表示顶点i到顶点j的最短路径长度。
运行示例
  • 这个程序创建了一个含有4个顶点的图，并以邻接矩阵形式表示。
  • 然后，它使用Floyd-Warshall算法计算图中所有顶点对之间的最短路径，并打印结果。

        在准备面试时，了解Floyd-Warshall算法的原理和应用是很重要的，尤其是在处理复杂图论问题时。这个算法虽然简单，但对于理解动态规划和图的最短路径问题非常有帮助。

7. Tarjan算法

  • 用途: 用于寻找图中的强连通分量。
  • 原理: 基于深度优先搜索，通过管理一个索引堆栈，能够有效地识别出强连通分量。

        Tarjan算法是图论中的一个重要算法，它不仅用于识别强连通分量，还可以应用于其他问题，如桥的检测和割点的识别。在准备面试时，理解这个算法的工作原理并能够实现它对于展示你的算法和数据结构知识非常有帮助。 

        Tarjan算法是一种基于深度优先搜索（DFS）的图算法，用于找出有向图中的所有强连通分量。算法维护一个堆栈来追踪已访问的顶点，并使用两个数组来记录每个顶点的访问顺序和可回溯到的最早顶点。以下是Tarjan算法的C++实现，包括详细注释： 

  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <list>
  5.  
  6. using namespace std;
  7.  
  8. class Graph {
  9.     int V;    // 顶点数
  10.     list<int> *adj; // 邻接表
  11.  
  12.     void tarjanUtil(int u, vector<int>& disc, vector<int>& low, stack<int>& st, vector<bool>& stackMember) {
  13.         static int time = 0;
  14.  
  15.         // 初始化当前节点
  16.         disc[u] = low[u] = ++time;
  17.         st.push(u);
  18.         stackMember[u] = true;
  19.  
  20.         // 遍历所有邻接顶点
  21.         for (int v : adj[u]) {
  22.             // 如果v未被访问，递归调用
  23.             if (disc[v] == -1) {
  24.                 tarjanUtil(v, disc, low, st, stackMember);
  25.  
  26.                 // 检查子树中是否有回路
  27.                 low[u] = min(low[u], low[v]);
  28.             }
  29.             // 如果v在栈中，更新u的low值
  30.             else if (stackMember[v] == true) {
  31.                 low[u] = min(low[u], disc[v]);
  32.             }
  33.         }
  34.  
  35.         // 如果u是强连通分量的根，提取整个分量
  36.         int w = 0;  // To store stack extracted vertices
  37.         if (low[u] == disc[u]) {
  38.             while (st.top() != u) {
  39.                 w = (int) st.top();
  40.                 cout << w << " ";
  41.                 stackMember[w] = false;
  42.                 st.pop();
  43.             }
  44.             w = (int) st.top();
  45.             cout << w << "\n";
  46.             stackMember[w] = false;
  47.             st.pop();
  48.         }
  49.     }
  50.  
  51. public:
  52.     Graph(int V) {
  53.         this->V = V;
  54.         adj = new list<int>[V];
  55.     }
  56.  
  57.     void addEdge(int v, int w) { adj[v].push_back(w); }
  58.  
  59.     // The function to find SCCs
  60.     void tarjanSCC() {
  61.         vector<int> disc(V, -1), low(V, -1);
  62.         vector<bool> stackMember(V, false);
  63.         stack<int> st;
  64.  
  65.         // Call the recursive helper function to find SCCs
  66.         for (int i = 0; i < V; i++)
代码解释
  • 图的表示：图使用邻接表表示，其中adj是一个指向整数列表的数组。
  • Tarjan算法的核心：tarjanUtil函数实现了Tarjan算法的主要逻辑。它使用时间戳来标记每个顶点的访问时间，用low数组来跟踪每个节点可以回溯到的最早访问节点。
  • 强连通分量的提取：当low[u] == disc[u]时，从堆栈中提取出一个完整的强连通分量。
运行示例
  • 这个程序创建了一个含有5个顶点的图，并添加了一些边。
  • 然后，它使用Tarjan算法找到并打印图中的所有强连通分量。

8. Bellman-Ford 算法

  • 用途: 在带权图中计算单源最短路径，特别是处理图中包含负权边的情况。
  • 原理: 通过松弛操作重复地减小从源点到所有其他顶点的距离估计。

        Bellman-Ford 算法是一种在带权图中计算单源最短路径的算法，尤其适用于含有负权边的图。该算法通过重复地松弛所有边，来逐步减小从源点到所有其他顶点的距离估计，直到这些估计不再改变。以下是Bellman-Ford 算法的 C++ 实现，包括详细注释：

  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4.  
  5. using namespace std;
  6.  
  7. // 定义边的结构
  8. struct Edge {
  9.     int src, dest, weight;
  10. };
  11.  
  12. class Graph {
  13.     int V, E;    // 图中的顶点数和边数
  14.     vector<Edge> edges; // 边的列表
  15.  
  16. public:
  17.     Graph(int V, int E) {
  18.         this->V = V;
  19.         this->E = E;
  20.     }
  21.  
  22.     // 向图中添加边
  23.     void addEdge(int u, int v, int w) {
  24.         edges.push_back({u, v, w});
  25.     }
  26.  
  27.     // Bellman-Ford算法实现
  28.     void BellmanFord(int src) {
  29.         vector<int> dist(V, INT_MAX);
  30.         dist[src] = 0;
  31.  
  32.         // 对每条边进行V-1次松弛操作
  33.         for (int i = 1; i <= V - 1; i++) {
  34.             for (int j = 0; j < E; j++) {
  35.                 int u = edges[j].src;
  36.                 int v = edges[j].dest;
  37.                 int weight = edges[j].weight;
  38.                 if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
  39.                     dist[v] = dist[u] + weight;
  40.             }
  41.         }
  42.  
  43.         // 检查负权回路
  44.         for (int i = 0; i < E; i++) {
  45.             int u = edges[i].src;
  46.             int v = edges[i].dest;
  47.             int weight = edges[i].weight;
  48.             if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
  49.                 cout << "Graph contains negative weight cycle" << endl;
  50.                 return;
  51.             }
  52.         }
  53.  
  54.         // 打印最短路径
  55.         for (int i = 0; i < V; i++)
  56.             cout << "Distance from " << src << " to " << i << " is " << dist[i] << endl;
  57.     }
  58. };
  59.  
  60. int main() {
  61.     int V = 5; // 顶点数
  62.     int E = 8; // 边数
  63.     Graph g(V, E);
  64.  
  65.     // 向图中添加边
  66.     g.addEdge(0, 1, -1);
  67.     g.addEdge(0, 2, 4);
  68.     g.addEdge(1, 2, 3);
  69.     g.addEdge(1, 3, 2);
  70.     g.addEdge(1, 4, 2);
  71.     g.addEdge(3, 2, 5);
  72.     g.addEdge(3, 1, 1);
  73.     g.addEdge(4, 3, -3);
  74.  
  75.     // 从顶点 0 执行Bellman-Ford算法
  76.     g.BellmanFord(0);
  77.  
  78.     return 0;
  79. }
代码解释
  • 图的表示：图使用边的列表表示，每个边包含源顶点、目标顶点和权重。
  • Bellman-Ford 算法实现：
    • 初始化所有顶点的距离为无穷大，除了源顶点的距离为0。
    • 对所有边执行 V-1 次松弛操作，更新每个顶点的距离估计。
    • 再次检查所有边，确认是否存在负权回路。
  • 打印结果：打印从源顶点到所有其他顶点的最短路径。
运行示例
  • 这个程序创建了一个含有5个顶点和8条边的图。
  • 然后，它使用 Bellman-Ford 算法从顶点0开始计算最短路径，并打印结果。

      Bellman-Ford 算法是理解动态规划在图论中应用的一个很好的例子。尽管它的时间复杂度高于 Dijkstra 算法，但它能处理包含负权边的图。在准备面试时，理解和能够实现这个算法是很重要的。

9. 拓扑排序

  • 用途: 对有向无环图（DAG）进行排序，以线性顺序表示图中所有顶点的前后关系。
  • 原理: 基于深度优先搜索或入度表（每个节点入度的计数）。

10. 网络流算法

  • 用途: 用于求解网络流问题，如最大流问题。
  • 常用算法: Ford-Fulkerson 算法、Edmonds-Karp 算法等。

        网络流问题，特别是最大流问题，在图论中是一个重要的主题。Ford-Fulkerson 算法是解决这类问题的一种常用方法，它通过不断查找增广路径来增加流量，直到达到最大流。Edmonds-Karp 算法是 Ford-Fulkerson 算法的一个特定实现，它使用广度优先搜索（BFS）来查找增广路径，保证了多项式时间复杂度。以下是 Edmonds-Karp 算法的 C++ 实现，包含详细注释：

  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <climits>
  5. #include <cstring>
  6.  
  7. using namespace std;
  8.  
  9. // 寻找从 s 到 t 的路径，并更新残留网络
  10. bool bfs(vector<vector<int>>& rGraph, int s, int t, vector<int>& parent) {
  11.     int V = rGraph.size();
  12.     vector<bool> visited(V, false);
  13.     queue<int> q;
  14.     q.push(s);
  15.     visited[s] = true;
  16.     parent[s] = -1;
  17.  
  18.     // 标准的 BFS 循环
  19.     while (!q.empty()) {
  20.         int u = q.front();
  21.         q.pop();
  22.  
  23.         for (int v = 0; v < V; v++) {
  24.             if (visited[v] == false && rGraph[u][v] > 0) {
  25.                 // 如果我们找到了一个连接到汇点的路径，则终止 BFS
  26.                 if (v == t) {
  27.                     parent[v] = u;
  28.                     return true;
  29.                 }
  30.                 q.push(v);
  31.                 parent[v] = u;
  32.                 visited[v] = true;
  33.             }
  34.         }
  35.     }
  36.  
  37.     return false;
  38. }
  39.  
  40. // 使用 Ford-Fulkerson 算法的 Edmonds-Karp 实现来返回最大流
  41. int edmondsKarp(vector<vector<int>>& graph, int s, int t) {
  42.     int u, v;
  43.  
  44.     // 创建残留网络并用给定的容量填充
  45.     int V = graph.size();
  46.     vector<vector<int>> rGraph(V, vector<int>(V)); // 残留网络
  47.     for (u = 0; u < V; u++)
  48.         for (v = 0; v < V; v++)
  49.              rGraph[u][v] = graph[u][v];
  50.  
  51.     vector<int> parent(V);  // 用于存储路径
  52.     int max_flow = 0;  // 存储最大流量
  53.  
  54.     // 增广路径循环
  55.     while (bfs(rGraph, s, t, parent)) {
  56.         // 找到最小的残留容量边
  57.         int path_flow = INT_MAX;
  58.         for (v = t; v != s; v = parent[v]) {
  59.             u = parent[v];
  60.             path_flow = min(path_flow, rGraph[u][v]);
  61.         }
  62.  
  63.         // 更新残留网络的容量和反向边
  64.         for (v = t; v != s; v = parent[v]) {
  65.             u = parent[v];
  66.             rGraph[u][v] -= path_flow;
  67.             rGraph[v][u] += path_flow;
  68.         }
  69.  
  70.         // 添加路径流量到总流量
  71.         max_flow += path_flow;
  72.     }
  73.  
  74.     return max_flow;
  75. }
  76.  
  77. int main() {
  78.     // 创建图：顶点数为 4
  79.     vector<vector<int>> graph = { {0, 10, 0, 10},
  80.                                   {0, 0, 4, 2},
  81.                                   {0, 0, 0, 8},
  82.                                   {0, 0, 0, 0} };
  83.  
  84.     // 设定源点为 0，汇点为 3
  85.     cout << "The maximum possible flow is " << edmondsKarp(graph, 0, 3) << endl;
  86.  
  87.     return 0;
  88. }
代码解释
  • 创建残留网络：残留网络 rGraph 初始时与原始图相同，表示流量的可能性。
  • 广度优先搜索（BFS）：bfs 函数用于在残留网络中查找从源点 s 到汇点 t 的路径，同时更新 parent 数组来记录路径。
  • 计算最大流：在找到增广路径之后，计算该路径上的最小残留容量，然后更新残留网络，增加流量。
  • 更新残留网络：减少正向边的容量，增加反向边的容量，表示流量的重新分配。
运行示例
  • 程序创建了一个包含 4 个顶点的图，并设置了每条边的容量。
  • 然后，它使用 Edmonds-Karp 算法计算从顶点 0（源点）到顶点 3（汇点）的最大流，并打印结果。

        Edmonds-Karp 算法是网络流问题的一种有效解法，特别是在求解最大流问题时。在准备面试时，了解此算法的原理和实现对于展示你的图论知识非常有帮助。

        Ford-Fulkerson 算法是解决网络流问题中的最大流问题的一种经典方法。它通过不断寻找从源点到汇点的增广路径，并沿着这些路径增加流量，直到无法再增加为止。以下是 Ford-Fulkerson 算法的 C++ 实现，我将包括详细的注释来解释关键部分：

  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4. #include <queue>
  5. #include <cstring>
  6.  
  7. using namespace std;
  8.  
  9. // 使用邻接矩阵来表示图
  10. class Graph {
  11.     int V;    // 顶点数
  12.     vector<vector<int>> rGraph; // 残留网络
  13.  
  14. public:
  15.     Graph(int V, vector<vector<int>> graph) : V(V), rGraph(graph) {}
  16.  
  17.     // 使用 BFS 查找从 s 到 t 的路径
  18.     bool bfs(int s, int t, vector<int>& parent) {
  19.         vector<bool> visited(V, false);
  20.         queue<int> q;
  21.         q.push(s);
  22.         visited[s] = true;
  23.         parent[s] = -1;
  24.  
  25.         while (!q.empty()) {
  26.             int u = q.front();
  27.             q.pop();
  28.  
  29.             for (int v = 0; v < V; v++) {
  30.                 if (visited[v] == false && rGraph[u][v] > 0) {
  31.                     if (v == t) {
  32.                         parent[v] = u;
  33.                         return true;
  34.                     }
  35.                     q.push(v);
  36.                     parent[v] = u;
  37.                     visited[v] = true;
  38.                 }
  39.             }
  40.         }
  41.         return false;
  42.     }
  43.  
  44.     // 主函数实现 Ford-Fulkerson 算法
  45.     int FordFulkerson(int s, int t) {
  46.         int max_flow = 0;  // 最大流初始化为 0
  47.         vector<int> parent(V);  // 用于存储路径
  48.  
  49.         // 增广路径循环
  50.         while (bfs(s, t, parent)) {
  51.             int path_flow = INT_MAX;
  52.  
  53.             // 计算增广路径的最小残留容量
  54.             for (int v = t; v != s; v = parent[v]) {
  55.                 int u = parent[v];
  56.                 path_flow = min(path_flow, rGraph[u][v]);
  57.             }
  58.  
  59.             // 更新残留网络的边和反向边
  60.             for (int v = t; v != s; v = parent[v]) {
  61.                 int u = parent[v];
  62.                 rGraph[u][v] -= path_flow;
  63.                 rGraph[v][u] += path_flow;
  64.             }
  65.  
  66.             // 将路径流添加到总流量
  67.             max_flow += path_flow;
  68.         }
  69.  
  70.         return max_flow;
  71.     }
  72. };
  73.  
  74. int main() {
  75.     // 创建图：顶点数为 4
  76.     vector<vector<int>> graph = { {0, 16, 13, 0},
  77.                                   {0, 0, 10, 12},
  78.                                   {0, 4, 0, 0},
  79.                                   {0, 0, 9, 0} };
  80.  
  81.     Graph g(4, graph);
  82.  
  83.     // 计算从顶点 0（源点）到顶点 3（汇点）的最大流
  84.     cout << "The maximum possible flow is " << g.FordFulkerson(0, 3) << endl;
  85.  
  86.     return 0;
  87. }

代码解释

  • 构造图：图使用邻接矩阵表示，其中 rGraph[u][v] 表示从顶点 u 到顶点 v 的流量。
  • BFS：使用广度优先搜索来查找从源点 s 到汇点 t 的路径，并更新 parent 数组以记录路径。
  • 计算最大流：通过不断查找增广路径并更新残留网络，直到无法找到新的增广路径为止。
  • 更新残留网络：沿着找到的路径减少正向边的流量，并增加反向边的流量。

运行示例

  • 程序创建了一个包含 4 个顶点的图，并设置了每条边的流量。
  • 然后，它使用 Ford-Fulkerson 算法计算从顶点 0（源点）到顶点 3（汇点）的最大流，并打印结果。

        Ford-Fulkerson 算法是理解网络流问题的基础，并且在求解实际问题时非常有用。在准备面试时，了解并能够实现此算法对于展示你的图论和算法能力非常重要。

总结

        以上算法涵盖了图论中的一些关键概念和问题，包括寻找最短路径、探索图的结构，以及解决网络流问题。Dijkstra 和 Bellman-Ford 算法关注于单源最短路径问题，适用于不同类型的图（无负权边和有负权边）。而 Floyd-Warshall 和 A* 算法则扩展到所有顶点对的最短路径和特定场景下的最短路径搜索。Tarjan 算法用于探索图的深层结构，如强连通分量，而 DFS 和 BFS 提供了基础的图遍历方法。最后，Ford-Fulkerson 和 Edmonds-Karp 算法解决网络流和最大流问题。这些算法是计算机科学中图论应用的基石，对于处理复杂的数据结构和网络问题至关重要。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/640873
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号