節點加邊,能表達任何關係網 —— 地圖、社群、相依關係。走訪它靠 BFS 和 DFS。
O(V+E)。
節點 + 邊 —— 節點(vertex)是東西,邊(edge)是關係。V 是節點數、E 是邊數。
有向 vs 無向 —— 邊有沒有方向:追蹤 IG(單向)是有向,互相好友是無向。
加權 vs 不加權 —— 邊有沒有數字:距離、費用、時間。
有環 vs 無環 —— 能不能繞回自己。有向無環圖(DAG)常用來排先修課、編譯相依。
鄰接表 adjacency list —— 用 dict:每個節點對到「它的鄰居清單」。最常用,稀疏圖省空間,加一條邊 O(1)。
鄰接矩陣 adjacency matrix —— V×V 的二維表,matrix[i][j] 記有沒有邊。查「兩點相不相連」O(1),但空間 O(V²)。
怎麼選 —— 大多數題目和真實網路都是稀疏的(邊遠少於 V²),所以預設用鄰接表;稠密圖或要狂查邊才用矩陣。
BFS 廣度優先 —— 用佇列,一層一層由近到遠。找「最少步數 / 最短路徑(不加權)」就用它。
DFS 深度優先 —— 用堆疊或遞迴,一條路走到底再回頭。找「連通、路徑、環、拓樸排序」常用它。
都是 O(V+E) —— 每個節點走一次、每條邊看一次。
差別只在「下一個先探誰」 —— BFS 探最早排進來的(先進先出),DFS 探最晚放進去的(後進先出)。
站是節點、路線是邊。找轉乘最少、車程最短,就是圖的最短路徑問題。
每個人是節點,朋友關係是邊。「共同朋友」「六度分隔」都是圖問題。
機場是節點,航線是邊 —— 有向(單程)、加權(票價或時間),找最便宜就是加權最短路。
同一張圖,都從 A 出發,比較兩種走訪。紫色是正在走訪的節點、琥珀色是待探清單(BFS 的佇列 / DFS 的堆疊路徑)、綠色是走完的。注意兩種走訪的順序不一樣。按「下一步」。
從建鄰接表、BFS / DFS(遞迴與迭代),到最短路徑、偵測環、連通分量、拓樸排序、Dijkstra。
❌ 無向圖只加單邊 —— 無向要 graph[u].append(v) 和 graph[v].append(u) 兩邊都加。
❌ 走訪忘了 visited —— 有環的圖不記錄走過的,會無窮迴圈。
❌ 用 BFS 找加權最短路 —— BFS 只對「不加權」的最短步數有效;有權重要用 Dijkstra。
❌ 稀疏圖用鄰接矩陣 —— 節點多、邊少時 O(V²) 空間浪費,改用鄰接表。
A-B、B-C、C-A,幾個節點、幾條邊?它的鄰接表(dict)長怎樣?把答案打到對話裡,我幫你對。