C++ 图论基础与遍历算法

C++ 图论基础与遍历算法

一、图的基础概念

1. 结点：图中的点，结点间由边连接。
2. 出边：从 A 指向 B 的边 E，是 A 的出边；出边数量叫出度。
3. 入边：从 A 指向 B 的边 E，是 B 的入边；入边数量叫入度。
4. 度数：某个点的出边 + 入边总数（无向图中对应边数）。
5. 点权：结点上的权重（可表示价值、重要程度等）。
6. 边权：边上的权重。
7. 有向图：图中的边是有向边（有方向）。
8. 无向图：图中的边是无向边（无方向）。
9. 完全图：任意两个点之间都有一条边相连。
10. 连通图：任意两个点之间都可达，一般用于无向图。
11. 图的存储方式
    • 主要有邻接矩阵（如用 d[i][j] 表示）和邻接表（常用 vector 或'前向星'实现）两种。
    • 多数情况用邻接表；邻接矩阵常用于 Floyd 算法等场景。

二、图的存储方式

1. 邻接表

1. 存储结构：用 vector<pair<int, int>> g[N] 表示，其中：

• g[x] 存储结点 x 的所有出点信息；
• g[i][j] = {first, second}：first 是从 i 出发的某个出点的编号，second 是这条边的边权。

2. 示例（对应上图，未标注边权默认为 0）：

• g[1] = {{2, 0}, {3, 0}}（结点 1 的出点是 2、3，边权为 0）；
• g[6] = {{3, 7}}（结点 6 的出点是 3，边权为 7）；
• g[4] = {{5, 0}, {6, 0}}（结点 4 的出点是 5、6，边权为 0）。

2. 邻接矩阵

1. 定义：用 d[i][j] 表示从结点 i 到 j 的边的距离（通常代表最短距离）；若 i 到 j 无边，则 d[i][j] = inf（无穷大）。

2. 示例（对应上图）：

• d[1,2] = 0（结点 1 到 2 的边权为 0）；
• d[6,3] = 7（结点 6 到 3 的边权为 7）；
• d[4,3] = inf（结点 4 到 3 无边）。

3. 遍历出点的方式：若要枚举某个点的所有出点，需遍历所有点，再判断 d[当前点][遍历点] 是否不为 inf。