DIV CSS 佈局教程網

JavaScript 資料結構與演算法:圖與圖演算法
編輯:JavaScript基礎知識     

圖是資料結構中非常強大的抽象模型,適合用來表示網路、路線、社交關係、依賴關係與狀態轉移等問題。與樹狀結構相比,圖的連接方式更自由,一個節點可以有多個相鄰節點,因此演算法設計也更多樣。

圖的定義

圖通常由頂點與邊組成,可表示為 G(V, E),其中 V 是頂點集合,E 是邊集合。

有向圖與無向圖

有向圖

若邊具有方向,則稱為有向邊,也稱為弧。通常用 <Vi, Vj> 表示,Vi 是弧尾,Vj 是弧頭。

無向圖

若邊沒有方向,則稱為無向邊,通常用 (Vi, Vj) 表示。

簡單圖

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

用 JavaScript 表示圖

頂點

可以建立 Vertex 類別來表示頂點:

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

邊

圖的邊可以透過鄰接表表示。每個頂點對應一個陣列,陣列中存放與它相鄰的頂點。

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,會沿著一條路徑持續往下探索,直到沒有未訪問節點,再回溯。

實作時通常需要一個陣列來記錄節點是否已訪問:

this.marked = [];

for (var i = 0; i < this.vertices; ++i) {
  this.marked[i] = false;
}

DFS 函式

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,會先訪問離起點最近的節點,再逐層向外擴展。它常用於最短路徑、層級遍歷與迷宮求解等問題。

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 回溯,就能得到路徑。

拓撲排序

拓撲排序常用於有向無環圖,目的是將所有頂點排成一列,使得所有有向邊都從前面的頂點指向後面的頂點。它常用於任務排程、套件依賴與課程先修順序等場景。

拓撲排序可以透過深度優先搜尋變化而來。核心概念是:拜訪節點時先遞迴處理相鄰節點,等所有相鄰節點都處理完,再把目前節點推入堆疊。

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 (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,到最短路徑與拓撲排序,這些概念不僅能幫助我們解決演算法題目,也能應用於真實系統中的依賴分析、網路路由與排程問題。

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