js 图线实现

在 JavaScript 中实现图（Graph）数据结构可以通过多种方式完成，以下是常见的实现方法：

邻接矩阵实现

邻接矩阵使用二维数组表示图的顶点和边。适用于稠密图或需要频繁查询边是否存在的情况。

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

  addEdge(v, w) {
    this.matrix[v][w] = 1;
    this.matrix[w][v] = 1; // 无向图需要双向设置
  }

  hasEdge(v, w) {
    return this.matrix[v][w] === 1;
  }
}

邻接表实现

邻接表使用数组或哈希表存储每个顶点的相邻顶点。适用于稀疏图或需要高效遍历邻接节点的情况。

class Graph {
  constructor() {
    this.adjList = new Map();
  }

  addVertex(v) {
    this.adjList.set(v, []);
  }

  addEdge(v, w) {
    this.adjList.get(v).push(w);
    this.adjList.get(w).push(v); // 无向图需要双向添加
  }
}

边列表实现

边列表直接存储所有边的信息。适用于需要频繁处理边的场景。

class Graph {
  constructor() {
    this.edges = [];
    this.vertices = new Set();
  }

  addEdge(v, w) {
    this.edges.push([v, w]);
    this.vertices.add(v);
    this.vertices.add(w);
  }
}

使用第三方库

对于复杂图操作，可以考虑使用专门库如：

• graphlib：提供多种图算法实现
• cytoscape.js：专注图可视化的库

// 使用graphlib示例
const { Graph } = require('graphlib');
const g = new Graph();
g.setNode('a');
g.setNode('b');
g.setEdge('a', 'b');

性能比较

1. 邻接矩阵：

   • 查询边是否存在：O(1)
   • 添加边：O(1)
   • 空间复杂度：O(V²)

2. 邻接表：

   • 查询边是否存在：O(V)
   • 添加边：O(1)
   • 空间复杂度：O(V+E)

3. 边列表：

   

   • 查询边是否存在：O(E)
   • 添加边：O(1)
   • 空间复杂度：O(E)

根据具体应用场景选择合适的数据结构，邻接表在大多数情况下是平衡的选择。