軟體工程師職涯升級計畫啟動！立即預約職涯諮詢、履歷健檢或模擬面試👈，為您的加薪做好準備！
什麼是圖（Graph）？
圖是一種非線性的資料結構，它由兩個基本元素構成：節點（vertex）和邊（edge）。我們可以將圖想像成一張地圖，其中每個城市是節點，而連接城市之間的道路就是邊。
- 節點（Vertex）：也稱為頂點或節點（node），代表資料元素。通常用 V 或 V(G) 表示所有節點的集合。
- 邊（Edge）：代表節點之間的連結關係。一條邊通常由一對節點 (u,v) 表示。所有邊的集合用 E 或 E(G) 表示。
因此，一個圖 G 就是一個由節點集合 V 和邊集合 E 組成的結構，通常寫作 G(V,E)。
有向圖與無向圖
根據邊是否具有方向性，圖可以分為兩種類型：
- 無向圖（Undirected Graph）：邊不具有方向性。如果節點 A 和 B 之間有一條邊，表示從 A 可以到達 B，同時也可以從 B 到達 A。例如，朋友關係就是一種無向圖：如果你是我的朋友，那我也是你的朋友。
- 有向圖（Directed Graph）：邊具有方向性。邊 (u,v) 表示可以從 u 到達 v，但不一定能從 v 到達 u。例如，大學課程的先修關係就是一種有向圖：要修習「資料結構」，必須先完成「程式設計」這門課。
圖的常見應用
圖結構在電腦科學和現實世界中應用廣泛，以下是一些經典例子：
- 最短路徑問題（Shortest Path）：這是圖中最常見的問題之一。例如，Google Maps 就是用圖來計算兩點之間的最短行車路線。
圖的程式碼實現
在程式中，我們可以用不同的方式來表示圖，最常見的是鄰接矩陣（Adjacency Matrix）和鄰接列表（Adjacency List）。
1. 鄰接矩陣（Adjacency Matrix）
這是一個二維陣列（矩陣），matrix[i][j] 的值用來表示節點 i 和節點 j 之間是否有邊。如果圖是加權的，matrix[i][j] 可以儲存邊的權重。
- 優點：查找兩個節點之間是否有邊的速度非常快，時間複雜度為 O(1)。
- 缺點：如果節點數量多但邊很少（稀疏圖），會浪費大量記憶體空間。
// 使用鄰接矩陣實現無向圖
class GraphMatrix {
constructor(numVertices) {
this.numVertices = numVertices;
this.adjMatrix = Array(numVertices)
.fill(null)
.map(() => Array(numVertices).fill(0));
}
// 新增一個節點
addVertex(v) {
// 鄰接矩陣無法動態增加節點，因此通常在初始化時就確定節點數
console.log("Cannot add vertex to a fixed-size adjacency matrix.");
}
// 新增一條邊
addEdge(v1, v2) {
if (v1 >= 0 && v1 < this.numVertices && v2 >= 0 && v2 < this.numVertices) {
this.adjMatrix[v1][v2] = 1;
this.adjMatrix[v2][v1] = 1; // 無向圖，是對稱的
}
}
// 移除一條邊
removeEdge(v1, v2) {
if (v1 >= 0 && v1 < this.numVertices && v2 >= 0 && v2 < this.numVertices) {
this.adjMatrix[v1][v2] = 0;
this.adjMatrix[v2][v1] = 0;
}
}
// 檢查兩個節點是否相連
hasEdge(v1, v2) {
if (v1 >= 0 && v1 < this.numVertices && v2 >= 0 && v2 < this.numVertices) {
return this.adjMatrix[v1][v2] === 1;
}
return false;
}
}
// 範例
const graphMatrix = new GraphMatrix(5); // 建立一個有5個節點的圖
graphMatrix.addEdge(0, 1);
graphMatrix.addEdge(0, 4);
graphMatrix.addEdge(1, 2);
graphMatrix.addEdge(1, 3);
graphMatrix.addEdge(1, 4);
graphMatrix.addEdge(2, 3);
graphMatrix.addEdge(3, 4);
console.log(graphMatrix.adjMatrix);
/* 輸出：
[
[0, 1, 0, 0, 1],
[1, 0, 1, 1, 1],
[0, 1, 0, 1, 0],
[0, 1, 1, 0, 1],
[1, 1, 0, 1, 0]
]
*/
2. 鄰接列表（Adjacency List）
這是一種陣列與鍊結串列（或 JavaScript 中的 Map / 陣列）結合的表示法。用一個 Map 來儲存所有節點，Map 的鍵（key）對應一個節點，值（value）則是一個陣列，用來儲存與該節點相連的所有鄰居節點。
- 優點：記憶體空間利用率高，特別適合稀疏圖。且可以動態增加、刪除節點。
- 缺點：查詢兩個節點之間是否有邊需要遍歷該節點的鄰接列表，時間複雜度為 O(∣V∣)，而鄰接矩陣為 O(1)。
// 使用鄰接列表實現無向圖
class GraphList {
constructor() {
this.adjList = new Map(); // 使用 Map 存儲鄰接列表
}
// 新增一個節點
addVertex(v) {
if (!this.adjList.has(v)) {
this.adjList.set(v, []);
}
}
// 新增一條邊
addEdge(v1, v2) {
// 確保兩個節點都存在
if (!this.adjList.has(v1)) {
this.addVertex(v1);
}
if (!this.adjList.has(v2)) {
this.addVertex(v2);
}
// 如果邊不存在才新增
if (!this.adjList.get(v1).includes(v2)) {
this.adjList.get(v1).push(v2);
}
if (!this.adjList.get(v2).includes(v1)) {
this.adjList.get(v2).push(v1); // 無向圖
}
}
// 移除一個節點
removeVertex(v) {
if (this.adjList.has(v)) {
// 移除所有指向該節點的邊
for (let neighbor of this.adjList.get(v)) {
this.adjList.set(neighbor, this.adjList.get(neighbor).filter(node => node !== v));
}
// 最後移除該節點
this.adjList.delete(v);
}
}
// 移除一條邊
removeEdge(v1, v2) {
if (this.adjList.has(v1) && this.adjList.has(v2)) {
this.adjList.set(
v1,
this.adjList.get(v1).filter((v) => v !== v2)
);
this.adjList.set(
v2,
this.adjList.get(v2).filter((v) => v !== v1)
);
}
}
// 檢查兩個節點是否相連
hasEdge(v1, v2) {
if (this.adjList.has(v1) && this.adjList.has(v2)) {
return this.adjList.get(v1).includes(v2);
}
return false;
}
}
// 範例
const graphList = new GraphList();
graphList.addVertex('A');
graphList.addVertex('B');
graphList.addVertex('C');
graphList.addEdge('A', 'B');
graphList.addEdge('A', 'C');
graphList.addEdge('B', 'C');
console.log(graphList.adjList);
/* 輸出：
Map(3) {
'A' => [ 'B', 'C' ],
'B' => [ 'A', 'C' ],
'C' => [ 'A', 'B' ]
}
*/
LeetCode 實戰範例：圖的遍歷
題目： LeetCode 200. Number of Islands（島嶼數量）
題目描述：
給定一個由 '1'（陸地）和 '0'（水）組成的 mtimesn 二維網格地圖，計算地圖中島嶼的數量。一個島嶼是由相鄰（水平或垂直）的陸地組成的，周圍被水環繞。
解題思路：
這是一個典型的圖遍歷問題。我們可以將網格中的每個陸地（'1'）視為圖中的一個節點，相鄰的陸地則有邊相連。我們的目標是計算圖中有多少個連通分量（connected components）。
我們可以使用 深度優先搜尋（DFS） 或 廣度優先搜尋（BFS） 來解決這個問題。
DFS 解法：
- 初始化一個變數 count 來計數島嶼數量。
- 遍歷網格中的每一個單元格。
- 如果當前單元格是陸地（'1'），表示我們找到了一個新的島嶼。將 count 加一。
- 對這個陸地單元格執行 DFS 遍歷，將它以及所有與它相連的陸地都標記為已訪問（例如，將 '1' 變成 '0'），以避免重複計算。
- DFS 函數會遞迴地訪問當前單元格的上下左右四個方向的鄰居。如果鄰居也是陸地且沒有被訪問過，則繼續對鄰居執行 DFS。
- 遍歷結束後，count 就是島嶼的總數。
JavaScript 程式碼（DFS）：
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function (grid) {
if (!grid || grid.length === 0) {
return 0;
}
const rows = grid.length;
const cols = grid[0].length;
let count = 0;
// DFS 輔助函數
const dfs = (r, c) => {
// 邊界條件檢查
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') {
return;
}
// 將當前節點標記為已訪問（'0'）
grid[r][c] = '0';
// 遞迴地訪問上下左右的鄰居
dfs(r + 1, c); // 下
dfs(r - 1, c); // 上
dfs(r, c + 1); // 右
dfs(r, c - 1); // 左
};
// 遍歷整個網格
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') {
count++; // 找到一個新的島嶼
dfs(r, c); // 執行 DFS 遍歷，將整個島嶼標記
}
}
}
return count;
};
總結
圖（Graph）作為一種強大的非線性資料結構，透過節點（Vertex）和邊（Edge）來表示複雜的關係網絡。無論是有向圖還是無向圖，它們在現實世界的應用無處不在，從社交網絡到地圖導航，甚至是電腦網路的拓撲結構。
在程式碼實現上，**鄰接列表（Adjacency List）和鄰接矩陣（Adjacency Matrix）**是最常見的兩種方式，各有其優缺點。鄰接列表在處理稀疏圖時更具空間效率，而鄰接矩陣則在查詢兩節點之間是否有邊時更快速。掌握這些基本概念和實現方法，是解決許多複雜演算法問題的關鍵，例如尋找最短路徑或計算連通分量等。
