Working With Graphs

In previous articles I’ve explored various different data structures — from linked lists and trees to hash tables. In this article I’ll explore the basics of working with a graph data structure.

To begin, let’s define the graph data structure. Graphs are collections of data points — called nodes or vertices — which connect to each other. How each node connects to another is where the value in graph data lies, which makes graphs great for displaying how one item is associated with another.

The image below is an example of a basic graph.

Diagram of a Simple Graph

Graphs are used to model data all over the web. From friend circles on Facebook to recommending products other people have purchased on Amazon, data graphs make it possible.

Graphs can come in two main flavors — directed or undirected graphs and weighted / unweighted graphs. The two categories are not mutually exclusive, so it’s possible to have a directed and weighted graph simultaneously for example.

Undirected Graph

An undirected graph is when each node has a reciprocal connection. So, you could say A is connected to B and B is connected to A. A real world example of this is when you add a friend on Facebook. Each user now has full access to the other user’s public content.

Undirected Graph Example — Facebook Friends

Directed Graph

In a directed graph, the connections between two nodes is not necessarily reciprocated. So, A can connect with B but B is not automatically connected to A. A real world example of a directed graph is followers on Instagram. When you follow a new account, that new account does not automatically follow you back.

This is represented in the graph below where some arrows are bi-directional and others are single directional.

Directed Graph Example — Instagram Followers

Weighted vs Unweighted Graph

Weighted graphs add additional information to the relationship between two nodes. This is done by assigning a numeric value to the edge — the line that connects the two nodes. This value could represent the distance or how strongly two nodes are connected. A real world example of a weighted graph is Google Maps.

When you look up directions for a location, Google Maps determines the fastest route, which is usually determined by finding the shortest distance between the beginning and end nodes.

Weighted Undirected Graph Example — Google Maps

How to Create a Graph

Graph data can be represented in two main formats:

1. An Adjacency List
2. An Adjacency Matrix

Both accomplish the same goal however each have their pros and cons. An adjacency list is often created with a hash table. The key is the node and the values are all of its connections.

Example of an adjacency list

In an adjacency matrix the data is often stored in nested arrays. The easiest way to picture an adjacency matrix is to think of a spreadsheet. In an undirected graph each node represents a column and a row. Each cell between a row and column represents whether or not a node is connected to another. Zero typically means no association and one means there is an association.

Example of an adjacency matrix

The difference in their design leads to performance differences based off the desired operation. In general, if your data has a lot of vertices (nodes) but each vertex has a limited number of connections, an adjacency list is a better option. If you have many vertices and each is connected to many other vertices then an adjacency matrix is a better option.

Adding and Removing Data

Adding data to a graph is pretty simple. Assuming we’re using an adjacency list we simply create a new key in our hash table. We can then create another method to handle adding connections (called edges). How those connections are established will be dependent on whether we’re creating a directed or undirected graph.

When deleting an edge (a connection) we loop through the key-value pairs and remove the desired edge. When removing a whole vertex, we follow the same process as with removing an edge except at the end we also delete the key from our hash table.

The following code is a basic skeleton for implementing an undirected graph using an adjacency list.

class Graph {
    constructor(){
        this.list = {}
    }
    addVertex(key){
        if (!this.list[key]) this.list[key] = []
    }
    addEdge(v1, v2){
        if (this.list[v1]) this.list[v1].push(v2)
        if (this.list[v2]) this.list[v2].push(v1)
    }
    removeEdge(v1, v2){
        if (this.list[v1]) {
            this.list[v1] = this.list[v1].filter(value => value !== v2)
        }
        if (this.list[v2]){
            this.list[v2] = this.list[v2].filter(value => value !== v1)
        }
    }
    removeVertex(v1){
        if (this.list[v1]){
            this.list[v1].forEach((v2) => {
                this.removeEdge(v1, v2)
            })
        }
        delete this.list[v1]
    }
}

Graph Traversal

As with traversing a binary tree, there are two main flavors for graph traversal — breadth-first search and depth-first search. In breadth-first searching we visit all of the connections of a given vertex first before moving on to the next vertex in the graph. In depth-first searching, we follow a given connection until it dead ends then work our way back up to follow another connection on the vertex.

It’s important to realize that with graph traversal there is not necessarily one right answer. There are many paths one could take to touch on every vertex in the graph. Additionally, there is no one correct starting point. Our traversals must start by being told which node to look at first. This is different from trees where there is a root node that kicks off the search.

A key concept to understand when dealing with graph traversal is keeping track of vertices you’ve already visited. In any graph traversal, you’ll inevitably come across a vertex you’ve already seen before. You need a way to keep track of these seen vertices so your traversal doesn’t go forever.

The image below shows a graph where vertices A B D are seen. On the right hand side a hash table is setup to keep track of them.

Creating a Hash Table to Track Seen Vertices in Graph Traversal

Depth First and Breadth First Code Implementation

1. Given a node, add it to a stack or queue, create a loop that runs as long as there are nodes in the stack or queue.
2. Pop or shift off a node. If you have NOT already visited that node, go to it. Add it to your results array. Add it to the visited nodes hash table.
3. Loop through all the connections that node has and add them to your stack or queue.
4. When the stack or queue ends, return your results array.

    DFS_iterative(vertex){
        let visited = {}
        let results = []
        let stack = []
        stack.push(vertex)
        while (stack.length > 0) {
            vertex = stack.pop();
            if (!visited[vertex]) {
                results.push(vertex)
                visited[vertex] = true
                this.list[vertex].forEach(v => {
                    stack.push(v)
                })
            }
        }
        return results
    }
    BFS_iterative(vertex){
        let visited = {}
        let results = []
        let queue = []
        queue.push(vertex)
        while (queue.length > 0){
            vertex = queue.shift();
            if (!visited[vertex]){
                visited[vertex] = true;
                results.push(vertex)
                this.list[vertex].forEach(v => {
                    queue.push(v)
                })    
            }
        }
        return results;
    }