C++ 图论基础与实战应用 | 极客日志

C++算法

C++ 图论基础与实战应用

图论通过顶点和边描述对象间的关系，在 C++ 中常用邻接表或邻接矩阵存储。深度优先搜索（DFS）和广度优先搜索（BFS）是遍历图的基础，Dijkstra 算法用于解决单源最短路径问题。涵盖图的基本概念、C++ 实现方式及典型算法示例，适合希望掌握图算法核心逻辑的开发者参考。

PgDevote发布于 2026/2/2更新于 2026/4/251 浏览

C++ 图论基础与实战应用

图论简介

如果你正在学习 C++ 并接触算法，图论是一个绕不开的话题。它用数学语言描述了现实世界中复杂的连接关系。

什么是图？

图由顶点（Vertex）和边（Edge）组成。点代表实体，线代表关系。

社交网络的好友关系
地图上的地点与道路
网页之间的超链接

在 C++ 中表示图

计算机处理图主要有两种结构，选择哪种取决于图的密度。

邻接表

适合稀疏图，每个顶点维护一个邻居列表。

#include <vector>
using namespace std;

int n = 5;
vector<vector<int>> graph(n);
// 添加无向边
graph[0].push_back(1);
graph[1].push_back(0);

这种方式空间效率高，查询邻居时直接遍历列表。

邻接矩阵

适合稠密图，用二维数组记录连通性。

#include <vector>
using namespace std;

int n = 5;
vector<vector<bool>> matrix(n, vector<bool>(n, false));
// 连接顶点 0 和 1
matrix[0][1] = true;
matrix[1][0] = true;

if (matrix[0][1]) {
    cout << "0 和 1 是相连的" << endl;
}

查询两点是否相连的时间复杂度为 O(1)，但空间占用随顶点数平方增长。

遍历图中的每一个顶点

void dfs(int node, vector<bool>& visited, const vector<vector<int>>& graph) {
    visited[node] = true;
    cout << "拜访顶点：" << node << endl;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, graph);
        }
    }
}

#include <queue>
void bfs(int start, const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        cout << "拜访顶点：" << current << endl;
        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

#include <queue>
#include <climits>
vector<int> dijkstra(int start, const vector<vector<pair<int, int>>>& graph) {
    int n = graph.size();
    vector<int> distance(n, INT_MAX);
    // 使用优先队列优化，默认最大堆，存负值模拟最小堆
    priority_queue<pair<int, int>> pq;
    distance[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        int dist = -pq.top().first;
        int node = pq.top().second;
        pq.pop();
        if (dist > distance[node]) continue;
        for (auto& edge : graph[node]) {
            int neighbor = edge.first;
            int weight = edge.second;
            if (distance[node] + weight < distance[neighbor]) {
                distance[neighbor] = distance[node] + weight;
                pq.push({-distance[neighbor], neighbor});
            }
        }
    }
    return distance;
}

#include <iostream>
#include <vector>
#include <queue>
class SocialNetwork {
private:
    vector<vector<int>> friends;
public:
    SocialNetwork(int n) : friends(n) {}
    void addFriendship(int a, int b) {
        friends[a].push_back(b);
        friends[b].push_back(a);
    }
    int findConnectionLevel(int person1, int person2) {
        int n = friends.size();
        vector<bool> visited(n, false);
        queue<pair<int, int>> q; // (人，距离)
        visited[person1] = true;
        q.push({person1, 0});
        while (!q.empty()) {
            auto [current, dist] = q.front();
            q.pop();
            if (current == person2) {
                return dist;
            }
            for (int friendId : friends[current]) {
                if (!visited[friendId]) {
                    visited[friendId] = true;
                    q.push({friendId, dist + 1});
                }
            }
        }
        return -1;
    }
};