5.8.3 邻接表与邻接矩阵

表示一个图的节点间连接关系，需要用邻接表或邻接矩阵，一般在稀疏图上，即节点较多，边数较少时使用邻接表。邻矩阵使用二维数组，邻接表使用 vector 数组或链式前向星（数组模拟链表），这里只介绍更好理解的 vector 数组。

一般来说，题目会给节点编号，通常为 到 的整数。

邻接矩阵

用一个二维数组G[][]存放图， G[i][j] 表示节点 i 和节点 j 之间边的情況（如有无边，边方向，权值大小等）。

遍历复杂度：#card=math&code=O%28n%C2%B2%29&id=bFkyB) , 为节点数。

邻接表

每个节点对应一个一维vector，里面存放从节点连出去的边，边的信息包括另一顶点，还可能包含边权值等（此时 vector 存储具有多个成员的数据类型，如：struct，pair）。

遍历复杂度：#card=math&code=O%28n%20%2B%20m%29&id=nV8a9) ， 为节点数， 为边数。

使用邻接表存储边时，参考示例代码：

vector<int> g[N];    // 邻接表
// 有向图，添加一条 u -> v 的有向边
void read(int u, int v) {
    g[u].push_back(v);
}
// 无向图，添加一条 u - v 的无向边
void read(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

访问节点，读取邻接表的一个例子：

for (int u=1; u<=n; ++u) {    // 遍历所有起点
    for (int j=0; j<g[u].size(); ++j) {    // 遍历当前点的所有出边
        int v = g[u][j];    // 当前边的终点
    }
}

在后续图的算法中，会反复使用到邻接表。