圖是一種非線性數(shù)據(jù)結(jié)構(gòu)，表示一組頂點（也稱為節(jié)點）以及它們之間的關(guān)系（或邊）。頂點表示實體或?qū)ο螅?b>邊表示頂點之間的關(guān)系或連接。圖可用于對許多不同類型的關(guān)系進行建模，例如社交網(wǎng)絡(luò)、交通系統(tǒng)或信息流。
圖有兩種主要類型：有向圖（也稱為有向圖）和無向圖。在有向圖中，邊有一個方向，并且只能在一個方向上遍歷，即從起始頂點到結(jié)束頂點。在無向圖中，邊沒有方向，可以在兩個方向上遍歷。
JavaScript 中圖的實現(xiàn)
圖可以使用鄰接矩陣或鄰接列表來實現(xiàn)。在這里，我們將使用鄰接列表在 JavaScript 中實現(xiàn)圖形。
創(chuàng)建圖表類
這里我們創(chuàng)建了圖形類的藍圖。
class Graph {
constructor() {
this.adjacencyList = {};
}
}
登錄后復(fù)制
添加頂點
該函數(shù)通過在 adjacencyList 對象中創(chuàng)建一個新鍵并將空數(shù)組作為其值來向圖中添加一個新頂點（或節(jié)點）。新頂點將作為鍵，空數(shù)組將用于存儲其鄰居。
addVertex(vertex) {
if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}
登錄后復(fù)制
添加邊緣
此函數(shù)在兩個頂點之間添加一條新邊。它接受兩個參數(shù)：vertex1 和 vertex2，并將 vertex2 添加到 vertex1 的鄰居數(shù)組中，反之亦然。這會在兩個頂點之間創(chuàng)建連接。
addEdge(vertex1, vertex2) {
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
}
登錄后復(fù)制
打印圖表
此函數(shù)將圖表記錄到控制臺。它迭代 adjacencyList 對象中的每個頂點并記錄該頂點及其鄰居。
print() {
for (const [vertex, edges] of Object.entries(this.adjacencyList)) {
console.log(`${vertex} -> ${edges.join(", ")}`);
}
}
登錄后復(fù)制
示例
在下面的示例中，我們定義一個圖并向該圖添加頂點和邊。最后打印圖表。
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ù)刪除兩個頂點之間的邊。它接受兩個參數(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ù)制
刪除頂點
該函數(shù)從圖中刪除一個頂點。它接受一個頂點參數(shù)，并首先刪除連接到該頂點的所有邊。然后，它從 adjacencyList 對象中刪除該鍵。
removeVertex(vertex) {
while (this.adjacencyList[vertex].length) {
const adjacentVertex = this.adjacencyList[vertex].pop();
this.removeEdge(vertex, adjacentVertex);
}
delete this.adjacencyList[vertex];
}
登錄后復(fù)制
示例
在下面的示例中，我們定義一個圖并添加頂點和邊，然后打印該圖。我們從圖中刪除一條邊 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ù)制
圖的遍歷方法
圖遍歷是指訪問圖的所有頂點（或節(jié)點）并處理與其關(guān)聯(lián)的信息的過程。圖遍歷是圖算法中的重要操作，用于查找兩個節(jié)點之間的最短路徑、檢測環(huán)路、查找連通分量等任務(wù)。
圖遍歷主要有兩種方法：廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（DFS）
A.廣度優(yōu)先搜索（BFS）
它是使用breadthFirstSearch()函數(shù)實現(xiàn)的。該函數(shù)實現(xiàn)廣度優(yōu)先搜索算法并采用 start 參數(shù)，即起始頂點。它使用隊列來跟蹤要訪問的頂點，使用結(jié)果數(shù)組來存儲訪問過的頂點，并使用訪問對象來跟蹤已經(jīng)訪問過的頂點。該函數(shù)首先將起始頂點添加到隊列中并將其標(biāo)記為已訪問。然后，當(dāng)隊列不為空時，它從隊列中取出第一個頂點，將其添加到結(jié)果數(shù)組中，并將其標(biāo)記為已訪問。然后它將所有未訪問的鄰居添加到隊列中。這個過程一直持續(xù)到所有頂點都被訪問過，并且結(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)先搜索方法通過使用以頂點作為參數(shù)的遞歸內(nèi)部函數(shù) dfs 來實現(xiàn) DFS 算法。該函數(shù)使用訪問的對象來跟蹤訪問的頂點，并將每個訪問的頂點添加到結(jié)果數(shù)組中。該函數(shù)首先將當(dāng)前頂點標(biāo)記為已訪問并將其添加到結(jié)果數(shù)組中。然后，它迭代當(dāng)前頂點的所有鄰居，并為每個未訪問的鄰居遞歸調(diào)用 dfs 函數(shù)。該過程一直持續(xù)到所有頂點都被訪問過并且結(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 中實現(xiàn)圖可以使用多種技術(shù)來完成，包括使用鄰接列表或鄰接矩陣。本答案中演示的 Graph 類使用鄰接列表表示形式，其中每個頂點都作為鍵存儲在對象中，其相應(yīng)的邊作為該鍵的值存儲在數(shù)組中。
Graph 類實現(xiàn)了向圖形添加頂點和邊、打印圖形以及執(zhí)行深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷的方法。
以上就是JavaScript 中圖的實現(xiàn)的詳細(xì)內(nèi)容，更多請關(guān)注www.92cms.cn其它相關(guān)文章！
