← Back

Beginner Graph Traversals

Cover Image for Beginner Graph Traversals
Justin Bender
Justin Bender
Contents

Graph Traversals

On the last post for Binary Tree Traversals we went over how we can move around a binary tree. Where we can pull out data and print it out as needed. For our post today we will have a very similar topic. Although this is going to be a bit different. Today won't have as much structure built in like a binary tree.

Graphs are a data structure that consist of a set of vertices (nodes) connected by edges. Each edge represent a relationship between two vertices. Graphs can be used to model various real-world scenarios, such as social networks, computer networks, transportation systems and more.

Let's go over some graphs at first.

Directed Graphs (Digraphs)

In a directed graph, the edges have a direction, meaning they go from one vertex to another. If there is an edge from vertex A to vertex B, it does not necessarily imply the existence of and edge from vertex B to vertex A.

Used to model relationships with a specific direction, like web page linking or transportation systems.

Undirected Graphs

In an undirected graph, the edges have no direction, and the connection between vertices is bidirectional. If there is an edge between vertex A and vertex B, it implies there is an edge between vertex B and vertex A.

Used to model relationships where the direction does not matter, such as social networks.

Weighted Graph

A weighted graph is a graph where each edge has an associated weight or cost. The weights represent the cost of traversing the edge or the distance between the connected vertices.

Used in various optimization problems, like finding the shortest path between two vertices.

Tree

A tree is a special type of undirected graph that has no cycles (acyclic) and is connected. In a tree, there is a unique path between any two vertices.

Used in hierarchical data structures and various search algorithms, like binary search trees.

Binary Tree

A binary tree is a type of tree where each node has at most two children, commonly referred to as the left child and the right child.

used in various tree-based algorithms, like binary search and binary tree traversal.

Binary Search Tree (BST)

A binary search tree is a binary tree where each node's left child has a value less than the parent's value, and the right child has a value greater than the parent's value.

Used to efficiently perform search, insertion, and deletion operations on sorted data.

Complete Binary Tree

A complete binary tree is a binary tree where all levels are completely filled, except possibly the last level, which is filled from left to right.

Used in heap data structures.

Balanced Binary Tree

A balanced binary tree is a binary tree where the difference in the heights of the left and right subtrees of every node is limited. These trees ensure that search, insertion, and deletion operations have the time complexity of O(log n), where n is the number of nodes.

Bipartite Graph

A bipartite graph is an undirected graph where the vertices can be divided into two disjoint sets such that all edges connect vertices from different sets.

Used in various applications like modeling two-sided relationships or scheduling problems.

Cyclic Graph

A cyclic graph is a graph that contains at least one cycle, which is a closed path in the graph that starts and ends at the same vertex. Cyclic graphs can be both directed and undirected, and they often represent systems with feedback loops or circular dependencies.

Directed Acyclic Graph (DAG)

In a DAG which is Special type of graph where the edges have a direction and, crucially, there are no cycles. In other words, it is a graph that does not contain any directed cycles.

Used in various applications and algorithms due to their unique properties. There are no cycles, it can be used for dependency representation, topological sorting, shortest path algorithms, and data flow. It's important to remember that not all directed graphs are DAGS, and cyclic directed graphs can have different behaviors from DAGS.

Each type of graph has its unique characteristics, and understanding them can help in choosing the appropriate data structure for different problem scenarios.

Setting up for graph problems

What do we do if we have to solve a problem that involves graphs? It's a good idea to take the data and put it into another type of data structure. Let's go over a few.

Adjacency Matrix

An adjacency matrix is a 2D array where rows and columns represent vertices, and the matrix element at (i,j) is 1 if there is an edge between vertex i and vertex j, and 0 otherwise. For weighted graphs, the matrix can store the weight of the edge instead of 1 or 0. The adjacency matrix is straightforward and allows for quick edge queries but may consume more memory, especially for sparse graphs.

Adjacency List

An adjacency list is a more memory-efficient representation of a graph. It uses a hashmap or array to store each vertex's neighbors. For each vertex, there is a list or set containing its adjacent vertices. For weighted graphs, the list can also include the edge weights. The adjacency list is suitable for most graph problems, as it efficiently represents sparse graphs and allows for easy traversal of neighbors.

Edge List

An edge list is a simple list of tuples or objects, each representing an edge in the graph. Each tuple contains the source vertex, target vertex, and optionally the weight of the edge for weighted graphs. The edge list is suitable for simple problems and does no provide direct access to neighbors like the adjacency list or matrix.

Incidence Matrix

An incidence matrix is a 2D array where rows represent vertices, and columns represent edges. Each matrix element at (i,j) is 1 if vertex i is part of edge j, and 0 otherwise. Incidence matrices are used less frequently due to their higher memory consumption and limited advantages compared to other representations.

Graph Class/Object

For object-oriented programming, you can create a Graph class that contains methods for adding vertices and edges and other operations like traversal and shortest path algorithms. This approach encapsulates the graph data and operations in a single entity, providing a more organized and modular solution.

Going over two graph problems

To better understand what we are talking about we will go over two graph problems. This will only scratch the surface. No where close to understanding all of the graphs we have described above. 

class Node {
  - val: Char
  - childre: List<Node>

      [A]
    /     \
   [B]---[C]

[A]-{val: 'A'
    {children: {'B','C'}

Our problems will need to be setup to have a graph to traverse.

function graphSetup() {
  // Define the vertices and edges data
  const vertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'];
  const edges = [
    ['A', 'B'],
    ['B', 'C'],
    ['B', 'H'],
    ['C', 'E'],
    ['H', 'E'],
    ['E', 'F'],
    ['E', 'G'],
    ['G', 'F'],
    ['F', 'D'],
  ];

  // Build the graph from the provided data
  class Vertex {
    constructor(id) {
      this.id = id !== undefined ? id : null;
      this.edges = [];
    }
  }

  function deserialize(vertices, edges) {
    let container = {};
    for (let i = 0; i < vertices.length; i++) {
      container[vertices[i]] = new Vertex(vertices[i]);
    }
    let v1;
    let v2;
    edges.forEach((edge) => {
      v1 = edge[0];
      v2 = edge[1];
      container[v1].edges.push(container[v2]);
      container[v2].edges.push(container[v1]);
    });

    return container[vertices[0]];
  }

  return deserialize(vertices, edges);
}

const graph = graphSetup();
console.log(graph);

Vertex { id: 'A', edges: [ Vertex { id: 'B', edges: [Array] } ] }

Breadth First Search

Implement Breadth First Search using a queue and a while loop.

  • Input: {Vertex} - the starting vertex (will always start at vertex A)

Vertices have the following properties.

  • id: the data stored in the vertex

  • edges: a list of vertices connected to this vertex

  • Output: {String} - a String with the IDs arranged in a breadth first manner

INPUT:

        C
       / \
A --- B   E --- F --- D
       \ / \   /
        H    G

OUTPUT: "ABCHEFGD"

This order is one of the possible breadth-first path. "ABHCEFGD" is also a valid
breadth-first traversal, but be aware this will not match with the test
expectations. To handle for this, make sure you work with the edges for a node
in the order they appear in the nodes' edge list.

NOTES:

  • You man use an array or linked list for your queue
  • There is no difference between the dashed lines and forward/back slashes when it comes to defining the connections between graph nodes.

HINT: Use a set or hash table to handle redundancy

Sudo Code:

  • current = q.dequeue()
  • loop through current edges
  • if not visited
  • enqueue edge
  • add edge to visited
  • add current ID to result

Solution:

const bfs = (origin) => {
  if (origin === null) return '';

  const queue = [];
  const visited = new Set();
  // collecting in array to return as a string
  const return_string = [];
  // add first value to queue
  queue.push(origin);
  // add first value to visited
  visited.add(origin);
  // loop over the queue until empty
  while (queue.length > 0) {
    // dequeue to current
    const current = queue.shift();
    // loop through current edges
    for (let edge of current.edges) {
        // if not visited
        if (!visited.has(edge)) {
          // enqueue edge
          queue.push(edge);
          // add edge to visited
          visited.add(edge);
        }
    }
    // add current ID to result
    return_string.push(current.id);
  }
  // join array into string to return
  return return_string.join('');
};

const bfs_solution = bfs(graph);
console.log(bfs_solution);

Console:

ABCHEFGD

Find all paths

Given a starting vertex, and a string destination, return all valid paths for a given source and destination.

  • Input: {Vertex} origin - the starting vertex

  • Input: {Integer} destination - integer value of the destination vertex

  • Output: {String Array} result - a shorted array of all paths from the origin to the destination 

INPUT:

        C
       / \
A --- B   E --- F --- D
       \ / \   /
        H    G

Origin: (A)

OUTPUT: ["ABCEFD", "ABCEGFD", "ABHEFD", "ABHEGFD"]

EXPLANATION:

There are four paths from vertex A to vertex D. These four paths are listed
above and then sorted within their array.
  • Contrary to breadth-first traversal, to find all paths, it is advised to use depth-first traversal implemented with recursion.
  • There is no difference between the dashed lines and forward/back slashes when it comes to defining the connections between graph nodes.

HINT: Use a set or hash map to handle redundancy

Solution:

const find_all_paths = (origin, destination) => {
  const visited = new Set();
  const result = [];

  const traverse = (current, path) => {
    if (visited.has(current)) {
      return;
    }

    if (current.id === destination) {
      result.push(path.join(''));
      return;
    }

    const edges = current.edges;
    // before traveling outwards
    visited.add(current);

    for (let edge of edges) {
      path.push(edge.id);
      traverse(edge, path);
      path.pop();
    }
    visited.delete(current);
  };
  traverse(origin, [origin.id]);
  result.sort();
  return result;
};

const find_all_paths_solution = find_all_paths(graph, 'D');
console.log(find_all_paths_solution);

Output:

[ 'ABCEFD', 'ABCEGFD', 'ABHEFD', 'ABHEGFD' ]