C++算法（图算法）

1. 图的深度优先搜索（DFS）

思路解析：

DFS 是一种递归的图遍历算法，从起始节点开始，沿着一条路径尽可能深地访问，直到无法继续为止，然后回溯
使用 visited 数组标记已访问的节点，避免重复访问
可以用递归或栈实现，递归更简洁
时间复杂度：O(V + E)，V 是节点数，E 是边数

#include <iostream>
#include <vector>

using namespace std;

// DFS 递归实现
void DFS(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;  // 标记当前节点为已访问
    cout << node << " ";   // 访问节点（可以是任何处理操作）
    
    // 遍历当前节点的所有邻居
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {  // 如果邻居未被访问
            DFS(neighbor, graph, visited);  // 递归访问邻居
        }
    }
}

int main() {
    int n = 6;  // 图中节点数
    vector<vector<int>> graph(n);  // 邻接表表示图
    
    // 构建图（无向图）
    graph[0] = {1, 2};
    graph[1] = {0, 3};
    graph[2] = {0, 4};
    graph[3] = {1};
    graph[4] = {2, 5};
    graph[5] = {4};
    
    vector<bool> visited(n, false);  // 初始化访问标记数组
    
    cout << "DFS 遍历结果: ";
    DFS(0, graph, visited);  // 从节点 0 开始 DFS
    cout << endl;
    
    return 0;
}

2. 图的广度优先搜索（BFS）

思路解析：

BFS 是一种逐层遍历的算法，先访问起始节点，再访问其所有邻居，然后访问邻居的邻居
使用队列（FIFO）来实现，保证按层次顺序访问
适用于求最短路径（无权图）、层次遍历等问题
时间复杂度：O(V + E)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// BFS 实现
void BFS(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    queue<int> q;  // 创建队列
    visited[start] = true;  // 标记起始节点为已访问
    q.push(start);  // 将起始节点入队
    
    while (!q.empty()) {
        int node = q.front();  // 取出队首节点
        q.pop();
        cout << node << " ";  // 访问节点
        
        // 遍历当前节点的所有邻居
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {  // 如果邻居未被访问
                visited[neighbor] = true;  // 标记为已访问
                q.push(neighbor);  // 将邻居入队
            }
        }
    }
}

int main() {
    int n = 6;
    vector<vector<int>> graph(n);
    
    // 构建图
    graph[0] = {1, 2};
    graph[1] = {0, 3};
    graph[2] = {0, 4};
    graph[3] = {1};
    graph[4] = {2, 5};
    graph[5] = {4};
    
    vector<bool> visited(n, false);
    
    cout << "BFS 遍历结果: ";
    BFS(0, graph, visited);
    cout << endl;
    
    return 0;
}

3. 拓扑排序（Topological Sorting）

思路解析：

拓扑排序用于有向无环图（DAG），将节点排成线性序列，使得对于每条有向边 (u, v)，u 都在 v 之前
使用 DFS 实现：递归访问所有节点，访问完一个节点后将其压入栈，最后栈中的顺序即为拓扑排序
应用场景：任务调度、课程安排、编译依赖等
时间复杂度：O(V + E)

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// DFS 辅助函数，用于拓扑排序
void topologicalSortUtil(int node, vector<vector<int>>& graph, 
                         vector<bool>& visited, stack<int>& result) {
    visited[node] = true;  // 标记当前节点为已访问
    
    // 递归访问所有邻居
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            topologicalSortUtil(neighbor, graph, visited, result);
        }
    }
    
    // 当前节点的所有邻居都处理完后，将其压入栈
    result.push(node);
}

// 拓扑排序主函数
void topologicalSort(int n, vector<vector<int>>& graph) {
    vector<bool> visited(n, false);
    stack<int> result;  // 用栈存储拓扑排序结果
    
    // 对所有未访问的节点进行 DFS
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            topologicalSortUtil(i, graph, visited, result);
        }
    }
    
    // 输出拓扑排序结果
    cout << "拓扑排序结果: ";
    while (!result.empty()) {
        cout << result.top() << " ";
        result.pop();
    }
    cout << endl;
}

int main() {
    int n = 6;
    vector<vector<int>> graph(n);  // 有向图
    
    // 构建有向无环图
    graph[5] = {2, 0};
    graph[4] = {0, 1};
    graph[2] = {3};
    graph[3] = {};
    graph[0] = {};
    graph[1] = {};
    
    topologicalSort(n, graph);
    
    return 0;
}

4. 最短路径问题：Dijkstra 算法

思路解析：

Dijkstra 算法用于求单源最短路径，适用于非负权图
贪心策略：每次选择当前距离最小的未访问节点，更新其邻居的距离
使用优先队列（最小堆）优化，每次取出距离最小的节点
时间复杂度：O((V + E) log V)

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// Dijkstra 算法实现
void dijkstra(int src, vector<vector<pair<int, int>>>& graph, vector<int>& dist) {
    int n = graph.size();
    dist[src] = 0;  // 源节点到自己的距离为 0
    
    // 优先队列：pair<距离, 节点>，按距离从小到大排序
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, src});  // 将源节点入队
    
    while (!pq.empty()) {
        int u = pq.top().second;  // 当前距离最小的节点
        int d = pq.top().first;   // 当前节点的距离
        pq.pop();
        
        // 如果当前距离大于已记录的距离，跳过（已处理过更优的路径）
        if (d > dist[u]) continue;
        
        // 遍历当前节点的所有邻居
        for (auto& edge : graph[u]) {
            int v = edge.first;       // 邻居节点
            int weight = edge.second; // 边的权重
            
            // 松弛操作：如果通过 u 到 v 的距离更短，则更新
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});  // 将更新后的节点入队
            }
        }
    }
}

int main() {
    int n = 5;
    // 邻接表表示带权图：pair<邻居节点, 边权重>
    vector<vector<pair<int, int>>> graph(n);
    
    // 构建带权无向图
    graph[0] = {{1, 2}, {2, 4}};
    graph[1] = {{0, 2}, {2, 1}, {3, 7}};
    graph[2] = {{0, 4}, {1, 1}, {3, 3}};
    graph[3] = {{1, 7}, {2, 3}, {4, 1}};
    graph[4] = {{3, 1}};
    
    vector<int> dist(n, INT_MAX);  // 初始化距离为无穷大
    
    dijkstra(0, graph, dist);  // 从节点 0 开始
    
    // 输出结果
    cout << "从节点 0 到各节点的最短距离:\n";
    for (int i = 0; i < n; i++) {
        cout << "到节点 " << i << ": " << dist[i] << endl;
    }
    
    return 0;
}

5. 最短路径问题：Bellman-Ford 算法

思路解析：

Bellman-Ford 算法可以处理负权边，并能检测负权环
核心思想：对所有边进行 V-1 次松弛操作，每次松弛都会更新最短路径
如果第 V 次松弛还能更新距离，说明存在负权环
时间复杂度：O(V * E)

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// Bellman-Ford 算法实现
void bellmanFord(int src, vector<vector<pair<int, int>>>& graph, int n) {
    vector<int> dist(n, INT_MAX);  // 初始化距离为无穷大
    dist[src] = 0;  // 源节点到自己的距离为 0
    
    // 进行 V-1 次松弛操作
    for (int i = 0; i < n - 1; i++) {
        for (int u = 0; u < n; u++) {
            // 遍历节点 u 的所有边
            for (auto& edge : graph[u]) {
                int v = edge.first;       // 邻居节点
                int weight = edge.second; // 边的权重
                
                // 松弛操作
                if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }
    }
    
    // 检测负权环：如果还能松弛，说明存在负权环
    for (int u = 0; u < n; u++) {
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                cout << "图中存在负权环！" << endl;
                return;
            }
        }
    }
    
    // 输出结果
    cout << "从节点 " << src << " 到各节点的最短距离:\n";
    for (int i = 0; i < n; i++) {
        if (dist[i] == INT_MAX) {
            cout << "到节点 " << i << ": 不可达" << endl;
        } else {
            cout << "到节点 " << i << ": " << dist[i] << endl;
        }
    }
}

int main() {
    int n = 5;
    vector<vector<pair<int, int>>> graph(n);
    
    // 构建带权有向图（可以有负权边）
    graph[0] = {{1, -1}, {2, 4}};
    graph[1] = {{2, 3}, {3, 2}, {4, 2}};
    graph[2] = {};
    graph[3] = {{2, 5}, {1, 1}};
    graph[4] = {{3, -3}};
    
    bellmanFord(0, graph, n);
    
    return 0;
}

6. 最小生成树：Prim 算法

思路解析：

Prim 算法用于求无向连通图的最小生成树（MST）
贪心策略：从任意节点开始,每次选择连接已访问节点和未访问节点的最小权重边
使用优先队列优化，维护当前可选的最小边
时间复杂度：O((V + E) log V)

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// Prim 算法实现
int prim(vector<vector<pair<int, int>>>& graph, int n) {
    vector<bool> inMST(n, false);  // 标记节点是否在 MST 中
    vector<int> key(n, INT_MAX);   // 记录连接到 MST 的最小边权重
    
    // 优先队列：pair<权重, 节点>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    int mstWeight = 0;  // MST 的总权重
    key[0] = 0;         // 从节点 0 开始
    pq.push({0, 0});
    
    while (!pq.empty()) {
        int u = pq.top().second;  // 当前权重最小的节点
        int weight = pq.top().first;
        pq.pop();
        
        // 如果节点已在 MST 中，跳过
        if (inMST[u]) continue;
        
        inMST[u] = true;      // 将节点加入 MST
        mstWeight += weight;  // 累加权重
        
        // 遍历当前节点的所有邻居
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;
            
            // 如果邻居不在 MST 中，且边权重更小，则更新
            if (!inMST[v] && w < key[v]) {
                key[v] = w;
                pq.push({w, v});
            }
        }
    }
    
    return mstWeight;
}

int main() {
    int n = 5;
    vector<vector<pair<int, int>>> graph(n);
    
    // 构建无向带权图
    graph[0] = {{1, 2}, {3, 6}};
    graph[1] = {{0, 2}, {2, 3}, {3, 8}, {4, 5}};
    graph[2] = {{1, 3}, {4, 7}};
    graph[3] = {{0, 6}, {1, 8}};
    graph[4] = {{1, 5}, {2, 7}};
    
    int mstWeight = prim(graph, n);
    cout << "最小生成树的总权重: " << mstWeight << endl;
    
    return 0;
}

7. 最小生成树：Kruskal 算法

思路解析：

Kruskal 算法也用于求最小生成树，基于边的贪心算法
将所有边按权重排序，依次选择权重最小的边，如果该边不会形成环则加入 MST
使用并查集（Union-Find）来检测环
时间复杂度：O(E log E)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 边的结构体
struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) cons

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

C++八股文全集文章被收录于专栏

本专栏系统梳理C++技术面试核心考点，涵盖语言基础、面向对象、内存管理、STL容器、模板编程及经典算法。从引用指针、虚函数表、智能指针等底层原理，到继承多态、运算符重载等OOP特性从const、static、inline等关键字辨析，到动态规划、KMP算法、并查集等手写实现。每个知识点以面试答题形式呈现，注重原理阐述而非冗长代码，帮助你快速构建完整知识体系，从容应对面试官提问，顺利拿下offer。