Computer >> Máy Tính >  >> Lập trình >> Javascript

Cấu trúc dữ liệu biểu đồ trong Javascript

Đồ thị là một biểu diễn bằng hình ảnh của một tập hợp các đối tượng trong đó một số cặp đối tượng được nối với nhau bằng các liên kết. Các đối tượng được kết nối với nhau được biểu thị bằng các điểm được gọi là đỉnh và các liên kết nối các đỉnh được gọi là cạnh .

Về mặt hình thức, biểu đồ là một cặp tập hợp (V, E) , ở đâu V là tập hợp các đỉnh và E là tập hợp các cạnh, nối các cặp đỉnh. Hãy xem biểu đồ sau -

Cấu trúc dữ liệu biểu đồ trong Javascript

Trong biểu đồ trên,

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

Thuật ngữ

Đồ thị toán học có thể được biểu diễn trong cấu trúc dữ liệu. Chúng ta có thể biểu diễn một đồ thị bằng cách sử dụng một mảng các đỉnh và một mảng hai chiều các cạnh. Trước khi tiếp tục, chúng ta hãy tự làm quen với một số thuật ngữ quan trọng -

  • Đỉnh - Mỗi nút của đồ thị được biểu diễn dưới dạng một đỉnh. Trong ví dụ sau, vòng tròn được dán nhãn đại diện cho các đỉnh. Do đó, A đến G là các đỉnh. Chúng ta có thể biểu diễn chúng bằng một mảng như trong hình sau. Ở đây A có thể được xác định bằng chỉ số 0. B có thể được xác định bằng cách sử dụng chỉ mục 1, v.v.

  • Cạnh - Cạnh biểu diễn đường đi giữa hai đỉnh hoặc đường thẳng giữa hai đỉnh. Trong ví dụ sau, các đường từ A đến B, B đến C, v.v. đại diện cho các cạnh. Chúng ta có thể sử dụng một mảng hai chiều để biểu diễn một mảng như trong hình sau. Ở đây AB có thể được biểu diễn là 1 ở hàng 0, cột 1, BC là 1 ở hàng 1, cột 2, v.v., giữ các kết hợp khác là 0.

  • Sự gần gũi - Hai nút hoặc hai đỉnh kề nhau nếu chúng được nối với nhau qua một cạnh. Trong ví dụ sau, B giáp với A, C tiếp giáp với B, v.v.

  • Đường dẫn - Đường đi biểu diễn một dãy các cạnh giữa hai đỉnh. Trong ví dụ sau, ABCD biểu thị một đường đi từ A đến D.

Đây là cách triển khai đầy đủ của Lớp đồ thị bằng Javascript.

Ví dụ

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) {
      // Create a Stack and add our initial node in it
      let s = new Stack(this.nodes.length);
      let explored = new Set();
      s.push(node);

      // Mark the first node as explored
      explored.add(node);

      // We'll continue till our Stack gets empty
      while (!s.isEmpty()) {
         let t = s.pop();

         // Log every element that comes out of the Stack
         console.log(t);

         // 1. In the edges object, we search for nodes this node is directly connected to.
         // 2. We filter out the nodes that have already been explored.
         // 3. Then we mark each unexplored node as explored and push it to the Stack.
         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() {
         // Create a Stack and add our initial node in it
         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() {
         // Initialize graph that'll contain the MST
         const MST = new Graph();
         if (this.nodes.length === 0) {
            return MST;
         }

         // Select first node as starting node
         let s = this.nodes[0];

         // Create a Priority Queue and explored set
         let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
         let explored = new Set();
         explored.add(s);
         MST.addNode(s);

         // Add all edges from this starting node to the PQ taking weights as priority
         this.edges[s].forEach(edge => {
            edgeQueue.enqueue([s, edge.node], edge.weight);
         });

         // Take the smallest edge and add that to the new graph
         let currentMinEdge = edgeQueue.dequeue();
         while (!edgeQueue.isEmpty()) {
            // COntinue removing edges till we get an edge with an unexplored node
            while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
               currentMinEdge = edgeQueue.dequeue();
            }
            let nextNode = currentMinEdge.data[1];
            // Check again as queue might get empty without giving back unexplored element
            if (!explored.has(nextNode)) {
               MST.addNode(nextNode);
               MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);

            // Again add all edges to the PQ
            this.edges[nextNode].forEach(edge => {
               edgeQueue.enqueue([nextNode, edge.node], edge.weight);
            });

            // Mark this node as explored
            explored.add(nextNode);
            s = nextNode;
         }
      }
      return MST;
   }

   kruskalsMST() {
      // Initialize graph that'll contain the MST
      const MST = new Graph();

      this.nodes.forEach(node => MST.addNode(node));
      if (this.nodes.length === 0) {
         return MST;
      }

      // Create a Priority Queue
      let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);

      // Add all edges to the Queue:
      for (let node in this.edges) {
         this.edges[node].forEach(edge => {
            edgeQueue.enqueue([node, edge.node], edge.weight);
         });
      }
      let uf = new UnionFind(this.nodes);

      // Loop until either we explore all nodes or queue is empty
      while (!edgeQueue.isEmpty()) {
         // Get the edge data using destructuring
         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 = {};

      // Stores the reference to previous nodes
      let prev = {};
      let pq = new PriorityQueue(this.nodes.length * this.nodes.length);

      // Set distances to all nodes to be infinite except startNode
      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]] = {};

      // For existing edges assign the dist to be same as weight
      this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));

   this.nodes.forEach(n => {
      // For all other nodes assign it to infinity
      if (dist[this.nodes[i]][n] == undefined)
      dist[this.nodes[i]][n] = Infinity;
      // For self edge assign dist to be 0
      if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
   });
}

this.nodes.forEach(i => {
   this.nodes.forEach(j => {
      this.nodes.forEach(k => {
         // Check if going from i to k then from k to j is better
         // than directly going from i to j. If yes then update
         // i to j value to the new value
         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) {
      // Number of disconnected components
      this.count = elements.length;

      // Keep Track of connected components
      this.parent = {};
      // Initialize the data structure such that all elements have themselves as parents
      elements.forEach(e => (this.parent[e] = e));
   }

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

      // Roots are same so these are already connected.
      if (rootA === rootB) return;

      // Always make the element with smaller root the parent.
      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];
      }
   }

   // Returns final parent of a node
   find(a) {
      while (this.parent[a] !== a) {
      a = this.parent[a];
   }
   return a;
}

// Checks connectivity of the 2 nodes
   connected(a, b) {
      return this.find(a) === this.find(b);
   }
}