JavaScript 实现图

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

有两种主要类型的图： 有向图 （也称为有向图）和 无向图 。在有向图中，边具有方向，并且只能沿一个方向遍历，从起始顶点到终止顶点。在无向图中，边没有方向，可以在两个方向上遍历。

在JavaScript中实现图

图可以使用邻接矩阵或邻接表来实现。在这里，我们将使用 邻接表 来在JavaScript中实现图。

创建图类

在这里，我们创建图类的蓝图。

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

添加顶点

此函数通过在adjacencyList对象中创建一个新的键，并用一个空数组作为其值，来向图中添加一个新的顶点（或节点）。新的顶点将作为键，空数组将用于存储其邻居。

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

添加边

此函数在两个顶点之间添加一条新边。它接受两个参数，顶点1和顶点2，并将顶点2添加到顶点1的邻居数组中，反之亦然。这样就创建了两个顶点之间的连接。

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(", ")}`);
   }
}

示例

在下面的示例中，我们定义了一个图并向图中添加了顶点和边。最后打印出该图。

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

移除顶点

此函数从图中移除一个顶点。它接受一个顶点参数，先移除所有与该顶点相连的边，然后从邻接表对象中删除该顶点对应的键。

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()函数实现。该函数实现了广度优先搜索算法，并接受一个起始顶点作为参数。它使用队列来跟踪要访问的顶点，使用结果数组存储已访问的顶点，使用一个visited对象来跟踪已经访问过的顶点。函数开始时将起始顶点添加到队列中并标记为已访问。然后，在队列非空的情况下，它从队列中取出第一个顶点，将其添加到结果数组并标记为已访问。然后，它将所有未访问的邻居顶点添加到队列中。这个过程会一直进行，直到所有顶点都被访问过，并将结果数组作为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;
   }
}

深度优先搜索

depthFirstSearch方法通过使用递归内部函数dfs来实现DFS算法。该函数使用一个对象visited来跟踪已访问的顶点，并将每个访问过的顶点添加到结果数组中。函数首先将当前顶点标记为已访问，并将其添加到结果数组中。然后，它遍历当前顶点的所有邻居，并对每个未访问的邻居递归调用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类实现了向图中添加顶点和边的方法，并且可以打印图和执行深度优先搜索和广度优先搜索遍历。