Introduction to Graphs and Traversals

Welcome to one of the most exciting topics in the Higher Level (HL) syllabus! If you've ever used Google Maps to find the shortest route home, scrolled through your "Suggested Friends" on social media, or wondered how the internet stays connected, you’ve already encountered Graphs. While other data types like arrays or linked lists are linear (like a single line of people), graphs allow us to model complex, "web-like" relationships. Don't worry if it looks messy at first—by the end of these notes, you'll see the logic behind the "chaos."

What is a Graph?

In Computer Science, a Graph is a non-linear data structure used to represent a set of objects where some pairs of objects are connected. It consists of two main components:

  • Vertices (or Nodes): These are the individual data points (like cities on a map or users on a social network).
  • Edges (or Arcs): These are the connections between the nodes (like the roads between cities or "friendships" between users).

Mathematically, we often describe a graph \(G\) as a set of vertices \(V\) and edges \(E\), written as \(G = (V, E)\).

Key Terminology

  • Adjacent: Two nodes are adjacent if there is an edge directly connecting them.
  • Path: A sequence of edges that allows you to travel from one node to another.
  • Cycle: A path that starts and ends at the same node without repeating any edges.
  • Degree: The number of edges connected to a specific node.

Quick Tip: Think of a graph like a spiderweb. The spots where the silk meets are vertices, and the silk strands themselves are the edges.

Types of Graphs

Not all graphs are created equal! Depending on the problem we are solving, we use different types:

1. Undirected vs. Directed Graphs

  • Undirected Graph: The edges have no direction. If Node A is connected to Node B, you can travel both ways. Example: A "friendship" on Facebook (it’s mutual).
  • Directed Graph (Digraph): The edges have arrows indicating a one-way relationship. Example: "Following" someone on Instagram (you follow them, but they might not follow you back).

2. Weighted vs. Unweighted Graphs

  • Unweighted Graph: All edges are treated as equal. We only care if a connection exists.
  • Weighted Graph: Each edge has a "weight" or "cost" associated with it. This could represent distance, time, or even money. Example: A map where the weights represent the number of kilometers between cities.

Key Takeaway: Choosing the right type of graph is the first step in solving a computational problem efficiently.

Representing Graphs in Code

Since computers don't "see" diagrams, we have to represent these connections using data structures we already know from the B.2 Programming and B.4 Abstract Data Types sections. There are two common ways to do this:

1. Adjacency Matrix

This is a 2D array (a table) where the rows and columns represent the nodes. If there is a connection between Node \(i\) and Node \(j\), we put a \(1\) (or the weight) in the cell at row \(i\), column \(j\). Otherwise, we put a \(0\).

  • Pros: Very fast to check if a specific edge exists between two nodes.
  • Cons: Uses a lot of memory (\(V^2\)), especially if there are many nodes but very few connections (a "sparse" graph).

2. Adjacency List

This is an array or a list where each element represents a node and contains a list of all the other nodes it is connected to. In Java or Python, this is often implemented using an array of Linked Lists or a Dictionary.

  • Pros: Much more memory-efficient for sparse graphs.
  • Cons: Slower to check if a specific edge exists, as you have to search through a list.

Graph Traversals (BFS and DFS)

A traversal is just a fancy word for visiting every node in a graph in a specific, systematic order. This is essential for searching for data or finding paths. There are two main methods you need to know:

1. Breadth-First Search (BFS) - "The Layered Approach"

BFS explores the graph layer by layer. It starts at a chosen node, visits all of its immediate neighbors first, then visits the neighbors of those neighbors, and so on.

  • Data Structure Used: BFS uses a Queue (First-In, First-Out). You can review Queues in the "Stacks and Queues" chapter of B.4.
  • Analogy: Throwing a stone into a pond and watching the ripples spread outward in circles.
  • Best for: Finding the shortest path in an unweighted graph.

2. Depth-First Search (DFS) - "The Maze Approach"

DFS goes as deep as possible down one path before backtracking to the last "fork in the road" to try a different branch.

  • Data Structure Used: DFS uses a Stack (Last-In, First-Out) or Recursion. You can review these in the "Recursion" and "Stacks" chapters.
  • Analogy: Exploring a maze by following a single wall with your hand and only turning back when you hit a dead end.
  • Best for: Checking if a path exists between two nodes or detecting cycles in a graph.

Did you know? Most GPS systems use a more advanced version of these traversals to find the fastest way to get you to your destination!

Step-by-Step: How BFS Works

  1. Pick a starting node and mark it as visited.
  2. Add the starting node to a Queue.
  3. While the Queue is not empty:
    • Remove the node at the front of the Queue.
    • For each neighbor of this node that has not been visited:
      • Mark it as visited.
      • Add it to the Queue.

Common Pitfalls to Avoid

  • Infinite Loops: Unlike Trees (which you will study in the "Trees" chapter), Graphs can have cycles. If you don't keep track of which nodes you have already visited, your traversal will run forever!
  • Choosing the wrong structure: Don't use an Adjacency Matrix if you have 10,000 nodes but only 50 connections; you'll waste a huge amount of memory.
  • Mixing up Stacks and Queues: Remember: Queue = BFS (think "QB" like a quarterback) and Stack = DFS.

Quick Review

Graphs are sets of Vertices and Edges. They can be directed (arrows) or undirected (no arrows), and weighted (costs) or unweighted (no costs). We represent them using Adjacency Matrices or Adjacency Lists. To visit every node, we use BFS (using a Queue) to explore layer-by-layer or DFS (using a Stack/Recursion) to explore deep into a branch first.