图是一种非线性数据结构，表示一组顶点（也称为节点）以及它们之间的关系（或边）。顶点表示实体或对象，而边表示顶点之间的关系或连接。图可用于对许多不同类型的关系进行建模，例如社交网络、交通系统或信息流。
图有两种主要类型：有向图（也称为有向图）和无向图。在有向图中，边有一个方向，并且只能在一个方向上遍历，即从起始顶点到结束顶点。在无向图中，边没有方向，可以在两个方向上遍历。
JavaScript 中图的实现
图可以使用邻接矩阵或邻接列表来实现。在这里，我们将使用邻接列表在 JavaScript 中实现图形。
创建图表类
这里我们创建了图形类的蓝图。
立即学习“Java免费学习笔记（深入）”；
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 类实现了向图形添加顶点和边、打印图形以及执行深度优先搜索和广度优先搜索遍历的方法。
