If Jane and John are friends, we can draw a line between them. If Jane and Elis are also friends, we can draw a line from Jane to Elis. If we continued with this, gathering enough information, we could form a graph that shows how many "friends of friends" there are between you and Bill Gates! Relationships, city streets, and computer graphics all have one big thing in common: they can be represented by graphs! As it turns out, graphs are a very powerful tool to have in a programmers back pocket as they have endless real world applications.

Assumptions

What is a Graph

In respect to computer science, a graph is an abstract data structure that consists of vertices connected by edges.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/datastructures/Graphs_01.png" alt="pretty graph header" style="width:500px;max-width:95%;"> </div>

The mathematical properties and concepts of graphs have been studied far before computers were invented, spanning back to 1736 when Leonard Euler published a paper on Graph Theory. Many of the concepts of Graph Theory are much more prevalently studied in discrete mathematics, a field of study that has largely contributed to the algorithms and logical structures that all computers use today.

> Compared to a data structured like a linked list, we could say that the vertices are the nodes, and the edges are the pointers between the nodes. However, some graphs such as weighted graphs may actually give these edges values of their own to act as weights, this is especially useful in GPS maps.

Graph Structure

Graphs come in many varieties based on what the needs of the program are. The most basic graphs can be implemented using an adjacency matrix, which is a two-dimensional array that contains the vertices and an array that shows which vertices a specific vertex shares an edge with.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/datastructures/Graphs_02.png" alt="adjacency matrix for a graph" style="max-width:95%;"> </div>

> This implementation is not well-suited for large graphs where not all nodes will have many connections, as it requires an equivalent of O(n<sup>2</sup>) memory compared to the number of vertices in the graph.

More common approaches in modern languages include using Maps, Sets, and Lists. For this basic implementation, we'll be utilizing an array of linked lists. The advantage that this holds is that it is easy to access a particular node on the graph, and the amount of memory is proportionate to the number of vertices and edges, and not the square of the vertices.

/* pseudo-code */
class Graph {
    // The number of vertices in the graph (hard coded!)
    int vertices = 16;
    // An array of Linked Lists representing the nodes
    // and their adjacency's.
    LinkedList [] adj; 
    
/* Instantiating a new graph with a set number of vertices.
A dynamic implementation would allow for vertices to
be added on the fly. */
   Graph(int verts) {
     vertices = verts;
     adj = new LinkedList [vertices];
     for( int i = 0; I &lt; vertices; i++ ){
     adj[i] = new LinkedList();
     }
   }
}

> While this implementation is good for visualization, utilizing regular arrays does have the drawback of not being easily expandable. In this case, a Linked List of LinkedLists, or even a Map would be a better choice!

Types of Graphs

Before jumping into inserting elements into a graph, it is worth learning about the two general types of graphs: directed graphs and undirected graphs. These two types of graphs make a big difference in the kind of graph that is being implemented, and sometimes one is preferred.

Undirected Graphs

Undirected graphs contain edges that allow for two-way traversal. If node A is connected to node B in an undirected graph, there is a path from A to B, and a Path from B to A, both by way of edge AB (or BA).

It can help to imagine the relationship between connected nodes on undirected graphs like friendships on a social media platform. If person A sends person B a friend request, upon accepting the request, person A is friends with person B, and person B is friends with person A.

To represent this is our code example, we will add an edge from node A to node B, and will be adding an edge from node B to node A.

/* pseudo-code */
LinkedList [] adj;

function addEdge(int nodeA, int nodeB){
    // Add an edge from node A to node B
    adj[nodeA].addFirst(nodeB);
    // Add an edge from node B to node A
    adj[nodeB].addFirst(nodeA);
}

> In this implementation, the nodes are represented by their index in the adjacency array. So adj[nodeA].addFirst(nodeB); represents adding nodeB to the adjacency list of nodeA.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/datastructures/Graphs_03.png" alt="undirected graph" style="width:500px;max-width:95%;"> </div>

Directed Graphs

If undirected graphs can be represented by mutual friendships on a social media site, then we can image that directed graphs are then similar to one-way relationships on other social media sites. For instance, say that the site allows you to "follow" your favorite musician. When you click the follow button, you subscribe to their updates, but the opposite is not true. That person can follow you back, which would then make it a mutual relationship, however this is not required in a directed graph.

To represent this in code, we'll follow the same steps as we had taken in the undirected graph, except that we won't be adding a mutual edge:

/* pseudo-code */
LinkedList [] adj;

function addEdge(int fromNode, int toNode){
    // Add an edge from node A to node B
    adj[fromNode].addFirst(toNode);
}

Directed graphs are useful when trying to create one-way relationships such as implementing follower-style social media sites, or constructing street maps that contain one-way streets as well as two-way streets.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/datastructures/Graphs_04.png" alt="directed graph" style="width:500px;max-width:95%;"> </div>

Traversing Graphs

This topic will only be briefly touched on as graph traversal is a large category. Nonetheless, the two major strategies of traversing a graph are known as breadth-first-search (BFS) and depth-first-search (DFS).

Imagine being in a maze, taking the role of a cautious adventurer. You don't want to get lost in the maze, so instead of wandering along a path aimlessly, you walk to the end of the first corridor.

Once you've taken note of that point in the maze, you go back to your starting point, taking the next available corridor until it turns.

After exploring the first few points from the beginning, you return to the end of the first corridor, and walk to the end of the next hall, taking notes of which hallways you have walked down as you explore.

You continue this process of cautiously exploring only one new corridor at a time in each direction until you find the exit.

If you had a piece of paper that you were keeping track of the maze layout while traversing the corridors, you would notice that the map would appear to "grow" from the starting point until the exit was found.

In breadth-first-search, you look at all the nodes that are nearest first before traversing deeper into the graph.

Imagine being back in the same maze, but this time you are an adventurer that likes to live a little closer to the edge. Instead of exploring the closest hallways first, you decide that you will follow one hallway all the way until you reach a dead end, or come to an intersection that you have already crossed.

Once you reach the first dead end or area that you've already been to, you backtrack until the last place that you had an option to explore a different corridor. In a sense, you are going deep into the maze before trying new areas.

While breadth first search uses a FIFO order of a queue to explore the breadth of the graph, depth first search uses the LIFO (or FILO) order of stacks to explore the graph in depth before returning to earlier nodes.

Benefits of BFS and DFS

BFS and DFS can be seen more so as frameworks for traversing a graph than concrete methods in themselves. This is because, through the structure that they are implemented in, you can solve many different graph theory problems by only adding a few lines of code. Problems that can be solved using the BFS and DFS framework include finding the shortest path to a node, discovering connected components in a graph, and putting the graph into topological order.

When to use Graphs

Between representing mazes, friendships, and modeling city streets, it is clear that graphs have a wide range of use cases that can be seen across many fields of study. Some more applications include:

  • Detecting infinite loops and "dead code" before a program is run: modern IDE's use graph-structures to analyze code and detect any unreachable "nodes". For instance, code types after a return statement in a function will never get executed.
  • Computer Networks: the topology of a network is well-represented by a graph type structure.
  • Modeling any type of data structure: linked lists, trees, and hash tables are actually all subsets of graphs; nodes connected by pointers!

Further Resources