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');性能比较
-
邻接矩阵：
- 查询边是否存在：O(1)
- 添加边：O(1)
- 空间复杂度：O(V²)
-
邻接表：
- 查询边是否存在：O(V)
- 添加边：O(1)
- 空间复杂度：O(V+E)
-
边列表：
- 查询边是否存在：O(E)
- 添加边：O(1)
- 空间复杂度：O(E)
根据具体应用场景选择合适的数据结构，邻接表在大多数情况下是平衡的选择。
