JavaScript 中圖的實現

圖是一種非線性資料結構，表示一組頂點（也稱為節點）以及它們之間的關係（或邊）。頂點表示實體或對象，而邊表示頂點之間的關係或連結。圖可用於對許多不同類型的關係進行建模，例如社交網路、交通系統或資訊流。

圖有兩種主要類型：有向圖（也稱為有向圖）和無向圖。在有向圖中，邊有一個方向，並且只能在一個方向上遍歷，即從起始頂點到結束頂點。在無向圖中，邊沒有方向，可以在兩個方向遍歷。

JavaScript 中圖的實作

圖可以使用鄰接矩陣或鄰接列表來實現。在這裡，我們將使用鄰接列表在 JavaScript 中實作圖形。

建立圖表類別

這裡我們創建了圖形類別的藍圖。

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
}

新增頂點

該函數透過在 adjacencyList 物件中建立一個新鍵並將空數組作為其值來為圖中新增一個頂點（或節點）。新頂點將作為鍵，空數組將用於儲存其鄰居。

addVertex(vertex) {
   if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}

新增邊緣

此函數在兩個頂點之間新增一條新邊。它接受兩個參數：vertex1 和 vertex2，並將 vertex2 加到 vertex1 的鄰居陣列中，反之亦然。這會在兩個頂點之間建立連接。

addEdge(vertex1, vertex2) {
   this.adjacencyList[vertex1].push(vertex2);
   this.adjacencyList[vertex2].push(vertex1);
}

列印圖表

此函數將圖表記錄到控制台。它迭代 adjacencyList 物件中的每個頂點並記錄該頂點及其鄰居。

print() {
   for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
      console.log(`${vertex} -> ${edges.join(", ")}`);
   }
}

範例

在下面的範例中，我們定義一個圖表並向該圖添加頂點和邊。最後列印圖表。

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
   addVertex(vertex) {
      if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1].push(vertex2);
      this.adjacencyList[vertex2].push(vertex1);
   }
   print() {
      for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
         console.log(`${vertex} -> ${edges.join(", ")}`);
      }
   }
}
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
console.log("Graph:");
graph.print();

輸出

Graph:
A -> B, C
B -> A, D
C -> A, D
D -> B, C

刪除邊

此函數刪除兩個頂點之間的邊。它接受兩個參數：vertex1 和 vertex2，並從 vertex1 的鄰居陣列中過濾掉 vertex2，反之亦然。

removeEdge(vertex1, vertex2) {
   this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
      (v) => v !== vertex2
   );
   this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
      (v) => v !== vertex1
   );
}

刪除頂點

此函數從圖中刪除一個頂點。它接受一個頂點參數，並首先刪除連接到該頂點的所有邊。然後，它從 adjacencyList 物件中刪除該鍵。

removeVertex(vertex) {
   while (this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
   }
   delete this.adjacencyList[vertex];
}

範例

在下面的範例中，我們定義一個圖並新增頂點和邊，然後列印該圖。我們從圖中刪除一邊 AC，最後列印結果圖。

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
   addVertex(vertex) {
      if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1].push(vertex2);
      this.adjacencyList[vertex2].push(vertex1);
   }
   removeEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
         (v) => v !== vertex2
      );
      this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
         (v) => v !== vertex1
      );
   }
   removeVertex(vertex) {
      while (this.adjacencyList[vertex].length) {
         const adjacentVertex = this.adjacencyList[vertex].pop();
         this.removeEdge(vertex, adjacentVertex);
      }
      delete this.adjacencyList[vertex];
   }
   print() {
      for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
         console.log(`${vertex} -> ${edges.join(", ")}`);
      }
   }
}
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
console.log("Initial Graph:");
graph.print();
console.log("Graph after removal of edge AC:")
graph.removeEdge("A","C");
graph.print();

輸出

Initial Graph:
A -> B, C
B -> A, D
C -> A, D
D -> B, C
Graph after removal of edge AC:
A -> B
B -> A, D
C -> D
D -> B, C

圖的遍歷方法

圖遍歷是指訪問圖的所有頂點（或節點）並處理與其關聯的資訊的過程。圖遍歷是圖演算法中的重要操作，用於尋找兩個節點之間的最短路徑、偵測迴路、尋找連通分量等任務。

圖遍歷主要有兩種方法：廣度優先搜尋（BFS）和深度優先搜尋（DFS）

A.廣度優先搜尋（BFS）

它是使用breadthFirstSearch()函數實現的。此函數實作廣度優先搜尋演算法並採用 start 參數，即起始頂點。它使用佇列來追蹤要存取的頂點，使用結果陣列來儲存存取過的頂點，並使用存取物件來追蹤已經存取過的頂點。此函數首先將起始頂點新增至佇列並將其標記為已存取。然後，當佇列不為空時，它會從佇列中取出第一個頂點，將其新增至結果陣列中，並將其標記為已存取。然後它將所有未訪問的鄰居添加到隊列中。這個過程一直持續到所有頂點都被訪問過，並且結果數組作為 BFS 的結果返回。

breadthFirstSearch(start) {
   const queue = [start];
   const result = [];
   const visited = {};
   let currentVertex;
   visited[start] = true;
   while (queue.length) {
      currentVertex = queue.shift();
      result.push(currentVertex);
         this.adjacencyList[currentVertex].forEach((neighbor) => {
            if (!visited[neighbor]) {
               visited[neighbor] = true;
               queue.push(neighbor);
            }
         });
      }
      return result;
   }
}

B。深度優先搜尋

深度優先搜尋方法透過使用以頂點作為參數的遞歸內部函數 dfs 來實作 DFS 演算法。此函數使用存取的物件來追蹤存取的頂點，並將每個存取的頂點新增至結果陣列。該函數首先將當前頂點標記為已存取並將其新增至結果陣列。然後，它迭代當前頂點的所有鄰居，並為每個未訪問的鄰居遞歸呼叫 dfs 函數。這個過程一直持續到所有頂點都被存取過並且結果數組作為 DFS 的結果傳回。

depthFirstSearch(start) {
   const result = [];
   const visited = {};
   const adjacencyList = this.adjacencyList;
   (function dfs(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach(neighbor => {
         if (!visited[neighbor]) {
            return dfs(neighbor);
         }
      });
   })(start);
   return result;
}

範例

在下面的範例中，我們示範了廣度優先搜尋（BFS）和深度優先搜尋（DFS）。

class Graph {
   constructor() {
      this.adjacencyList = {};
   }
   addVertex(vertex) {
      if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
   }
   addEdge(vertex1, vertex2) {
      this.adjacencyList[vertex1].push(vertex2);
      this.adjacencyList[vertex2].push(vertex1);
   }
   print() {
      for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
         console.log(`${vertex} -> ${edges.join(", ")}`);
      }
   }
   breadthFirstSearch(start) {
      const queue = [start];
      const result = [];
      const visited = {};
      let currentVertex;
      visited[start] = true;
      while (queue.length) {
         currentVertex = queue.shift();
         result.push(currentVertex);
         this.adjacencyList[currentVertex].forEach((neighbor) => {
            if (!visited[neighbor]) {
               visited[neighbor] = true;
               queue.push(neighbor);
            }
         });
      }
      return result;
   }
   depthFirstSearch(start) {
      const result = [];
      const visited = {};
      const adjacencyList = this.adjacencyList;
      (function dfs(vertex) {
         if (!vertex) return null;
         visited[vertex] = true;
         result.push(vertex);
         adjacencyList[vertex].forEach(neighbor => {
            if (!visited[neighbor]) {
               return dfs(neighbor);
            }
         });
      })(start);
      return result;
   }
}
const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
console.log("Initial Graph:");
graph.print();
console.log("BFS: "+graph.breadthFirstSearch('A'));
console.log("DFS: "+graph.depthFirstSearch('A'));

輸出

Initial Graph:
A -> B, C
B -> A, D
C -> A, D
D -> B, C
BFS: A,B,C,D
DFS: A,B,D,C

結論

圖是一種有用的資料結構，可用來表示物件之間的關係和連結。在 JavaScript 中實作圖可以使用多種技術來完成，包括使用鄰接列表或鄰接矩陣。本答案中演示的 Graph 類別使用鄰接列表表示形式，其中每個頂點都作為鍵存儲在物件中，其對應的邊作為該鍵的值儲存在數組中。

Graph 類別實作了為圖形新增頂點和邊、列印圖形以及執行深度優先搜尋和廣度優先搜尋遍歷的方法。

以上是JavaScript 中圖的實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！