js实现图

JavaScript 实现图的常见方法

在 JavaScript 中实现图数据结构，通常采用邻接表或邻接矩阵的方式。以下是两种常见的实现方法：

邻接表实现

邻接表使用对象或数组存储图的顶点和边，适合稀疏图（边数远小于顶点数的平方）。

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

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

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1); // 无向图需双向添加
  }

  removeEdge(v1, v2) {
    this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2);
    this.adjacencyList[v2] = this.adjacencyList[v2].filter(v => v !== v1);
  }

  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.numVertices = numVertices;
    this.matrix = Array(numVertices)
      .fill()
      .map(() => Array(numVertices).fill(0));
  }

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

  removeEdge(v1, v2) {
    this.matrix[v1][v2] = 0;
    this.matrix[v2][v1] = 0;
  }
}

图的遍历算法

深度优先搜索 (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 = {};
  visited[start] = true;

  while (queue.length) {
    const currentVertex = queue.shift();
    result.push(currentVertex);

    this.adjacencyList[currentVertex].forEach(neighbor => {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    });
  }

  return result;
}

加权图的实现

对于带权重的图，可以扩展邻接表的存储方式：

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

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

  addEdge(v1, v2, weight) {
    this.adjacencyList[v1].push({ node: v2, weight });
    this.adjacencyList[v2].push({ node: v1, weight });
  }
}

最短路径算法

Dijkstra 算法实现

dijkstra(start, finish) {
  const nodes = new PriorityQueue();
  const distances = {};
  const previous = {};
  let path = [];
  let smallest;

  // 初始化距离和前驱节点
  for (let vertex in this.adjacencyList) {
    if (vertex === start) {
      distances[vertex] = 0;
      nodes.enqueue(vertex, 0);
    } else {
      distances[vertex] = Infinity;
      nodes.enqueue(vertex, Infinity);
    }
    previous[vertex] = null;
  }

  while (nodes.values.length) {
    smallest = nodes.dequeue().val;
    if (smallest === finish) {
      // 构建路径
      while (previous[smallest]) {
        path.push(smallest);
        smallest = previous[smallest];
      }
      break;
    }

    if (smallest || distances[smallest] !== Infinity) {
      for (let neighbor in this.adjacencyList[smallest]) {
        let nextNode = this.adjacencyList[smallest][neighbor];
        let candidate = distances[smallest] + nextNode.weight;
        let nextNeighbor = nextNode.node;

        if (candidate < distances[nextNeighbor]) {
          distances[nextNeighbor] = candidate;
          previous[nextNeighbor] = smallest;
          nodes.enqueue(nextNeighbor, candidate);
        }
      }
    }
  }

  return path.concat(smallest).reverse();
}

以上实现涵盖了图的基本操作、遍历算法和最短路径算法，可以根据具体需求选择适合的图表示方法和算法。