C++ 图论基础与遍历算法详解
一、图的基础概念
在深入代码之前,先理清几个核心术语,这决定了后续存储和遍历的逻辑。
- 结点:图中的点,由边连接。
- 出边/入边:有向图中,从 A 指向 B 的边是 A 的出边,B 的入边。对应的数量称为出度和入度。
- 度数:无向图中指与该点相连的边数;有向图中为出度加入度。
- 点权/边权:分别代表结点和边的权重(如距离、价值)。
- 连通图:任意两点间都可达(通常针对无向图)。
- 完全图:任意两点间都有边直接相连。
图的存储主要有两种方式,选择哪种取决于图的密度和具体算法需求。
二、图的存储方式
1. 邻接表
适合稀疏图,空间效率高。
结构定义:
const int N = 1005;
vector<pair<int, int>> g[N]; // g[x] 存储 x 的所有出点及边权
g[i][j] 是一个 pair,第一个元素是目标节点编号,第二个是边权。若未标注边权,默认视为 0。
示例:
g[1] = {{2, 0}, {3, 0}}:结点 1 指向 2 和 3,边权均为 0。g[6] = {{3, 7}}:结点 6 指向 3,边权为 7。
2. 邻接矩阵
适合稠密图或需要频繁查询两点间是否有边的场景。
定义:
用 d[i][j] 表示 i 到 j 的距离。若无边,设为无穷大(inf)。
遍历注意: 若要枚举某点的所有出点,需遍历所有列并判断是否不为 inf。对于 Floyd 等算法,这是首选结构。
三、图的遍历
1. DFS(深度优先搜索)
通俗讲就是'一条路走到黑'。递归实现最直观。
const int N = 1005;
bitset<N> vis; // 标记访问状态
vector<int> g[N];
void dfs(int x) {
vis[x] = true; // 标记当前点已访问
for (const auto& y : g[x]) {
if (vis[y]) ;
(y);
}
}


