🧠 Advanced Algorithms: Graph Algorithms (9645)
Hello! Welcome to one of the most powerful and exciting topics in Computer Science: Graph Algorithms. Graphs aren't just bar charts—they are fundamental data structures that model complex relationships in the real world, from social networks to mapping the Internet.
Mastering these algorithms means you can find the quickest route home, solve puzzles, and understand how modern software navigates interconnected data. Don't worry if this seems tricky; we will break down each concept step-by-step, using clear analogies to help it stick!
1. Graph Fundamentals: Defining the Structure
Before we run algorithms on a graph, we need to know what a graph actually is and how it’s built.
1.1 Core Terminology (3.10.1)
A graph is a data structure used to represent complex relationships between pieces of data.
- Vertex or Node: This represents an entity or a point in the relationship. (Think of a city on a map or a person on a social network.)
- Edge or Arc: This represents the connection or relationship between two vertices. (Think of a road connecting two cities.)
Types of Graphs
The type of algorithm we use often depends on the type of graph we are dealing with:
- Undirected Graph: Edges have no direction. If Node A is connected to Node B, that connection works both ways. (A two-way street.)
- Directed Graph: Edges have a specific direction (arcs). The relationship only goes one way. (A one-way street, or a Twitter follow where I follow you, but you don't necessarily follow me back.)
- Weighted Graph: Each edge has a numerical value (a "weight") associated with it. This value usually represents cost, distance, or time. (The length of the road, or the cost of a flight.)
Quick Review: Graph algorithms are usually focused on either finding a path between nodes or systematically visiting all nodes.
1.2 Representing Graphs in Code (3.10.1)
In memory, graphs are typically stored using two main structures:
a) Adjacency Matrix
This uses a 2D array (a matrix) where rows and columns represent nodes. If an edge exists between node \(i\) and node \(j\), the cell at \([i][j]\) is marked (often with 1 for unweighted, or the weight value for weighted).
- Pros (When to use a Matrix):
- Easy to test if an edge exists (check if \([i][j] = 1\)). This is known as checking frequently for the presence/absence of edges.
- Easy to add/remove edges quickly.
- Best for Dense Graphs (graphs with many edges relative to the number of vertices).
- Cons: Wastes memory for Sparse Graphs (graphs with few edges) as most of the matrix entries will be zero.
b) Adjacency List
This uses a list or array where each index represents a node. At each index, there is a linked list (or array/list) containing the neighbours of that node.
- Pros (When to use a List):
- More efficient memory use for Sparse Graphs because you only store existing connections.
- Faster to find all neighbours of a specific node.
- Cons: Checking if a single specific edge exists (A to B) requires iterating through A’s entire neighbour list, which can be slower than a direct matrix lookup.
Key Takeaway for Section 1: A graph connects nodes (vertices) via edges (arcs). We use Adjacency Matrices for quick edge checking and dense graphs, and Adjacency Lists for memory efficiency in sparse graphs.
2. Search Algorithms: Breadth-First Search (BFS) (3.11.1)
Search algorithms are used to explore a graph systematically. BFS is like throwing a stone into a pond—the ripples expand outwards layer by layer.
2.1 What is Breadth-First Search (BFS)?
BFS explores a graph level by level, or breadth-wise. It finds all the neighbours of the starting node, then all their neighbours, and so on, before moving deeper into the graph.
Memory Aid: Breadth-First uses a Broad approach and uses a Queue (FIFO).
Core Data Structure: BFS uses a Queue (First-In, First-Out) to manage which nodes to visit next. This ensures that nodes closer to the start are visited first.
2.2 Tracing the BFS Algorithm (Step-by-Step)
- Start at a designated Start Node. Mark it as visited and add it to the Queue.
- While the Queue is not empty:
a. Dequeue (remove) the first node, call it the Current Node.
b. Examine all the unvisited neighbours of the Current Node.
c. For each unvisited neighbour, mark it as visited and Enqueue (add) it to the Queue. - Repeat until the Queue is empty.
Did you know? Because BFS systematically checks all nodes at distance \(d\) before moving to distance \(d+1\), it inherently finds the shortest path in an unweighted graph. This is the primary application you need to know!
2.3 Application of BFS (3.11.1)
The typical application of BFS is finding the shortest path for an unweighted graph. Since all edges have the same 'weight' (1 unit), the algorithm guarantees that the first time you reach a destination node, it is via the fewest possible number of edges.
Example: Finding the minimum number of connections between two people on a social network.
Key Takeaway for BFS: BFS uses a Queue, explores level by level, and is perfect for finding the shortest path in unweighted graphs.
3. Search Algorithms: Depth-First Search (DFS) (3.11.1)
DFS is the graph explorer that commits to a single path, going as deep as possible before backtracking.
3.1 What is Depth-First Search (DFS)?
DFS explores along a single branch or path in the graph until it hits a dead end (a node with no unvisited neighbours). It then "backtracks" to the last junction and tries a new path.
Analogy: Exploring a maze. You keep going down one passage until you hit a wall, then you return to the last corner and try the next passage.
Core Data Structure: DFS uses a Stack (Last-In, First-Out) or Recursion (which uses the call stack) to manage which path to return to for backtracking.
3.2 Tracing the DFS Algorithm (Step-by-Step)
- Start at a designated Start Node. Mark it as visited and process it.
- If the Current Node has unvisited neighbours:
a. Choose one unvisited neighbour, make it the new Current Node. (Effectively a recursive call or a push onto the stack). - If the Current Node has no unvisited neighbours (a dead end):
a. Backtrack (return) to the previous node and try any remaining unvisited neighbours from that point. - Repeat until all reachable nodes have been visited.
Implementation: You must be able to implement both BFS and DFS in program code. In an exam scenario, DFS is often easiest to implement using a recursive subroutine.
3.3 Application of DFS (3.11.1)
The typical application of DFS is navigating a maze or puzzle solving where you need to explore one option fully before abandoning it.
Example: Determining if a path exists between two points, or topological sorting (ordering tasks based on dependencies).
Key Takeaway for DFS: DFS uses a Stack (or Recursion), explores deep into one path before backtracking, and is useful for maze navigation and path existence checks.
4. Shortest Path Algorithm: Dijkstra's Algorithm (3.11.1)
BFS works great for unweighted graphs. But what if the roads have different distances or costs? We need Dijkstra's algorithm.
4.1 Purpose of Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path between a starting node and all other nodes in a weighted graph, provided the edge weights are non-negative (you cannot have negative distance or negative time).
Analogy: This is exactly what your GPS does when calculating the fastest route between two points—it accounts for the weight (distance/time) of every road (edge).
4.2 Tracing the Algorithm (Focus on Understanding)
While you are not expected to recall the full steps or write code for Dijkstra's unless the steps are provided in the question, you must be able to trace it.
The core idea of tracing involves maintaining two key sets of data:
- Distances: A list recording the shortest known distance from the starting node to every other node. Initially, the starting node distance is 0, and all others are set to infinity (\(\infty\)).
- Visited Set: The set of nodes for which the final shortest distance from the source has been determined.
The Tracing Process (Simplified)
- Initialise the distance list (Start = 0, Others = \(\infty\)).
- Select the unvisited node with the smallest current distance (this will be the Start Node first).
- Mark the selected node as visited (its shortest path is now final).
- For all neighbours of the visited node, calculate the tentative distance (Current Node Distance + Edge Weight).
- If this tentative distance is smaller than the currently recorded distance for that neighbour, update the distance to the smaller value. (This process is called relaxation).
- Repeat steps 2-5 until the destination node is visited, or all reachable nodes are in the visited set.
Common Mistake to Avoid: Dijkstra's only works correctly if the weights are non-negative. If weights can be negative, other algorithms (like Bellman-Ford) are required, but these are outside the scope of this syllabus.
4.3 Applications of Shortest Path Algorithms (3.11.1)
Any problem where you need to minimise cost, distance, or time on a map or network:
- Network routing (how data packets travel across the internet efficiently).
- Geographic Information Systems (GIS) and navigation apps (like Google Maps).
- Scheduling and logistics (finding the quickest sequence of deliveries).
Key Takeaway for Dijkstra: Dijkstra's finds the shortest path in a weighted graph with non-negative edges by constantly updating and confirming the shortest known distance to each node (tracing is the key skill here).
💡 Summary Table of Advanced Algorithms (3.11.1)
| Algorithm | Type | Core Data Structure | Primary Application |
|---|---|---|---|
| BFS | Search (Breadth-wise) | Queue (FIFO) | Shortest path in unweighted graphs. |
| DFS | Search (Depth-wise) | Stack / Recursion (LIFO) | Navigating a maze or checking connectivity. |
| Dijkstra's | Shortest Path | Priority Queue (Implied, or handled iteratively) | Shortest path in weighted graphs (non-negative weights). |