亚洲视频二区_亚洲欧洲日本天天堂在线观看_日韩一区二区在线观看_中文字幕不卡一区

圖是一種非線性數(shù)據(jù)結(jié)構(gòu)，表示一組頂點(diǎn)（也稱為節(jié)點(diǎn)）以及它們之間的關(guān)系（或邊）。頂點(diǎn)表示實(shí)體或?qū)ο螅?b>邊表示頂點(diǎn)之間的關(guān)系或連接。圖可用于對許多不同類型的關(guān)系進(jìn)行建模，例如社交網(wǎng)絡(luò)、交通系統(tǒng)或信息流。

圖有兩種主要類型：有向圖（也稱為有向圖）和無向圖。在有向圖中，邊有一個(gè)方向，并且只能在一個(gè)方向上遍歷，即從起始頂點(diǎn)到結(jié)束頂點(diǎn)。在無向圖中，邊沒有方向，可以在兩個(gè)方向上遍歷。

JavaScript 中圖的實(shí)現(xiàn)

圖可以使用鄰接矩陣或鄰接列表來實(shí)現(xiàn)。在這里，我們將使用鄰接列表在 JavaScript 中實(shí)現(xiàn)圖形。

創(chuàng)建圖表類

這里我們創(chuàng)建了圖形類的藍(lán)圖。

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

登錄后復(fù)制

添加頂點(diǎn)

該函數(shù)通過在 adjacencyList 對象中創(chuàng)建一個(gè)新鍵并將空數(shù)組作為其值來向圖中添加一個(gè)新頂點(diǎn)（或節(jié)點(diǎn)）。新頂點(diǎn)將作為鍵，空數(shù)組將用于存儲其鄰居。

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

登錄后復(fù)制

添加邊緣

此函數(shù)在兩個(gè)頂點(diǎn)之間添加一條新邊。它接受兩個(gè)參數(shù)：vertex1 和 vertex2，并將 vertex2 添加到 vertex1 的鄰居數(shù)組中，反之亦然。這會在兩個(gè)頂點(diǎn)之間創(chuàng)建連接。

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

登錄后復(fù)制

打印圖表

此函數(shù)將圖表記錄到控制臺。它迭代 adjacencyList 對象中的每個(gè)頂點(diǎn)并記錄該頂點(diǎn)及其鄰居。

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

登錄后復(fù)制

示例

在下面的示例中，我們定義一個(gè)圖并向該圖添加頂點(diǎn)和邊。最后打印圖表。

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

登錄后復(fù)制

輸出

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

登錄后復(fù)制

刪除邊

此函數(shù)刪除兩個(gè)頂點(diǎn)之間的邊。它接受兩個(gè)參數(shù)：vertex1 和 vertex2，并從 vertex1 的鄰居數(shù)組中過濾掉 vertex2，反之亦然。

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

登錄后復(fù)制

刪除頂點(diǎn)

該函數(shù)從圖中刪除一個(gè)頂點(diǎn)。它接受一個(gè)頂點(diǎn)參數(shù)，并首先刪除連接到該頂點(diǎn)的所有邊。然后，它從 adjacencyList 對象中刪除該鍵。

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

登錄后復(fù)制

示例

在下面的示例中，我們定義一個(gè)圖并添加頂點(diǎn)和邊，然后打印該圖。我們從圖中刪除一條邊 AC，最后打印結(jié)果圖。

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

登錄后復(fù)制

輸出

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

登錄后復(fù)制

圖的遍歷方法

圖遍歷是指訪問圖的所有頂點(diǎn)（或節(jié)點(diǎn)）并處理與其關(guān)聯(lián)的信息的過程。圖遍歷是圖算法中的重要操作，用于查找兩個(gè)節(jié)點(diǎn)之間的最短路徑、檢測環(huán)路、查找連通分量等任務(wù)。

圖遍歷主要有兩種方法：廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（DFS）

A.廣度優(yōu)先搜索（BFS）

它是使用breadthFirstSearch()函數(shù)實(shí)現(xiàn)的。該函數(shù)實(shí)現(xiàn)廣度優(yōu)先搜索算法并采用 start 參數(shù)，即起始頂點(diǎn)。它使用隊(duì)列來跟蹤要訪問的頂點(diǎn)，使用結(jié)果數(shù)組來存儲訪問過的頂點(diǎn)，并使用訪問對象來跟蹤已經(jīng)訪問過的頂點(diǎn)。該函數(shù)首先將起始頂點(diǎn)添加到隊(duì)列中并將其標(biāo)記為已訪問。然后，當(dāng)隊(duì)列不為空時(shí)，它從隊(duì)列中取出第一個(gè)頂點(diǎn)，將其添加到結(jié)果數(shù)組中，并將其標(biāo)記為已訪問。然后它將所有未訪問的鄰居添加到隊(duì)列中。這個(gè)過程一直持續(xù)到所有頂點(diǎn)都被訪問過，并且結(jié)果數(shù)組作為 BFS 的結(jié)果返回。

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

登錄后復(fù)制

B。深度優(yōu)先搜索

深度優(yōu)先搜索方法通過使用以頂點(diǎn)作為參數(shù)的遞歸內(nèi)部函數(shù) dfs 來實(shí)現(xiàn) DFS 算法。該函數(shù)使用訪問的對象來跟蹤訪問的頂點(diǎn)，并將每個(gè)訪問的頂點(diǎn)添加到結(jié)果數(shù)組中。該函數(shù)首先將當(dāng)前頂點(diǎn)標(biāo)記為已訪問并將其添加到結(jié)果數(shù)組中。然后，它迭代當(dāng)前頂點(diǎn)的所有鄰居，并為每個(gè)未訪問的鄰居遞歸調(diào)用 dfs 函數(shù)。該過程一直持續(xù)到所有頂點(diǎn)都被訪問過并且結(jié)果數(shù)組作為 DFS 的結(jié)果返回。

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

登錄后復(fù)制

示例

在下面的示例中，我們演示了廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（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'));

登錄后復(fù)制

輸出

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

登錄后復(fù)制

結(jié)論

圖是一種有用的數(shù)據(jù)結(jié)構(gòu)，可用于表示對象之間的關(guān)系和連接。在 JavaScript 中實(shí)現(xiàn)圖可以使用多種技術(shù)來完成，包括使用鄰接列表或鄰接矩陣。本答案中演示的 Graph 類使用鄰接列表表示形式，其中每個(gè)頂點(diǎn)都作為鍵存儲在對象中，其相應(yīng)的邊作為該鍵的值存儲在數(shù)組中。

Graph 類實(shí)現(xiàn)了向圖形添加頂點(diǎn)和邊、打印圖形以及執(zhí)行深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷的方法。

以上就是JavaScript 中圖的實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多請關(guān)注www.92cms.cn其它相關(guān)文章！