JS Graph (图-数据结构)

Code:

/**
 * 基于邻接表实现的无向图
 * @class
 */
class GraphAdjList {
    /**
     * @type {Map<any, any[]>}
     */
    adjList;

    /**
     * 构造函数
     * @constructor
     * @param {[any, any][]} edges 
     */
    constructor(edges) {
        this.adjList = new Map();
        /**
         * 初始化现有的顶点与边
         */
        for (const [e1, e2] of edges) {
            this.addVertex(e1);
            this.addVertex(e2);
            this.addEdge(e1, e2);
        }
    }

    /**
     * 获取顶点数量
     * @returns 
     */
    size() {
        return this.adjList.size;
    }

    /**
     * 添加顶点
     * @param vet 
     * @returns 
     */
    addVertex(vet) {
        //// 如果该顶点已经存在
        if (this.adjList.has(vet)) {
            return;
        }
        // 在邻接表中添加一个新链表
        this.adjList.set(vet, []);
    }

    /**
     * 删除顶点
     * @param vet 
     */
    removeVertex(vet) {
        if (!this.adjList.has(vet)) {
            throw new Error('Illegal Argument Exception');
        }
        // 删除该顶点所对应的链表
        this.adjList.delete(vet);
        // 删除其他顶点与该顶点形成的“边”
        const values = this.adjList.values();
        for (const arr of values) {
            const idx = arr.indexOf(vet);
            if (idx > -1) {
                arr.splice(idx, 1);
            }
        }
    }

    /**
     * 添加边
     * @param v1 
     * @param v2 
     */
    addEdge(v1, v2) {
        if (!this.adjList.has(v1) || !this.adjList.has(v2) || v1 === v2) {
            throw new Error('Illegal Argument Exception');
        }
        // 连接v1-v2，形成新的边
        this.adjList.get(v1).push(v2);
        this.adjList.get(v2).push(v1);
    }

    /**
     * 删除边
     * @param v1 
     * @param v2 
     */
    removeEdge(v1, v2) {
        if (!this.adjList.has(v1) || !this.adjList.has(v2) || v1 === v2) {
            throw new Error('Illegal Argument Exception');
        }
        const v1Idx = this.adjList.get(v2).indexOf(v1);
        const v2Idx = this.adjList.get(v1).indexOf(v2);
        this.adjList.get(v1).splice(v2Idx, 1);
        this.adjList.get(v2).splice(v1Idx, 1);
    }

    // 打印链表
    print() {
        console.log('邻接表 =');
        for (const [key, value] of this.adjList) {
            const valList = [];
            for (const piece of value) {
                valList.push(piece);
            }
            console.log(key + '：' + valList.toString());
        }
    }
}

/**
 * 基于邻接矩阵实现的无向图
 * @class
 */
class GraphAdjMat {
    /**
     * 顶点列表（元素代表顶点值，元素索引代表顶点索引）
     * @type {any[]}
     */
    vertices;
    /**
     * 邻接矩阵（行列索引代表顶点索引）
     * @type {any[][]}
     */
    adjMat;

    /**
     * 构造器
     * @constructor
     * @param {any[]} vertices 
     * @param {[number, number][]} edges 
     */
    constructor(vertices, edges) {
        this.vertices = [];
        this.adjMat = [];
        // 添加顶点
        for (const val of vertices) {
            this.addVertex(val);
        }
        // 添加边
        for (const [x, y] of edges) {
            this.addEdge(x, y);
        }
    }

    /**
     * 顶点数量
     * @returns 
     */
    size() {
        return this.vertices.length;
    }

    /**
     * 添加顶点
     * @param {any} val 
     */
    addVertex(val) {
        const n = this.size();
        this.vertices.push(val);
        // 添加行
        const newRow = [];
        for (let i = 0; i < n; i++) {
            newRow.push(0);
        }
        this.adjMat.push(newRow);
        // 添加列
        for (const row of this.adjMat) {
            row.push(0);
        }
    }

    /**
     * 删除顶点
     * @param {number} index 
     */
    removeVertex(index) {
        if (index >= this.size()) {
            throw new RangeError('Index Out Of Bounds Exception');
        }
        this.vertices.splice(index, 1);
        // 删除行
        this.adjMat.splice(index, 1);
        // 删除列
        for (const row of this.adjMat) {
            row.splice(index, 1);
        }
    }

    /**
     * 添加边
     * @param {number} i 
     * @param {number} j 
     */
    addEdge(i, j) {
        // 处理边界条件
        if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
            throw new RangeError('Index Out Of Bounds Exception');
        }
        this.adjMat[i][j] = 1;
        this.adjMat[j][i] = 1;
    }

    /**
     * 删除边
     * @param {number} i 
     * @param {number} j 
     */
    removeEdge(i, j) {
        if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
            throw new RangeError('Index Out Of Bounds Exception');
        }
        this.adjMat[i][j] = 0;
        this.adjMat[j][i] = 0;
    }
}

图的遍历操作

Code: 

function bfsGraph(graph, startVet) {
    const ans = [];
    const vis = new Set();
    vis.add(startVet);
    const q = [startVet];

    while (q.length > 0) {
        const vet = q.shift();
        ans.push(vet);
        const adjList = graph.adjList.get(vet) ?? []
        for (const adjVet of adjList) {
            if (vis.has(adjVet)) {
                continue;
            }
            q.push(adjVet);
            vis.add(adjVet);
        }
    }

    return ans;
}