实现图-邻接表
class Vertex {
constructor(V) {
this.data = https://www.it610.com/article/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 =https://www.it610.com/article/== 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'), '----')推荐阅读
- chrome|2022软件测试技巧 Chrome 谷歌浏览器 开发者工具(F12) 快速调试xpath代码
- JS|Chrome浏览器使用Overrides调试线上代码的技巧
- 前端核心知识点整理|如何使用谷歌浏览器 Chrome 更好地调试
- vue|【Vue】仿小米商城系统（一）
- Java|基于Vue的仿小米商城
- web前端作业|【HTML】HTML网页设计---海贼王动漫网页设计
- 认识Chrome扩展插件
- 微信小程序|【你踩的坑这里都有】微信小程序分包指南
- 前端|微信小程序 - 进阶（自定义组件、promis化、mobx、分包、自定义tabBar）