Graphs

Hello! Today, let’s delve into one of the most important data structures, especially for an Advent of Code: graphs.

A graph is a collection of vertices (also called nodes) and edges (also called links). An edge connects two vertices together.

Characteristics

Each graph has different characteristics, including:

• Directed vs. undirected:

  • Directed: Directed edges have a direction, meaning from one vertex to another (think about Twitter, where Alice follows Bob¹).

    

  • Undirected: Undirected edges do not have a direction (think about Facebook, where Alice and Bob are mutual friends).

    

• Cyclic vs. acyclic:

  • Cyclic: A graph is cyclic if we can start at a vertex, traverse edges, and return to the same vertex. Here, a cycle goes through A, C, D, and B.

    

  • Acyclic: A graph without cycles.

    

• Weighted vs. unweighted:

  • Weighted: Each edge has an associated weight (like the time to travel between cities).

    

  • Unweighted: All edges have an equal weight (like a social network friends graph where all friendships have the same value).

    

• Connected vs. disconnected:

  • Connected: There’s a path between every pair of vertices (think about a network where every machine can communicate with every other machine).

    

  • Disconnected: Some vertices cannot be reached from others (think about a network partition with machines that are unreachable).

    

Graph Representation

There are two common ways to represent a graph in memory². To illustrate them, we will take the following directed graph as an example:

• Adjacency matrix: A two-dimensional array of booleans (integers if weighted graph) with a[i][j] being true if there is an edge from node i to node j.

  

  • Searching an edge time complexity: O(1).

  • Space complexity: O(v²) with v the number of vertices.

  • Potential problems:

    • If the graph is undirected, half of the space is useless

    • If the graph is sparse (with few edges), most of the space will be useless.

• Adjacency list: A map with the values being a linked list representing all the edges for each vertex.

  

  • Searching an edge time complexity: O(d) with d the degree³ of a vertex.

  • Space complexity: O(v + e) with v the number of vertices and e the number of edges.

  • Potential problems:

    • If the graph is dense (with many edges), finding an edge will become significantly slower than with an adjacency matrix.

Common Algorithms

We won’t delve into all the graph algorithms in this very issue. Yet, let’s briefly discuss a few important graph algorithms⁴.

Note that some algorithms only work if a graph has some specific characteristics. This is another reason for understanding the importance of graph characteristics.

• Breadth-First Search (BFS): The BFS has many use cases, but its main use case is to find the shortest path in an unweighted graph.

• Floyd–Warshall: Used to find the shortest path between all pairs of vertices and is particularly useful for weighted graphs.

• Topological sort: Sort the vertices in a Directed Acyclic Graph (DAG), which we will explore tomorrow.

Graphs are everywhere. From social networks to maps and even in biology, graphs provide a powerful way to represent and analyze relationships between objects. Make sure to be comfortable with graphs—they are foundational for solving real-world problems.

---

Tomorrow, we will explore the topological sort algorithm.

1. Bob doesn’t necessarily follow Alice in return.

2. Other representations and variations of the two discussed here exist.

3. The number of edges connected to a vertex.

4. You will likely have to use them in the current edition of the Advent of Code, if you participate.