點與線
把所有細節剝掉，一張[[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 鄰接矩陣
點和線是一個想法；計算機需要把它們作為資料。有兩種標準表示法。鄰接矩陣是一張 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);