Реализация алгоритма Прима в JavaScript с помощью списка смежности


Это моя реализация алгоритма Прима для поиска минимального остовного дерева.Если вы считаете, что мой код правильный, вы можете предложить что-то улучшить этот код.

class Graph {
    constructor(noOfVertices) {
        this.noOfVertices = noOfVertices;
        this.AdjList = new Map();
    }

    addVertex(v) {
        this.AdjList.set(v, []);
    }

    addEdgeUndirected(v, w, weight) {
        this.AdjList.get(v).push({
            neighbour: w,
            weight: weight
        });
        this.AdjList.get(w).push({
            neighbour: v,
            weight: weight
        });
    }


    primMST(V) {
        let reachedSet = [0]; //visited vertices
        let unreachedSet = []; //array containing all vertices set to false
        let mstSet = []; //contains final minimum spanning tree vertices

        for (let i = 0; i < this.noOfVertices; i++) {
            unreachedSet[i] = false;
        }

        unreachedSet[0] = true; //because we already added 0 to reachedSet.

        for (let i = 0; i < this.noOfVertices - 1; i++) {
            let e = this.minKey(reachedSet, unreachedSet);
            mstSet.push(e);
            reachedSet.push(e);
            unreachedSet[e] = true;
        }
        console.log(reachedSet);
    }

    minKey(reachedSet, unreachedSet) {
        let min = Number.MAX_SAFE_INTEGER;
        let minNode;
        for (let i = 0; i < reachedSet.length; i++) {
            let values = this.AdjList.get(reachedSet[i]);
            values.forEach(x => {
                if (unreachedSet[x.neighbour] === false && x.weight < min) {
                    min = x.weight;
                    minNode = x.neighbour;
                }
            })
        }
        return minNode;
    }

}



(function main() {
    var g = new Graph(9);
    g.addVertex(0);
    g.addVertex(1);
    g.addVertex(2);
    g.addVertex(3);
    g.addVertex(4);
    g.addVertex(5);
    g.addVertex(6);
    g.addVertex(7);
    g.addVertex(8);

    g.addEdgeUndirected(0, 1, 4);
    g.addEdgeUndirected(1, 2, 8);
    g.addEdgeUndirected(2, 3, 7);
    g.addEdgeUndirected(3, 4, 9);
    g.addEdgeUndirected(4, 5, 10);
    g.addEdgeUndirected(3, 5, 14);
    g.addEdgeUndirected(2, 5, 4);
    g.addEdgeUndirected(2, 8, 2);
    g.addEdgeUndirected(8, 6, 6);
    g.addEdgeUndirected(7, 8, 7);
    g.addEdgeUndirected(6, 7, 1);
    g.addEdgeUndirected(0, 7, 8);
    g.addEdgeUndirected(1, 7, 11);
    g.addEdgeUndirected(6, 5, 2);

    g.primMST(g.noOfVertices);
})();


Комментарии