Graph

• Quick summary: a data structure that stores items in a connected, non-hierarchical network.
• Important facts:
  • Each graph element is called a node, or vertex.
  • Graph nodes are connected by edges.
  • Graphs can be directed or undirected.
  • Graphs can be cyclic or acyclic. A cyclic graph contains a path from at least one node back to itself.
  • Graphs can be weighted or unweighted. In a weighted graph, each edge has a certain numerical weight.
  • Graphs can be traversed. See important facts under Tree for an overview of traversal algorithms.
  • Data structures used to represent graphs:
    • Edge list: a list of all graph edges represented by pairs of nodes that these edges connect.
    • Adjacency list: a list or hash table where a key represents a node and its value represents the list of this node's neighbors.
    • Adjacency matrix: a matrix of binary values indicating whether any two nodes are connected.
• Pros:
  • Ideal for representing entities interconnected with links.
• Cons:
  • Low performance makes scaling hard.
• Notable uses:
  • Social media networks.
  • Recommendations in ecommerce websites.
  • Mapping services.
• Time complexity (worst case): varies depending on the choice of algorithm. O(n*lg(n)) or slower for most graph algorithms.
• See also:
  • The Simple Reference to Graphs

xxxxxxxxxx

console.log(graph.adjacencyList);

class Graph {

  constructor() {

    this.adjacencyList = {};

  }

​

  addVertex(nodeVal) {

    this.adjacencyList[nodeVal] = [];

  }

​

  addEdge(src, dest) {

    this.adjacencyList[src].push(dest);

    this.adjacencyList[dest].push(src);

  }

​

  removeVertex(val) {

    if (this.adjacencyList[val]) {

      this.adjacencyList.delete(val);

    }

​

    this.adjacencyList.forEach((vertex) => {

      const neighborIdx = vertex.indexOf(val);

      if (neighborIdx >= 0) {

        vertex.splice(neighborIdx, 1);

      }

    });

  }

​

  removeEdge(src, dest) {

    const srcDestIdx = this.adjacencyList[src].indexOf(dest);