用Javascript完成图类

在此代码中已注释掉的功能。您也可以切换到那些。我们还将Queue，Stack和PriorityQueue类移到了可以使用import语句或require调用导入的不同模块中。这是Graph类的完整实现- 

示例

const Queue = require("./Queue");
const Stack = require("./Stack");
const PriorityQueue = require("./PriorityQueue");

class Graph {
   constructor() {
      this.edges = {};
      this.nodes = [];
 }

   addNode(node) {
      this.nodes.push(node);
      this.edges[node] = [];
 }

   addEdge(node1, node2, weight = 1) {
      this.edges[node1].push({ node: node2, weight: weight});
      this.edges[node2].push({ node: node1, weight: weight});
 }

   addDirectedEdge(node1, node2, weight = 1) {
      this.edges[node1].push({ node: node2, weight: weight});
 }

   //addEdge(node1,node2){
      //this.edges [node1] .push(node2); 
      //this.edges [node2] .push(node1); 
   //}

   //addDirectedEdge(node1,node2){
      //this.edges [node1] .push(node2); 
   //}

   display() {
      let graph = "";
      this.nodes.forEach(node => {
         graph += node + "->" + this.edges[node].map(n => n.node).join(", ") + "\n";
    });
      console.log(graph);
 }

   BFS(node) {
      let q = new Queue(this.nodes.length);
      let explored = new Set();
      q.enqueue(node);
      explored.add(node);
      while (!q.isEmpty()) {
         let t = q.dequeue();
         console.log(t);
         this.edges[t].filter(n => !explored.has(n)).forEach(n => {
            explored.add(n);
            q.enqueue(n);
       });
    }
 }

   DFS(node) {
      //创建一个堆栈并在其中添加我们的初始节点
      let s = new Stack(this.nodes.length);
      let explored = new Set();
      s.push(node);

      //将第一个节点标记为已浏览
      explored.add(node);

      //我们将继续直到堆栈变空
      while (!s.isEmpty()) {
         let t = s.pop();

         //记录从堆栈中出来的每个元素
         console.log(t);

         //节点
         //直接连接。
         //2.我们过滤掉已经探索过的节点。
         //3.然后，我们将每个未探索的节点标记为已探索并推动它
         //到堆栈。
         this.edges[t].filter(n => !explored.has(n)).forEach(n => {
            explored.add(n);
            s.push(n);
       });
    }
 }

   topologicalSortHelper(node, explored, s) {
      explored.add(node);
      this.edges[node].forEach(n => {
         if (!explored.has(n)) {
            this.topologicalSortHelper(n, explored, s);
       }
    });
      s.push(node);
 }

   topologicalSort() {
      //创建一个堆栈并在其中添加我们的初始节点
      let s = new Stack(this.nodes.length);
      let explored = new Set();
      this.nodes.forEach(node => {
         if (!explored.has(node)) {
            this.topologicalSortHelper(node, explored, s);
       }
    });
      while (!s.isEmpty()) {
         console.log(s.pop());
    }
 }

   BFSShortestPath(n1, n2) {
      let q = new Queue(this.nodes.length);
      let explored = new Set();
      let distances = { n1: 0};

      q.enqueue(n1);
      explored.add(n1);

      while (!q.isEmpty()) {
         let t = q.dequeue();
         this.edges[t].filter(n => !explored.has(n)).forEach(n => {
            explored.add(n);
            distances[n] = distances[t] == undefined ? 1 : distances[t] + 1;
            q.enqueue(n);
       });
    }
      return distances[n2];
 }

   primsMST() {
      //初始化将包含MST的图形
      const MST = new Graph();
      if (this.nodes.length === 0) {
         return MST;
    }

      //选择第一个节点作为起始节点
      let s = this.nodes[0];

      //创建一个优先级队列并浏览集
      let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
      let explored = new Set();

      explored.add(s);
      MST.addNode(s);

      //将所有从此起始节点开始的边以权重作为优先级添加到PQ-
      this.edges[s].forEach(edge => {
         edgeQueue.enqueue([s, edge.node], edge.weight);
    });

      //选取最小的边缘并将其添加到新图形中
      let currentMinEdge = edgeQueue.dequeue();
      while (!edgeQueue.isEmpty()) {
         //继续去除边缘，直到我们得到带有未开发节点的边缘
         while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
            currentMinEdge = edgeQueue.dequeue();
       }
         let nextNode = currentMinEdge.data[1];

         //再次检查，因为队列可能会变空而没有退还未开发的元素
         if (!explored.has(nextNode)) {
            MST.addNode(nextNode);
            MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);
            //再次将所有边添加到PQ-
            this.edges[nextNode].forEach(edge => {
               edgeQueue.enqueue([nextNode, edge.node], edge.weight);
          });

            //将此节点标记为exploredexplored.add(nextNode); 
            s = nextNode;
       }
    }
      return MST;
 }

   kruskalsMST() {
      //初始化将包含MST的图形
      const MST = new Graph();
      this.nodes.forEach(node => MST.addNode(node));
      if (this.nodes.length === 0) {
         return MST;
    }

      //创建一个优先级队列
      let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);

      //将所有边添加到队列中：
      for (let node in this.edges) {
         this.edges[node].forEach(edge => {
            edgeQueue.enqueue([node, edge.node], edge.weight);
       });
    }

      let uf = new UnionFind(this.nodes);
      //循环直到我们探索所有节点或队列为空
      while (!edgeQueue.isEmpty()) {
         //使用解构获取边缘数据
         let nextEdge = edgeQueue.dequeue();
         let nodes = nextEdge.data;
         let weight = nextEdge.priority;
         if (!uf.connected(nodes[0], nodes[1])) {
            MST.addEdge(nodes[0], nodes[1], weight);
            uf.union(nodes[0], nodes[1]);
       }
    }
      return MST;
 }

   djikstraAlgorithm(startNode) {
      let distances = {};
      //存储对先前节点的引用
      let prev = {};
      let pq = new PriorityQueue(this.nodes.length * this.nodes.length);

      //以外的所有节点的距离设置为无限
      distances[startNode] = 0;
      pq.enqueue(startNode, 0);
      this.nodes.forEach(node => {
         if (node !== startNode) distances[node] = Infinity;
         prev[node] = null;
    });

      while (!pq.isEmpty()) {
         let minNode = pq.dequeue();
         let currNode = minNode.data;
         let weight = minNode.priority;

         this.edges[currNode].forEach(neighbor => {
            let alt = distances[currNode] + neighbor.weight;
            if (alt < distances[neighbor.node]) {
               distances[neighbor.node] = alt;
               prev[neighbor.node] = currNode;
               pq.enqueue(neighbor.node, distances[neighbor.node]);
          }
       });
    }
      return distances;
 }

   floydWarshallAlgorithm() {
      let dist = {};
      for (let i = 0; i < this.nodes.length; i++) {
         dist[this.nodes[i]] = {};
         //对于现有的边缘，将dist设置为与weight相同
         this.edges[this.nodes[i]].forEach(
            e => (dist[this.nodes[i]][e.node] = e.weight)
         );

         this.nodes.forEach(n => {
            //对于所有其他节点，将其分配给infinity-
            if (dist[this.nodes[i]][n] == undefined)
            dist[this.nodes[i]][n] = Infinity;
            //对于自身边缘，将dist分配为0-
            if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
       });
    }

      this.nodes.forEach(i => {
         this.nodes.forEach(j => {
            this.nodes.forEach(k => {
               //检查从i到k再从k到j是否更好
               //而不是直接从i转到j。如果是，则更新
               //我将j值更改为新值
               if (dist[i][k] + dist[k][j] < dist[i][j])
                  dist[i][j] = dist[i][k] + dist[k][j];
          });
       });
    });
      return dist;
 }
}

class UnionFind {
   constructor(elements) {
      //断开连接的组件数量
      this.count = elements.length;

      //跟踪连接的组件
      this.parent = {};

      //初始化数据结构，使所有
      //元素有自己的父母
      elements.forEach(e => (this.parent[e] = e));
 }

   union(a, b) {
      let rootA = this.find(a);
      let rootB = this.find(b);

      //根是相同的，因此它们已经连接。
      if (rootA === rootB) return;

      //始终将根较小的元素作为父元素。
      if (rootA < rootB) {
         if (this.parent[b] != b) this.union(this.parent[b], a);
         this.parent[b] = this.parent[a];
    } else {
         if (this.parent[a] != a) this.union(this.parent[a], b);
         this.parent[a] = this.parent[b];
    }
 }

   //返回节点的最终父级
   find(a) {
      while (this.parent[a] !== a) {
         a = this.parent[a];
    }
      return a;
 }

   //检查2个节点的连接
   connected(a, b) {
      return this.find(a) === this.find(b);
 }
}