当前位置: 首页 > 编程笔记 >

用Javascript完成图类

郎建章
2023-03-14
本文向大家介绍用Javascript完成图类,包括了用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);
 }
}
 类似资料:
  • 我是Hadoop和Map/reduce框架的新手。在进行第一个程序时,字数问题,我陷入了跟踪者的工作细节。Map/Reduce完成图代表什么?或者通俗地说,x,y轴上代表什么?

  • 问题内容: 在Xcode 8中,键入时图像会自动完成。 问题是: 为什么? 我尝试使用建议的结果初始化UIImage,但是它不起作用。 有谁知道如何使用它? 问题答案: Xcode 8会自动识别资产目录中的所有图像,并将它们作为建议提供给UIImage初始化程序。 因此,基本上,您需要做的只是以下操作(就像您在问题中所做的那样,但是必须有其他令人不安的事情): 然后仅在要设置图像时使用。 在后台,

  • 问题内容: 我想用表调用一些针对div的jQuery函数。该表中填充了。 当我打电话时 我没有结果也 没有帮助。 ng重复填充完成后,有什么方法可以执行功能?我已经阅读了有关使用custom的建议,但是我不知道如何在ng-repeat和div中使用它。 问题答案: 确实,您应该使用指令,并且没有与ng-Repeat循环的结尾相关的事件(因为每个元素都是单独构造的,并且具有自己的事件)。但是a)使用

  • 问题内容: 我正在使用Angular构建Web应用程序,并且试图找到一种方法来等待所有元素都经过评估并且包括完成加载。例如,菜单是一个已加载的视图,每个页面的主要内容也是如此,因此至少有两个s被评估并加载。最重要的是菜单包含嵌套s,它们构成了我的菜单。在所有这些包含项以及其中的所有角度函数均已加载并且DOM已准备就绪之后,我需要一种启动脚本的方法。 Angular完成页面设置后,是否会触发任何事件

  • 问题是: 我们提供了一些简单的JavaScript模板代码。您的目标是修改应用程序,以便您可以正确地切换按钮以在ON状态和OFF状态之间切换。当按钮打开并被单击时,它将关闭,其中的文本将从打开变为关闭,反之亦然。您可以自由添加类和样式,但要确保保持元素ID的原样。 所以我所尝试的 我是JavaScript的新手,这就是我在这里寻求帮助的原因。

  • 我试过这个: 结果:s3上的5.9 gig文件。似乎不包含多个部分。 我找到了这个示例,但是没有定义