DIV CSS 佈局教程網

JavaScript 資料結構與演算法:圖與圖演算法
編輯:關於JavaScript     

圖的定義

圖(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 迴圈為陣列中每個元素建立一個子陣列來儲存所有相鄰頂點,並將元素初始化為空字串。

圖的遍歷

深度優先遍歷(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)屬於一種盲目搜尋法,目的是系統性地展開並檢查圖中的所有節點以尋找結果。也就是說,它並不考慮結果的可能位置,而是徹底搜尋整張圖,直到找到結果為止。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);
      }
    }
  }
}

最短路徑

執行廣度優先搜尋時,會自動查找從一個頂點到另一個相連頂點的最短路徑。

確定路徑

要查找最短路徑,需修改 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 兩種遍歷策略,以及最短路徑與拓撲排序等進階應用。

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