关于前端:图邻接表

实现图 - 邻接表

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'), '----')