点与线
把所有细节剥掉，一张[[graph|图]]不过就是*点和线*。点是顶点（也叫节点）——那些“东西”——线是边——它们之间的关系。这就是全部定义，而它的空泛正是它的力量：每当你有*一些东西*以及*东西之间的连接*，你就有了一张图。城市与道路。人与友谊。网页与链接。任务与“必须先于”的箭头。全是同一个抽象对象。
你已经认识一个特例：[[tree|树]]不过是一张恰好有单一根、没有环、且除一个节点外人人有一个父亲的图。图把这三条规则统统扔掉。它可以有环（A→B→C→A）、有许多“父亲”的节点、互不相连的孤岛，甚至一个顶点连着自己的边。这种自由，正是图为何能把杂乱的现实世界建模得这么好。
(0)---(1) an undirected graph, 5 vertices:
| / | edges = { 0-1, 0-2, 1-2, 1-3, 3-4 }
| / |
(2) (3)---(4)
note the cycle 0-1-2-0: trees can't do this, graphs can.边的三种风味
边有几种风味，而选对哪一种，就完成了把一个问题正确建模的一半。
- 无向 — 边是双向的。友谊：你认识我，我就认识你。画成一条朴素的线。
- 有向 — 边有方向，画成箭头。推特关注：你可以关注一个不回关你的人。A→B 不蕴含 B→A。
- 带权 — 每条边带一个数字：距离、成本、行程时间。路网图的边以公里数加权。
这些可以自由组合。路网通常是无向且带权的（路两头都能走，且无论哪个方向都是 5 公里）。项目排期是有向且无权的（“打地基”必须先于“砌墙”，没得商量）。航班网络是有向且带权的（单程票，要花一笔票价）。在写代码前先把风味叫准，能让你不至于把错的东西建了模。
存一张图：邻接表 vs 邻接矩阵
点和线是一个想法；计算机需要把它们作为数据。有两种标准表示法。[[graph|邻接矩阵]]是一张 n×n 的方格，单元 `[i][j]` 在 i 到 j 有边时为 1（或为权值），否则为 0。简单，而且“i→j 之间有边吗？”是瞬时的 O(1) 查询——但它总要用掉 n² 的空间，哪怕图里只有寥寥几条边。
[[adjacency-list|邻接表]]则为每个顶点只保留一份它的邻居清单。它只用与边数一样多的空间，这正是它成为现实世界中那些大而稀疏的图的默认选择的原因（一座城市有数百万个路口，但每个只接触寥寥几条路）。在 C++ 里它无比自然：一个 `vector` 套着 `vector`。
graph: 0---1 adjacency LIST (a vector per vertex):
| /| adj[0] = {1, 2}
| / | adj[1] = {0, 2, 3}
2 3 adj[2] = {0, 1}
adj[3] = {1}
same graph as a MATRIX (m[i][j]=1 if edge i-j):
0 1 2 3 adjacency list: ~edges of space
0[0 1 1 0] matrix: always n*n space
1[1 0 1 1]
2[1 1 0 0] sparse, big graph -> use the LIST
3[0 1 0 0]#include <vector>
int n = 4;
std::vector<std::vector<int>> adj(n); // adjacency list
auto addEdge = [&](int u, int v) { // UNDIRECTED:
adj[u].push_back(v); // add both directions
adj[v].push_back(u); // (drop one line if directed)
};
addEdge(0,1); addEdge(0,2); addEdge(1,2); addEdge(1,3);