JS中數據結構之圖

圖由邊的集合及頂點的集合組成。邊是有方向的是有序圖（有向圖），否則就是無序圖（無向圖）。圖中的一系列頂點構成路徑，路徑中所有的頂點都由邊連接。路徑的長度用路徑中第一個頂點到最后一個頂點之間邊的數量表示。

用鄰接表來表示邊，即將與某一頂點的相鄰的邊表示為由該頂點的相鄰頂點列表構成的數組，并以該頂點作為索引。比如，如果頂點 2 與頂點 0、 1、3、4 相連，那么就將0、1、3、4存儲在數組中索引為 2 的位置。

Graph 類定義圖

function Graph(v) {
  this.vertices = v;  //頂點的數量
  this.edges = 0;
  this.adj = [];
  for (var i = 0; i < this.vertices; ++i) {
    this.adj[i] = [];  //保存與頂點 i 相鄰的頂點列表
  }
  this.addEdge = addEdge;
  this.showGraph = showGraph;
  this.dfs = dfs;
  this.bfs = bfs;
  this.marked = [];  //保存未訪問過的頂點
  for (var i = 0; i < this.vertices; ++i) {
    this.marked[i] = false;
  }
  this.pathTo = pathTo;
  this.hasPathTo = hashPathTo;
  this.edgeTo = [];
}

addEdge(A,B) 添加邊，先查找頂點 A 的鄰接表，將頂點 B 添加到列表中，然后再查找頂點 B 的鄰接表，將頂點 A 加入列表。最后，將邊數加 1。

function addEdge(v, w) {
　　this.ajd[v].push(w);
　　this.adj[w].push(v);
　　this.edges++;
}

showGraph() 方法顯示所有頂點及其相鄰頂點列表

function showGraph() {
  for (var i = 0; i < this.vertices; ++i) {
    var str = '';
    str += i + " -> ";
    for (var j = 0; j < this.vertices; ++j) {
      if (this.adj[i][j] != undefined) {
        str += this.adj[i][j] + ' ';
      }
    }
    console.log(str);
  }
}

搜索圖

確定從一個指定的頂點可以到達其他哪些頂點，有兩種搜索方法：深度優先搜索和廣度優先搜索。

深度優先搜索從起始頂點開始追溯，直到到達最后一個頂點，然后回溯，繼續追溯下一條路徑，直到到達最后的頂點，如此往復，直到沒有路徑為止。當訪問一個沒有訪問過的頂點時，將它標記為已訪問，再遞歸地去訪問在初始頂點的鄰接表中其他沒有訪問過的頂點。

function dfs(v) {
  this.marked[v] = true;
  if (this.adj[v] != undefined) {
    console.log("Visited vertex: " + v);
  }
  for(var w of this.adj[v]) {
    if (!this.marked[w]) {
      this.dfs(w);
    }
  }
}

//調用
g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.showGraph();
g.dfs(0);

廣度優先搜索從第一個頂點開始，嘗試訪問盡可能靠近它的頂點。本質上，這種搜索是逐層移動的，首先檢查最靠近第一個頂點的層，再逐漸向下移動到離起始頂點最遠的層。

function bfs(s) {
  var queue = [];
  this.marked[s] = true;
  queue.push(s); // 添加到隊尾
  while (queue.length > 0) {
    var v = queue.shift(); // 從隊首移除
    if (v != undefined) {
      console.log("Visisted vertex: " + v);
    }
    for(var w of this.adj[v]) {
      if (!this.marked[w]) {this.marked[w] = true;
        queue.push(w);
      }
    }
  }
}

posted @ 2019-01-22 23:16 wenxuehai 閱讀(1613) 評論(0) 收藏舉報

刷新頁面返回頂部

//右下角添加目錄

提升自己，才有選擇的能力和勇氣

JS中數據結構之圖

公告