js实现图

JavaScript 实现图的常用方法

在 JavaScript 中，图（Graph）可以通过多种方式实现，常见的包括邻接表（Adjacency List）和邻接矩阵（Adjacency Matrix）。以下是具体实现方法：

邻接表实现

邻接表是图的常见表示方法，适合稀疏图（边数远小于顶点数的平方）。使用对象或数组存储顶点及其相邻顶点。

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

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

  addEdge(vertex1, vertex2) {
    if (!this.adjacencyList[vertex1] || !this.adjacencyList[vertex2]) {
      return false;
    }
    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];
  }
}

邻接矩阵实现

邻接矩阵适合稠密图（边数接近顶点数的平方），使用二维数组表示顶点间的连接关系。

class Graph {
  constructor(numVertices) {
    this.matrix = Array(numVertices)
      .fill()
      .map(() => Array(numVertices).fill(0));
  }

  addEdge(i, j) {
    this.matrix[i][j] = 1;
    this.matrix[j][i] = 1; // 无向图需对称设置
  }

  removeEdge(i, j) {
    this.matrix[i][j] = 0;
    this.matrix[j][i] = 0;
  }

  hasEdge(i, j) {
    return this.matrix[i][j] === 1;
  }
}

图的遍历算法

深度优先搜索（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）

队列实现，适合查找最短路径或层级遍历。

breadthFirstSearch(start) {
  const queue = [start];
  const result = [];
  const visited = { [start]: true };

  while (queue.length) {
    const vertex = queue.shift();
    result.push(vertex);
    this.adjacencyList[vertex].forEach(neighbor => {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    });
  }
  return result;
}

加权图的实现

对于带权重的图（如 Dijkstra 算法场景），邻接表可扩展为存储对象而非单纯顶点。

addWeightedEdge(vertex1, vertex2, weight) {
  this.adjacencyList[vertex1].push({ node: vertex2, weight });
  this.adjacencyList[vertex2].push({ node: vertex1, weight }); // 无向图
}

实际应用示例

以下是通过图解决简单路径问题的示例：

const graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge("A", "B");
graph.addEdge("B", "C");
console.log(graph.depthFirstSearch("A")); // ["A", "B", "C"]

通过以上方法，可以灵活实现图的存储、修改和遍历操作。邻接表在大多数场景下更节省空间，而邻接矩阵适合快速查询边是否存在。