Introduction

Graphs are a data structure that is used to model relationships between objects. They are composed of nodes and edges. Nodes are the objects and edges are the relationships between those objects Graphs are used to model things such as social networks, road networks, and computer networks.

Traversing a Graph

Traversing a graph is the process of visiting every node in the graph. There are many different ways to traverse a graph, and each has its own pros and cons. In this article, we will explore the different ways to traverse a graph and compare them.

Breadth First Search

Breadth First Search (BFS) is a graph traversal algorithm that starts at a given node and visits every node in the graph that is reachable from that node. BFS is a great algorithm to use when you want to find the shortest path between two nodes in a graph. BFS is also a great algorithm to use when you want to find all the nodes that are reachable from a given node.

Implementations

Recursive

function bfsRecursive<T>(graph: Graph<T>, start: T): T[] {
  const visited: T[] = [];
  const queue: T[] = [start];

  function visit(node: T) {
    if (visited.includes(node)) {
      return;
    }

    visited.push(node);
    queue.push(...graph.getNeighbors(node));
  }

  while (queue.length > 0) {
    const node = queue.shift();
    visit(node);
  }

  return visited;
}

Iterative

function bfsIterative<T>(graph: Graph<T>, start: T): T[] {
  const visited: T[] = [];
  const queue: T[] = [start];

  while (queue.length > 0) {
    const node = queue.shift();
    if (visited.includes(node)) {
      continue;
    }

    visited.push(node);
    queue.push(...graph.getNeighbors(node));
  }

  return visited;
}

Depth First Search

Depth First Search (DFS) is a graph traversal algorithm that starts at a given node and visits every node in the graph that is reachable from that node. DFS is a great algorithm to use when you want to find all the nodes that are reachable from a given node. DFS is also a great algorithm to use when you want to find all the nodes that are reachable from a given node in a specific order.

Implementations

Recursive

function dfsRecursive<T>(graph: Graph<T>, start: T): T[] {
  const visited: T[] = [];

  function visit(node: T) {
    if (visited.includes(node)) {
      return;
    }

    visited.push(node);
    graph.getNeighbors(node).forEach(visit);
  }

  visit(start);

  return visited;
}

Iterative

function dfsIterative<T>(graph: Graph<T>, start: T): T[] {
  const visited: T[] = [];
  const stack: T[] = [start];

  while (stack.length > 0) {
    const node = stack.pop();
    if (visited.includes(node)) {
      continue;
    }

    visited.push(node);
    stack.push(...graph.getNeighbors(node));
  }

  return visited;
}

Comparing the Implementations

Performance

Ergonomics

Conclusion

In this article, we explored the different ways to traverse a graph. We looked at the different types of traversals, the pros and cons of each, and how to implement them in TypeScript. We also compared the different implementations in terms of performance, ergonomics, and readability. We also included a real world example of a usage with the example of a social network.