圖是一種非線性數據結構，表示一組頂點（也稱為節點）以及它們之間的關系（或邊）。頂點表示實體或對象，而邊表示頂點之間的關系或連接。圖可用于對許多不同類型的關系進行建模，例如社交網絡、交通系統或信息流。
圖有兩種主要類型：有向圖（也稱為有向圖）和無向圖。在有向圖中，邊有一個方向，并且只能在一個方向上遍歷，即從起始頂點到結束頂點。在無向圖中，邊沒有方向，可以在兩個方向上遍歷。
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 中圖的實現的詳細內容，更多請關注www.92cms.cn其它相關文章！
