圖是資料結構中非常強大的抽象模型,適合用來表示網路、路線、社交關係、依賴關係與狀態轉移等問題。與樹狀結構相比,圖的連接方式更自由,一個節點可以有多個相鄰節點,因此演算法設計也更多樣。
圖通常由頂點與邊組成,可表示為 G(V, E),其中 V 是頂點集合,E 是邊集合。
若邊具有方向,則稱為有向邊,也稱為弧。通常用 <Vi, Vj> 表示,Vi 是弧尾,Vj 是弧頭。
若邊沒有方向,則稱為無向邊,通常用 (Vi, Vj) 表示。
若圖中不存在頂點到自身的邊,且同一條邊不重複出現,則稱為簡單圖。
可以建立 Vertex 類別來表示頂點:
function Vertex(label) {
this.label = label;
}
圖的邊可以透過鄰接表表示。每個頂點對應一個陣列,陣列中存放與它相鄰的頂點。
function Graph(v) {
this.vertices = v;
this.edges = 0;
this.adj = [];
for (var i = 0; i < this.vertices; ++i) {
this.adj[i] = [];
this.adj[i].push('');
}
this.addEdge = addEdge;
this.toString = toString;
}
function addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
圖的遍歷是圖演算法中非常基礎的操作。常見方式包括深度優先搜尋與廣度優先搜尋。
深度優先搜尋,簡稱 DFS,會沿著一條路徑持續往下探索,直到沒有未訪問節點,再回溯。
實作時通常需要一個陣列來記錄節點是否已訪問:
this.marked = [];
for (var i = 0; i < this.vertices; ++i) {
this.marked[i] = false;
}
function dfs(v) {
this.marked[v] = true;
if (this.adj[v] !== undefined) {
print('Visited vertex: ' + v);
for (var i = 0; i < this.adj[v].length; i++) {
var w = this.adj[v][i];
if (!this.marked[w]) {
this.dfs(w);
}
}
}
}
廣度優先搜尋,簡稱 BFS,會先訪問離起點最近的節點,再逐層向外擴展。它常用於最短路徑、層級遍歷與迷宮求解等問題。
function bfs(s) {
var queue = [];
this.marked[s] = true;
queue.push(s);
while (queue.length > 0) {
var v = queue.shift();
if (v !== undefined) {
print('Visited vertex: ' + v);
}
for (var i = 0; i < this.adj[v].length; i++) {
var w = this.adj[v][i];
if (!this.marked[w]) {
this.edgeTo[w] = v;
this.marked[w] = true;
queue.push(w);
}
}
}
}
在廣度優先搜尋過程中,若記錄每個節點是從哪個節點被發現的,就能還原最短路徑。這通常需要一個 edgeTo 陣列。
this.edgeTo = [];
在 BFS 中,當發現新節點時,可以記錄它的前驅節點:
this.edgeTo[w] = v;
這樣一來,從目標節點沿著 edgeTo 回溯,就能得到路徑。
拓撲排序常用於有向無環圖,目的是將所有頂點排成一列,使得所有有向邊都從前面的頂點指向後面的頂點。它常用於任務排程、套件依賴與課程先修順序等場景。
拓撲排序可以透過深度優先搜尋變化而來。核心概念是:拜訪節點時先遞迴處理相鄰節點,等所有相鄰節點都處理完,再把目前節點推入堆疊。
function topSort() {
var stack = [];
var visited = [];
for (var i = 0; i < this.vertices; i++) {
visited[i] = false;
}
for (var i = 0; i < this.vertices; i++) {
if (visited[i] === false) {
this.topSortHelper(i, visited, stack);
}
}
for (var i = 0; i < stack.length; i++) {
if (stack[i] !== undefined && stack[i] !== false) {
print(this.vertexList[stack[i]]);
}
}
}
function topSortHelper(v, visited, stack) {
visited[v] = true;
for (var i = 0; i < this.adj[v].length; i++) {
var w = this.adj[v][i];
if (!visited[w]) {
this.topSortHelper(w, visited, stack);
}
}
stack.push(v);
}
圖與圖演算法是資料結構中非常重要的一部分。從鄰接表表示、DFS、BFS,到最短路徑與拓撲排序,這些概念不僅能幫助我們解決演算法題目,也能應用於真實系統中的依賴分析、網路路由與排程問題。