在 JavaScript 中实现 Graph

图是一种非线性数据结构，表示一组顶点(也称为节点)及其之间的关系(或边)。顶点表示实体或对象，而边表示顶点之间的关系或连接。图可用于模拟许多不同类型的关系，例如社交网络、交通系统或信息流。

图主要有两种类型:有向图(也称为有向图)和无向图。在有向图中，边有方向，并且只能沿一个方向遍历，即从起始顶点到终止顶点。在无向图中，边没有方向，可以双向遍历。

在 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 参数，即起始顶点。它使用队列来跟踪要访问的顶点，使用结果数组来存储已访问的顶点，并使用 accessed 对象来跟踪已访问的顶点。该函数首先将起始顶点添加到队列并将其标记为已访问。然后，当队列不为空时，它从队列中取出第一个顶点，将其添加到结果数组中，并将其标记为已访问。然后，它将所有未访问的邻居添加到队列中。此过程持续到所有顶点都被访问过，并将结果数组作为 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. 深度优先搜索

depthFirstSearch 方法通过使用递归内部函数 dfs 来实现 DFS 算法，该函数以顶点为参数。该函数使用 accessed 对象跟踪已访问的顶点，并将每个已访问的顶点添加到结果数组中。该函数首先将当前顶点标记为已访问，并将其添加到结果数组中。然后，它遍历当前顶点的所有邻居，并为每个未访问的邻居递归调用 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 查找三角形的面积?
• 如何使用原生 JavaScript 查找 div 的宽度?
• 如何查找所有元素是否包含相同的类?
• 如何使用 JavaScript 找到图像的平均颜色?
• 如何在 JavaScript 中查找 HTML 元素的位置?
• 如何在 JavaScript 中过滤嵌套对象?
• 如何在 JavaScript 中根据字段值过滤对象?
• 如何使用 object() 构造函数创建 JavaScript 对象?
• 如何使用 JavaScript 将消息打印到错误控制台?
• 如何打印 JavaScript 对象的内容?