实现图-邻接表
class Vertex { constructor(V) { this.data = V; // 顶点 this.adj = []; // 邻接表数组实现 }}
// 模仿实现一个无向图的邻接表实现class UndirectedListGraph { constructor(size){ this.vertexesList = new Array(size); this.edges = 0; this.vertexes = 0; } edgeSize() { return this.edges; } vertexesSize() { return this.vertexes; } // 增加顶点 addVertex(vertex) { this.vertexesList[this.vertexes] = new Vertex(vertex); this.vertexes++; } // 新增一条边 addEdge(from, to, weight = 1) { const i = this.getPosition(from); const j = this.getPosition(to); this.vertexesList[i].adj.push(j); this.vertexesList[j].adj.push(i); this.edges++; } getPosition(v) { for(let i = 0; i < this.vertexes; i++) { if(this.vertexesList[i].data === v) return i; } return -1; } // 删除一条边 removeEdge(from, to) { const i = this.getPosition(from); const j = this.getPosition(to); this.vertexesList[i].adj.splice(j, 1); this.vertexesList[j].adj.splice(i, 1); this.edges--; } // 删除一个顶点 removeVertex(v) { /** * 删除一个顶点 * 1. 查问顶点V的序号index * 2. 更新边的个数 * 3. 删除所有邻接点对应的index * 4. 在数组中删除以后顶点 * 5. 更新顶点的个数 * 6. 更新所有邻接表的序号值大于1的值，将所有大于index的值全副减1 */ let index = this.getPosition(v); this.edges = this.edges - this.degree(v); this.vertexesList[index].adj.map((it, i) =>{ const removeIndex = this.vertexesList[it].adj.findIndex((v) => v === index); this.vertexesList[it].adj.splice(removeIndex, 1); }) // // 删除以后的顶点 for(let i = index; i < this.vertexes - 1; i++){ this.vertexesList[i] = this.vertexesList[i + 1]; } this.vertexes--; for(let i = 0; i < this.vertexes; i++) { this.vertexesList[i].adj = this.vertexesList[i].adj.map(it => it > 1 ? it - 1 : it ) } } // 某个顶点的度 degree(v) { return this.vertexesList[this.getPosition(v)].adj.length; } // 显示图 displayGraph() { console.log('这是一个无向图，邻接表存储的图'); console.log('顶点信息', this.vertexesList); for(let i = 0; i < this.vertexes; i++) { console.log(this.vertexesList[i].data); console.log(`邻接表： ${this.vertexesList[i].adj}`) } }}const graph = new UndirectedListGraph(10);graph.addVertex('A');graph.addVertex('B');graph.addVertex('C');graph.addVertex('D');graph.addVertex('E');graph.addVertex('F');console.log(graph, 'graph')graph.addEdge('A', 'B');graph.addEdge('A', 'D');graph.addEdge('B', 'C');graph.addEdge('B', 'E');graph.addEdge('C', 'D');graph.addEdge('C', 'F');graph.addEdge('D', 'F');graph.addEdge('E', 'F'); graph.displayGraph()graph.removeVertex('B');graph.displayGraph()console.log(graph.degree('C'), '----')