图的基本操作

基于邻接矩阵的增删如何实现？

• 添加边: adjMat[i][j] = 1, 无向图再补 adjMat[j][i] = 1;
• 删除边: 对应位置置 0;
• 添加顶点: 追加一行全 0 与一列全 0, 同时维护 "顶点 → 下标" 与 "下标 → 顶点" 两张映射表;
• 删除顶点: 删除该顶点所在的行与列, 同时更新映射表;

addVertex(value) {
  const size = this._size;
  this._vertices[value] = size;
  this._index[size] = value;
  this._adjMat.push(new Array(size).fill(0));
  for (const row of this._adjMat) row.push(0);
  this._size += 1;
}

removeVertex(value) {
  const i = this._vertices[value];
  delete this._vertices[value];
  delete this._index[i];
  this._adjMat.splice(i, 1);
  for (const row of this._adjMat) row.splice(i, 1);
  this._size -= 1;
}

• 易错: 删除下标 i 之后, 所有大于 i 的下标都会前移, 映射表必须同步重建或整体平移;

基于邻接表的增删如何实现？

• 添加边: 在起点的邻接容器里加入终点, 无向图再反向加一次;
• 删除边: 从起点的邻接容器里移除终点, 无向图再反向移除一次;
• 添加顶点: 新增一个空的邻接容器;
• 删除顶点: 删除该顶点的容器, 再遍历其余容器移除指向它的记录;

class GraphAdjList {
  constructor(vertices, edges, isDirected = false) {
    this._adj = new Map(vertices.map((v) => [v, new Set()]));
    this._isDirected = isDirected;
    for (const [a, b] of edges) this.addEdge(a, b);
  }

  addVertex(v) {
    this._adj.set(v, new Set());
  }

  removeVertex(v) {
    this._adj.delete(v);
    for (const neighbors of this._adj.values()) neighbors.delete(v);
  }

  addEdge(a, b) {
    this._adj.get(a).add(b);
    if (!this._isDirected) this._adj.get(b).add(a);
  }

  removeEdge(a, b) {
    this._adj.get(a).delete(b);
    if (!this._isDirected) this._adj.get(b).delete(a);
  }
}

• 容器选择: 用 Set 或哈希表可让上述操作都保持 O(1), 复杂度对照见 图的两种表示;