JavaScript 中图的实现

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

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

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 中图的实现的详细内容。更多信息请关注PHP中文网其他相关文章！