DIV CSS 佈局教程網

JavaScript 資料結構與演算法:圖與圖的遍歷演算法
編輯:JavaScript綜合知識     

圖(Graph)是資料結構中相當靈活的一種,廣泛應用於路徑規劃、網路連線與依賴分析等場景。本文將以 JavaScript 為工具,從圖的基本概念出發,逐步實作圖類,並深入探討深度優先與廣度優先遍歷、最短路徑與拓撲排序等經典圖演算法。

圖的定義

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

有向圖與無向圖

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

無向邊:若頂點 Vi 到 Vj 之間的邊沒有方向,則稱這條邊為無向邊(Edge),以無序偶 (Vi, Vj) 表示。

簡單圖:若圖中不存在頂點到其自身的邊,且同一條邊不重複出現,則稱這樣的圖為簡單圖。

實作图類

表示頂點

建立圖類的第一步,是建立一個 Vertex 類來保存頂點。它的作用如同鏈結串列或二元搜尋樹中的 Node 類。此處我們用 label 標識頂點:

function Vertex(label){
  this.label = label;
}

我們把所有頂點保存在陣列中,並透過它們在陣列中的位置來引用。

表示邊

圖的實際資訊都保存在「邊」上,因為邊描述了圖的結構。與二元樹每個父節點最多兩個子節點不同,圖的結構靈活得多——一個頂點可以有一條邊,也可以有多條邊與之相連。我們將表示邊的方法稱為鄰接表(adjacency list),它以陣列形式儲存每個頂點的相鄰頂點列表。

建立 Graph 類

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)

深度優先遍歷(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)屬於一種盲目搜尋法,目的是系統性地展開並檢查圖中的所有節點以尋找結果。它不考慮結果可能的位置,而是徹底地搜尋整張圖,直到找到為止。它從第一個頂點開始,嘗試訪問盡可能靠近它的頂點。

其工作原理為:

1. 首先查找與當前頂點相鄰的未訪問頂點,將其加入已訪問列表與佇列;
2. 接著從圖中取出下一個頂點 v,加入已訪問列表;
3. 最後把所有與 v 相鄰的未訪問頂點加入佇列。

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);
      }
    }
  }
}

最短路徑

在執行廣度優先搜尋時,會自動找出從一個頂點到另一個相連頂點的最短路徑。要記錄這條路徑,我們需要一個 edgeTo 陣列來保存從一個頂點到下一個頂點的所有邊:

this.edgeTo = []; // 將這行加入 Graph 類中

配合上述 bfs 函式中的 this.edgeTo[w] = v;,便能追蹤每個頂點是從哪個頂點被抵達的,進而還原最短路徑。

拓撲排序演算法

拓撲排序會對有向圖的所有頂點進行排序,使得有向邊都從前面的頂點指向後面的頂點。它與 BFS 類似,不同的是:拓撲排序不會立即輸出已訪問的頂點,而是先訪問當前頂點鄰接表中的所有相鄰頂點,直到這個列表窮盡時,才把當前頂點壓入堆疊。

拓撲排序被拆分為兩個函式:主函式 topSort() 負責設定排序進程並呼叫輔助函式 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() 中完成:它會把當前頂點標記為已訪問,接著遞歸訪問鄰接表中的每個頂點,最後將當前頂點壓入堆疊。

// 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 中建立圖結構,並靈活運用遍歷與排序演算法解決各類圖相關問題。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved