---

場景設定

想象你是一個社交達人，要記錄你和所有朋友的關系（這就是“圖”）。每個朋友是一個節點，關系是一條邊。你需要快速回答：“我有哪些朋友？”（遍歷鄰居）。

---

方式1：鏈式前向星（固定小本本）

• 核心思想：你買了一個固定頁數的筆記本（預分配的數組）。

• 怎么記？

  1. 給每個朋友一個專屬頁（head[你]）。
  2. 每認識一個新朋友，就在筆記本最新空白頁記錄：
     • 朋友名字 (to)
     • 和你的關系 (weight，可選)
     • 關鍵！ 還要寫上“上一個記錄在筆記本第幾頁？” (next)
  3. 更新你的專屬頁：寫上最新這條記錄的頁碼。

• 通俗比喻：

  • 你的筆記本就是 edges[] 數組（每條邊占一頁）。
  • head[你] 是你名字標簽貼紙指向的最新記錄頁碼。
  • next 就像是“上一條記錄在第幾頁？”的提示。
  • 要查所有朋友？從 head[你] 找到最新記錄，然后根據 next 翻到前一頁，再前一頁…直到沒記錄了（next = -1）。

優點

1. 省空間（內存少）：
   • 筆記本只記核心信息（朋友名、關系、上條頁碼），沒有多余開銷。
   • vector 像活頁夾，每頁本身還有夾子、標簽等額外重量（vector 的容量指針、大小等元數據）。
2. 加朋友超快（O(1)）：
   • 直接寫在最新空白頁，更新你的標簽貼紙 (head) 就行。固定操作，永不拖延。
3. 筆記本整齊（內存連續）：
   • 所有記錄按頁碼連續存放。CPU 一次“搬”一摞記錄進緩存效率高（緩存友好），但翻頁查找過程不連續。

缺點

1. 筆記本頁數固定（靜態大小）：
   • 買的時候要猜最多交多少朋友。朋友太多？本子寫滿了，得重買更大的本子，全部重抄一遍（重新初始化，擴容麻煩）。
2. 絕交（刪除邊）超麻煩：
   • 想刪掉一個朋友的記錄？你得順著鏈條一頁頁找，找到后還要修改它前后記錄的 next 指向，像拆掉一節火車車廂。幾乎沒人用鏈式前向星刪邊。
3. 查朋友名單有點慢（遍歷效率）：
   • 雖然記錄在物理上是連續的，但你查名單時是根據 next 跳著翻頁（第 5 頁 -> 第 2 頁 -> 第 8 頁）。翻頁動作不連貫，CPU 緩存可能幫不上忙。
4. 寫起來費勁（代碼復雜）：
   • 你得自己維護 head 和每條記錄的 next 指針。寫代碼時容易搞暈，調試也麻煩。

代碼：

#include <bits/stdc++.h> 
using namespace std;
const int N = 1000;  // 最大節點數
const int M = 10000; // 最大邊數// 定義邊的結構體
struct Edge {int to;     // 這條邊指向哪個節點int next;   // 同一個起點的下一條邊的索引（相當于"上一條記錄的頁碼"）int w;      // 邊權（可選）
} edges[M];  // 存儲所有邊的數組int head[N]; // head[u] 表示節點 u 的第一條邊的索引（初始為 -1）
int idx = 0;    // 當前邊的索引（相當于"最新空白頁的頁碼"）// 添加一條從 u 到 v 的邊，權重為 w
void addEdge(int u, int v, int w) {edges[idx].to = v;       // 記錄這條邊指向 vedges[idx].w = w;        // 記錄邊權edges[idx].next = head[u]; // 新邊的 next 指向 u 原來的第一條邊head[u] = idx++;         // 更新 u 的第一條邊為當前這條邊
}// 遍歷節點 u 的所有鄰居
void printNeighbors(int u) {cout << "節點 " << u << " 的朋友: ";for (int i = head[u]; i != -1; i = edges[i].next) {int v = edges[i].to;int w = edges[i].w;cout << v << "(親密度:" << w << ") ";}cout << endl;
}int main() {memset(head, -1, sizeof(head)); // 初始化 head 數組為 -1（表示空鏈表）// 添加邊：0 -> 1 (權重 5), 0 -> 2 (權重 3), 1 -> 2 (權重 2)addEdge(0, 1, 5);addEdge(0, 2, 3);addEdge(1, 2, 2);// 打印鄰居printNeighbors(0); // 輸出: 節點 0 的朋友: 2(親密度:3) 1(親密度:5)printNeighbors(1); // 輸出: 節點 1 的朋友: 2(親密度:2)return 0;
}

關鍵點

• head[u] 存儲節點 u 的最新一條邊的索引（類似鏈表頭指針）。
• edges[idx] 存儲所有邊，idx 是當前可用的邊索引（類似動態分配的頁數）。
• next 指向同起點的上一條邊（類似鏈表的前驅指針）。
• 遍歷時，從 head[u] 開始，沿著 next 走，直到 -1（類似鏈表遍歷）。

適合誰？ 朋友數量上限確定（比如競賽題已知最大點數/邊數），追求極致速度和省內存的“極客”。

---

方式2：Vector 鄰接表（活頁文件夾）

• 核心思想：你買了一個帶標簽的活頁文件夾。給每個朋友（包括你自己）分配一個專屬分區。

• 怎么記？

  1. 想加一個新朋友“老王”？
  2. 直接找到你自己的分區。
  3. 在分區里新加一頁活頁紙，寫上“老王”和你們的關系（vector[你].push_back(Edge{老王, 關系})）。

• 通俗比喻：

  • 文件夾是 vector > graph。
  • 每個分區是 graph[你]、graph[朋友A]、graph[朋友B]…
  • 每個分區里的活頁紙就是該節點的所有鄰居邊記錄。

優點

1. 分區獨立，無限加頁（動態擴容）：
   • 你的分區寫滿了？系統自動給你換更大的分區頁夾（vector 自動擴容）。雖然換的時候要復印所有舊頁（復制數據），但均攤下來每次加頁還是很快（均攤 O(1)）。
2. 查朋友名單超快（遍歷高效）：
   • 打開你自己的分區，里面的活頁紙按添加順序疊放（內存連續）。你可以一口氣從頭翻到尾，翻頁動作流暢，CPU 緩存瘋狂點贊！
3. 用起來超簡單（代碼簡潔）：
   • 加朋友？一句 graph[你].push_back(老王)。查朋友？一個 for 循環遍歷 graph[你]。邏輯清晰，不易出錯。
4. 額外功能強大（STL支持）：
   • 想按關系親密度排序朋友？直接用 sort(graph[你].begin(), graph[你].end())。想找特定朋友？可以用 find。活頁夾兼容各種“辦公用具”（STL算法）。

缺點

1. 文件夾本身有點重（內存開銷大）：
   • 每個分區（vector）都要維護自己的“目錄”（容量、大小等元數據）。朋友非常多時，比鏈式前向星多占 20%-50% 內存。
2. 換分區頁夾時手忙腳亂（擴容開銷）：
   • 雖然系統自動幫你換，但換的那一刻（擴容）要把所有舊頁復印到新分區，這時添加操作會短暫變慢（雖然均攤后很快，但有波動）。
3. 撕掉某頁很麻煩（刪除邊低效）：
   • 想刪掉分區中間一頁？你得把后面所有頁往前挪一格（vector 刪除中間元素 O(度數)）。除非你總是刪最后一頁（pop_back）。
4. 分區分散（內存不連續）：
   • 你的分區、朋友A的分區、朋友B的分區在文件夾里可能不挨著。雖然每個分區內部連續，但訪問不同節點時，CPU 可能要在文件夾里跳來跳去。

適合誰？ 朋友數量不確定或經常變，追求代碼好寫、好讀、易維護的“務實派”。絕大多數工程項目的首選。

代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 1000; // 最大節點數// 定義邊的結構體（比鏈式前向星更簡單，不需要 next）
struct Edge {int to; // 這條邊指向哪個節點int w;  // 邊權（可選）
};vector<Edge> graph[N]; // graph[u] 存儲節點 u 的所有鄰居// 添加一條從 u 到 v 的邊，權重為 w
void addEdge(int u, int v, int w) {graph[u].push_back({v, w}); // 直接 push_back 即可
}// 遍歷節點 u 的所有鄰居
void printNeighbors(int u) {cout << "節點 " << u << " 的朋友: ";for (Edge e : graph[u]) {cout << e.to << "(親密度:" << e.w << ") ";}cout << endl;
}int main() {// 添加邊：0 -> 1 (權重 5), 0 -> 2 (權重 3), 1 -> 2 (權重 2)addEdge(0, 1, 5);addEdge(0, 2, 3);addEdge(1, 2, 2);// 打印鄰居printNeighbors(0); // 輸出: 節點 0 的朋友: 1(親密度:5) 2(親密度:3)printNeighbors(1); // 輸出: 節點 1 的朋友: 2(親密度:2)return 0;
}

關鍵點

• graph[u] 是一個 vector，直接存儲 u 的所有鄰居邊。
• 添加邊直接用 push_back，無需維護 next 指針。
• 遍歷時直接 for (Edge e : graph[u])，比鏈式前向星更直觀。

---

總結

總的來說，兩款存圖方式各有優劣，具體取決于需求和喜好