Understand Graphs and Trees with JavaScript

Understanding Graphs and Trees with JavaScript

Photo by Mila Tovar on Unsplash

In the last article, I introduced the principal data structures like stacks, queues, and hash tables. This article is a second part where I will explain two important data structures: graph and tree, demonstrating how you can implement them with JavaScript.

If you haven’t read the first part, please click here to read it before further reading the second part.

Understanding Graphs

A graph is a structure used to represent non-linear relationships between objects. Graph objects are named nodes (or vertices), and the relationships between objects are named edges. The number of edges connected to a node is called a degree.

Graphs are essential to represent complex data relationships and have many applications in diverse fields like logistics, gene mapping, and air traffic control.

A sequence of nodes connected by edges is named a path. When the path starts and ends on the same node, it’s named a cycle.

When the edges in a graph have a single direction, the graph is called a directional graph (digraph). When the edges are bi-directional, the graph is called an undirected graph.

We can also assign values to the edges. In that case, the graph is called a weighted graph. An example of a weighted graph is an airway map, where the waypoints are the nodes, the routes connecting the waypoints are the edges, and the distances between waypoints are the weights.

Part of the Brazil en-route chart, available at decea.mil.br

How to implement graphs

There are two main techniques to represent a graph: adjacent matrix , which uses a matrix listing all nodes horizontally and vertically, adding a number in the intersections representing the edges connecting the nodes, and adjacent list , which uses a list containing the reference of nodes connected by edges.

We can implement an undirected graph with adjacent lists in JavaScript by creating two classes as follows:

Let’s start by creating the Node class.

export class Node {
  constructor(value) {
    this.adjacentNodes = new Set();
    this.value = value;
  }

  getAdjacentNodes() {
    return this.adjacentNodes;
  }

  addAdjacentNode(node) {
    if (!this.adjacentNodes.has(node)) {
      return this.adjacentNodes.add(node);
    }
  }

  removeAdjacentNode(node) {
    return this.adjacentNodes.delete(node);
  }
}

The Node class has the properties adjacentNodes (a set of adjacent nodes) and value (the node value), and the methods getAdjacentNodes, addAdjacentNode, and removeAdjacentNode to get, add, and remove adjacent nodes.

Next, create the Graph class as follows:

import { Node } from "./node.js";

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

  addNode(value) {
    if (!this.nodes.has(value)) {
      const node = new Node(value);
      this.nodes.set(value, node);
    }
  }

  removeNode(value) {
    const currentNode = this.nodes.get(value);

    if (this.nodes.has(value)) {
      for (const node of this.nodes.values()) {
        node.removeAdjacentNode(currentNode);
      }
    }
    this.nodes.delete(value);
  }
}

In the implementation above, we are using a Map object to store the graph nodes. The JavaScript map class provides all the advantages of the hash table explained in the last article.

The class also has the method addNode, for creating new nodes and adding them to the nodes map, and the method removeNode, for removing the node from all adjacent lists and then removing it from the nodes map.

We also need to create methods for adding and removing edges in the Graph class as follows:

addEdge(sourceValue, destinationValue) {
    const source = this.nodes.get(sourceValue);
    const destination = this.nodes.get(destinationValue);

    if (source && destination) {
      source.addAdjacentNode(destination);
      destination.addAdjacentNode(source);
    }
 }

 removeEdge(sourceValue, destinationValue) {
    const source = this.nodes.get(sourceValue);
    const destination = this.nodes.get(destinationValue);

    if (source && destination) {
      source.removeAdjacentNode(destination);
      destination.removeAdjacentNode(source);
    }
  }

In an undirected graph with adjacent lists, we define edges by adding the source and destination nodes to the adjacent list of each node.

In the example above, the method addEdge receives the source and destination values, searches for each node in the nodes map, and adds the corresponding nodes to the adjacent lists. The method removeEdge is very similar, but instead of adding the nodes, it will remove nodes from the adjacent lists.

A practical example

Imagine you want to represent the following graph:

You can represent the graph as in the following example:

const graph = new Graph();

const nodes = new Set(["A", "B", "C", "D", "E"]);

for (const node of nodes.values()) {
  graph.addNode(node);
}

graph.addEdge("A", "B");
graph.addEdge("A", "E");

graph.addEdge("B", "C");
graph.addEdge("B", "D");

graph.addEdge("C", "E");
graph.addEdge("C", "D");

graph.addEdge("D", "E");
graph.addEdge("E", "A");

/* Adjacent lists:
 * A > ["B", "E"];
 * B > ["A", "C", "D"];
 * C > ["B", "E", "D"];
 * D > ["B", "C", "E"];
 * E > ["A", "C", "D"];
 */

Now, let’s understand another useful type of graph named tree.

Understanding Trees

A tree is a specific type of graph. We say it’s a tree when the graph is undirected, has no cycles, and all nodes are connected. The first node in a tree is named root, the last node in a path is named leaf , and the path connecting the root node to a leaf node is named branch. The number of edges connecting the root to the more distant leaf is named height.

Trees are used for solving diverse problems like building other data structures, fast searching algorithms, and machine learning models.

You can implement different versions, depending on the problem you need to solve, such as binary search trees , expression trees , and balanced trees.

A tree is a type of graph, so you can also use the techniques explained before ( adjacent matrix and adjacent list).

Graph and tree traversal algorithms

Graph traversal is the process of visiting each node in a graph. There are various traversal algorithms for specific uses. I’ll explain the breadth-first search (BFS) and depth-first search (DFS), which you can use to traverse both a graph and a tree.

How to implement a breadth-first search

The BFS algorithm starts in a given node and visits all the adjacent nodes before proceeding. In a tree, the starting node must be the root.

We can implement the BFS algorithm using a queue and registering all visited nodes in a list, as in the following example:

  bfs(firstNode) {
    const nodesVisited = new Set();
    const visitQueue = new Queue();

    visitQueue.add(firstNode);

    while (!visitQueue.isEmpty()) {
      const node = visitQueue.dequeue();

      if (node != "Empty" && !nodesVisited.has(node)) {
        nodesVisited.add(node);
        node
          .getAdjacentNodes()
          .forEach((adjacentNode) => visitQueue.add(adjacentNode));
      }
    }
  }

In the example above, we’re adding the first node to the visitQueue and iterating over the queue until it’s empty. In each iteration, we dequeue the node placed in front, add it to the nodesVisited set, and add all adjacent nodes to the visitQueue. With this method, all nodes will be visited following the order FIFO (first-in, first-out).

How to implement a depth-first search

The DFS algorithm starts in a given node, but instead of visiting all adjacent nodes like in the BFS algorithm, it will visit the following nodes in the path before proceeding.

We can implement the DFS algorithm the same way as BFS, but instead of using a queue, we must use a stack, as in the following example:

 dfs(firstNode) {
    const nodesVisited = new Set();
    const visitStack = new Stack();

    visitStack.push(firstNode);

    while (!visitStack.isEmpty()) {
      const node = visitStack.pop();

      if (node != "Underflow" && !nodesVisited.has(node)) {
        nodesVisited.add(node);
        node
          .getAdjacentNodes()
          .forEach((adjacentNode) => visitStack.push(adjacentNode));
      }
    }
  }

With this method, all nodes will be visited following the order LIFO (last-in, first-out).

Next steps

Graphs and trees are complex data structures. It’s challenging to resume all this knowledge in one article, so I recommend you to keep studying, and to help you in this journey, check these free resources:

• Graph implementations : https://isaaccomputerscience.org/concepts/dsa_datastruct_graph_implementation?examBoard=all&stage=all&topic=data_structures
• Tree implementations : https://isaaccomputerscience.org/concepts/dsa_datastruct_tree?examBoard=all&stage=all&topic=data_structures

Conclusion

Thank you for reading! I hope this article has interesting and informative to you. Let me know your thoughts in the comments section, and consider following me for more articles like this.