圖(Graph)由頂點的有窮非空集合與頂點之間邊的集合組成,通常表示為 G(V, E),其中 G 代表一個圖,V 是圖 G 中頂點的集合,E 是邊的集合。

有向邊:若從頂點 Vi 到 Vj 的邊帶有方向,則稱為有向邊,也稱弧(Arc),以有序偶 <Vi, Vj> 表示,Vi 稱為弧尾,Vj 稱為弧頭。

無向邊:若頂點 Vi 到 Vj 之間的邊沒有方向,則稱為無向邊(Edge),以無序偶 (Vi, Vj) 表示。
若圖中不存在頂點到其自身的邊,且同一條邊不重複出現,則稱這樣的圖為簡單圖。
建立圖類別的第一步是建立一個 Vertex 類別來保存頂點與邊,其角色和鏈表、二元搜尋樹的 Node 類別一樣。這裡的 Vertex 有兩個資料成員:一個用於標識頂點(label),另一個是表明是否被存取過的布林值(wasVisited)。
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++;
}
這裡以 for 迴圈為陣列中每個元素建立一個子陣列來儲存所有相鄰頂點,並將元素初始化為空字串。
深度優先遍歷(Depth First Search),又稱深度優先搜尋,簡稱 DFS。可以把它想像成在一個房間裡找鑰匙:從任一房間開始,把牆角、床頭櫃、床上、床下、衣櫃、電視櫃逐一找過,不放過任何死角,當抽屜與儲藏櫃全找遍後,再前往下一個房間。

其原理是:存取一個未存取過的頂點並標記為已存取,再遞歸地去存取該頂點鄰接表中其他未存取的頂點。
先為 Graph 類別添加一個用來記錄已存取頂點的陣列:
this.marked = []; // 保存已存取過的頂點
for (var i = 0; i < this.vertices; ++i){
this.marked[i] = false; // 初始化為 false
}
接著是深度優先搜尋函式:
function dfs(v){
this.marked[v] = true;
// if 判斷在此不是必須的
if (this.adj[v] != undefined){
print("Visited vertex: " + v);
for each (var w in this.adj[v]){
if (!this.marked[w]){
this.dfs(w);
}
}
}
}
廣度優先搜尋(BFS)屬於一種盲目搜尋法,目的是系統性地展開並檢查圖中的所有節點以尋找結果。也就是說,它並不考慮結果的可能位置,而是徹底搜尋整張圖,直到找到結果為止。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 each (var w in this.adj[v]){
if (!this.marked[w]){
this.edgeTo[w] = v;
this.marked[w] = true;
queue.push(w);
}
}
}
}

執行廣度優先搜尋時,會自動查找從一個頂點到另一個相連頂點的最短路徑。
要查找最短路徑,需修改 BFS 演算法來記錄從一個頂點到下一個頂點的所有邊。我們用一個名為 edgeTo 的陣列來保存這些邊:
this.edgeTo = []; // 將這行加入 Graph 類別
// 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 each (var w in this.adj[v]){
if (!this.marked[w]){
this.edgeTo[w] = v;
this.marked[w] = true;
queue.push(w);
}
}
}
}
拓撲排序會對有向圖的所有頂點進行排序,使有向邊從前面的頂點指向後面的頂點。它與 BFS 類似,不同的是:拓撲排序不會立即輸出已存取的頂點,而是先存取當前頂點鄰接表中的所有相鄰頂點,直到這個列表窮盡時,才把當前頂點壓入堆疊。
拓撲排序被拆分為兩個函式:topSort() 負責設定排序進程、呼叫輔助函式 topSortHelper(),最後顯示排序好的頂點列表;而主要工作在遞歸函式 topSortHelper() 中完成——它會把當前頂點標記為已存取,遞歸存取鄰接表中的每個頂點並標記,最後把當前頂點壓入堆疊。
// topSort() 函式
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]]);
}
}
}
// topSortHelper() 函式
function topSortHelper(v, visited, stack){
visited[v] = true;
for each (var w in this.adj[v]){
if (!visited[w]){
this.topSortHelper(w, visited, stack);
}
}
stack.push(v);
}
以上就是 JavaScript 實作圖與圖演算法的完整解析,涵蓋圖的表示、DFS 與 BFS 兩種遍歷策略,以及最短路徑與拓撲排序等進階應用。