简单图及其存储

简单图及其存储

图的定义与相关概念；图的表示与存储：邻接矩阵；图的表示与存储：邻接表。

概念

图由顶点集 $V$ 与边集 $E$ 组成，描述多对多关系。无向边 $(u,v)$ 与 $(v,u)$ 等价；有向边 $u\to v$ 区分方向。顶点的度：无向图中与顶点关联的边数；有向图分入度、出度。简单图无自环、无重边。邻接矩阵：$n\times n$ 数组，mat[i][j] 表示 $i$ 到 $j$ 是否有边，适合稠密图、$O(1)$ 判边。邻接表：每个顶点挂一条边链表（或 vector），存所有邻接点，适合稀疏图、省空间。与 cspj.ds.tree：树是无环连通图，是图的特例；与 cspj.algo.graph-traversal：本叶考概念与存储，DFS/BFS 遍历算法在算法叶。

CSP-J 常考

• cspj-r1-2020 第 8 题：10 个顶点的无向图至少多少条边才是连通图（树边数 $n-1$）。
• cspj-r1-2021 第 6 题：$n$ 顶点 $m$ 边的无向连通图（$m>n$），删掉多少条边可变成一棵树。
• cspj-r1-2022 第 9 题：$N$ 顶点有向连通图的邻接矩阵至少多少个非零元素。
• cspj-r1-2024 第 11 题：无向图所有顶点度数之和等于边数的几倍。
• cspj-r1-2025 第 5 题：有向图所有入度之和 = 所有出度之和 = 边数（握手定理的有向版）。

const int N = 50;
int n, m;
bool adj[N + 1][N + 1];   // 邻接矩阵，adj[u][v]=1 表示 u→v 有边

void addEdge(int u, int v) {
    adj[u][v] = adj[v][u] = 1;   // 无向图对称
}

易错点

• 无向图度数之和 = 2×边数（每条边贡献两个端点各一度）；有向图入度总和 = 出度总和 = 边数。
• $n$ 个顶点连通无向图至少 $n-1$ 条边；再多出的边数 $m-(n-1)$ 是要删的环边数（2021 第 6 题形态）。
• 邻接矩阵「至少几个非零」：有向连通至少 $n-1$ 条边对应 $n-1$ 个非零（不含对角），不要误选 $n^2$。
• 不要把「图」与「网络图 / 流程图」混为一谈——初赛考的是数据结构意义上的图。