Graphs

Overview:

A graph is a type of abstract data structure used to represent relationships between things.

It consists of vertices/nodes and edges which represent connections between 2 nodes. Two nodes are said to be connected if it's possible to follow consecutive edges to make a path between those 2 nodes in the graph. The path can be represented by an array of nodes to visit, where the first element is the start node and the last element is the end node. Additionally, graphs can be directed, in which case an edge can only go in one direction, or undirected, where an edge goes both from node 1 to node 2, and from node 2 to node 1. An undirected graph can be stored as a directed graph where any edge added will really add 2 edges, one for each direction.

A graph can also be weighted, which means that each edge has a number, or weight associated with it. The weight is often used to represent length of a path between 2 nodes, or the strength of a connection.

Storing a graph

There are 2 main ways to store a graph. The first is using an adjacency matrix, which is like a table where the space in the ith row and the jth column indicates the weight of the edge between vertices i and j. If there is no connection the weight is set to 0.

The adjacency matrix is sometimes useful as it has certain mathematical properties and allows to check the presence of an edge in constant time, but takes up more space than the second solution: the adjacency list. This is where each vertex is stored in some data structure such as a hash map, along with an array of every edge connected to the graph. This may be slower to access, but takes up less memory and is often easier to implement.

Traversal:

To traverse a graph means to start from a certain node, and then visit every single node which is connected to the start node. There are two main algorithms to traverse a graph: depth-first and breadth-first traversal (DFT and BFT respectively).

Depth-First:

Depth-first traversal means that the algorithm traverses the graph as far as possible down one branch, then travels back up and takes the first available path further down. In computer science terms this will be implemented using a stack, where the algorithm repeatedly adds all of the unvisited neighbours of the current node to the stack, and then travels to the node on the top of the stack:

  traverseDepthFirst (node) {
    // Use a stack to traverse
    let stack = [node], visited = [], next
    while (stack.length !== 0) {
      next = stack.pop()
      let neighbours = this.getEdges(next).filter((v) => !visited.includes(v)) // Get all unvisited neighbours
      neighbours.forEach((v) => stack.push(v)) // Add each neighbour to the stack
    }
    return visited
  }

Depth-first traversal is more useful if you need to be space-efficient, as will usually need to remember fewer nodes than with a breadth-first search.

Breadth-First:

Breadth-first traversal means that the algorithm traverses the graph by visiting every path a little bit: this is achieved by adding each unvisited neighbour of the current node to the end of a queue:

  traverseBreadthFirst (node) {
    // Uses a queue instead of a stack, otherwise the exact same
    let queue = [node], visited = [], next
    while (queue.length !== 0) {
      next = queue.shift()
      let neighbours = this.getEdges(next).filter((v) => !visited.includes(v)) // Get all unvisited neighbours
      neighbours.forEach((v) => queue.push(v)) // Add each neighbour to the queue
    }
    return visited
  }

Since depth-first traversal will usually need to store more information than breadth-first, it is less space-efficient but it is generally quicker at finding the shortest path, a common use of graphs.

Other Important Information:

• A graph is connected if it's possible to reach every single vertex by traversing the graph from a single node
• A cycle is a loop in a graph.
• A tree is a connected graph with no cycles (and therefore the minimum number of edges required to make it connected). Any additional edge added will create a cycle. It's also worth noting that a tree in computer science doesn't have to be stored as a graph (e.g. binary tree)

Demo:

Try using the buttons to play with the interactive graph tool:

Home