◎学完你会
- 用邻接矩阵存稠密图，会查两点间是否直连、取边权；
- 用邻接表存稀疏图，
vector<int> g[N] 加边；
- 认识链式前向星：数组模拟链表，内存紧凑适合大图。
1动一动：同一张图，三种存法
下图为 5 点 5 边的无向带权图。点三个按钮，看同一张图怎么变成三种数据结构；再点某条边，看它在每种存法里的表示：
点按钮切换存法。这是一张 5 点 5 边无向图：1-2(5)、1-4(7)、2-3(3)、3-5(2)、4-5(1)。
三种存法都能表达同一张图，区别只在查得快还是省内存。
2关键命令：三种存法
// ① 邻接矩阵：g[i][j]=边权，稠密图
int g[5][5]; g[1][2]=5; g[2][1]=5;
查 1-2 是否直连：if(g[1][2])
// ② 邻接表：vector 存每个点的邻居
vector<int> g[5]; g[1].push_back(2); g[2].push_back(1);
遍历 1 的邻居：for(int v:g[1])
// ③ 链式前向星：数组模拟链表，h[u] 头，nxt 下一条
int h[5],to[M],w[M],nxt[M],ec=0;
void add(int u,int v,int c){ to[++ec]=v; w[ec]=c; nxt[ec]=h[u]; h[u]=ec; }
无向图邻接表必须加两次边：push_back 进 g[u] 也要进 g[v]，否则只存了单向。
⚠易错点
无向图加两次边：邻接表和链式前向星都是 add(u,v) 后再 add(v,u)，只加一次会丢一半边。
链式前向星是头插法：nxt[ec]=h[u]，新边永远插在链表头，遍历顺序和插入顺序相反。
邻接矩阵的 O(n²) 空间：n=10⁵ 时矩阵要 10¹⁰ 格，必须改用邻接表。
?跨学科：图 = 关系的地图
社交平台的好友关系就是一张无向图：邻接表像"每个人的好友列表"，邻接矩阵像"全校同学两两是否认识的关系表"。
地图导航、航班航线、蛋白质相互作用网络，都是同一套"点 + 边"的抽象——选对存法，几千到几亿条边都能装得下。
✎练一练
无向图用邻接表存一条边 (1,2)，正确做法是？
无向边是双向可达，邻接表要同时在两端各记一次——选 B。
n=10⁵、m=3×10⁵ 的稀疏图，为什么不能用邻接矩阵？
邻接矩阵需要 n² 格 ≈ 10¹⁰ 个 int，约 40GB 内存，完全放不下；且矩阵查遍全行也浪费。稀疏图用邻接表，总空间 O(n+m) 即可。