/** * 模仿实现一个无向图 */class UndirectedVertexGraph { constructor(size){ this.size = size; this.vertexesList = []; // 保留顶点 this.edgeMatex = new Array(10).fill(0).map(() => new Array(10).fill(0)); // 用来保留邻接矩阵 this.vertexes = 0; // 保留顶点数量 this.edges = 0; // 保留边的数量 } edgeSize() { return this.vertexes; } // 增加顶点 addVertex(vertex) { this.vertexesList.push(vertex); this.vertexes++; } // 新增一条边 addEdge(from, to, weight = 1) { const i = this.vertexesList.indexOf(from); const j = this.vertexesList.indexOf(to); this.edgeMatex[i][j] = weight; this.edgeMatex[j][i] = weight; this.edges++; } // 删除一条边 removeEdge() { const i = this.vertexesList.indexOf(from); const j = this.vertexesList.indexOf(to); this.edgeMatex[i][j] = 0; this.edgeMatex[j][i] = 0; this.edges--; } // 删除一个顶点 removeVertex(v) { const index = this.vertexesList.indexOf(v); for(let i = 0; i < this.vertexes; i++) { if(this.edgeMatex[index][i] !== 0) { // 示意index与i之间有一条边 this.edges--; } } this.vertexesList.splice(index, 1); // index前面的所有行前移一行 for(let i = index; i < this.vertexes - 1; i++) { for(let j = 0; j < this.vertexes; j++) { this.edgeMatex[i][j] = this.edgeMatex[i + 1][j]; } } // index前面的所有列迁徙一列 for(let i = 0; i < this.vertexes; i++) { for(let j = index; j < this.vertexes - 1; j++) { this.edgeMatex[i][j] = this.edgeMatex[i][j + 1]; } } this.vertexes--; } // 某个顶点的度 degree(v) { const index = this.vertexesList.indexOf(v); let count = 0; for(let i = 0; i < this.vertexes; i++) { if(this.edgeMatex[index][i] !== 0) { count++; } } return count; } // 显示图 displayGraph() { console.log('这是一个无向图,领接矩阵'); console.log('顶点信息', this.vertexesList); for(let i = 0; i < this.vertexes; i++) { let str = '' for(let j = 0; j < this.vertexes; j++){ str += this.edgeMatex[i][j] + ' '; } console.log(str); } }}const graph = new UndirectedVertexGraph(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('B'), '----')