Welcome to the World of Graphs!
In this chapter, we are going to explore Graphs. While you might think of bar charts or line graphs from Maths, in Computer Science, a graph is a way of showing how different things are connected.
Think about Facebook: you are a "point," and your friendships are the "lines" connecting you to others. Or think about Google Maps: cities are the points, and the roads are the lines. Graphs are everywhere! Don't worry if this seems a bit abstract at first; we will break it down piece by piece.
1. The Basics: What is a Graph?
A graph is a mathematical structure used to represent complex relationships between pairs of objects. It consists of two main parts:
• Vertex (or Node): These are the "objects" or "points" in the graph (like a person or a city).
• Edge (or Arc): these are the "lines" that connect the vertices together (like a friendship or a road).
Directed vs. Undirected Graphs
Imagine a relationship between two nodes, A and B.
Undirected Graph: The edges have no direction. If there is an edge between A and B, you can go both ways.
Analogy: A two-way street or a Facebook friendship (you are both friends with each other).
Directed Graph: The edges have a specific direction, shown by an arrow. You can only move in the direction the arrow points.
Analogy: A one-way street or a Twitter "Follow" (you might follow a celebrity, but they don't necessarily follow you back!).
Weighted Graphs
Sometimes, the connection between nodes has a "cost" or "value" attached to it. This is called a weighted graph. The "weight" could represent distance, time, or even the price of a flight between two cities.
Quick Review Box:
• Vertex: A point.
• Edge: A connection.
• Weighted: The connection has a value (e.g., 5 miles).
• Directed: The connection is one-way.
Key Takeaway: Graphs are just collections of nodes and the connections between them. They help us model everything from the internet to chemical molecules!
2. How Computers Store Graphs
Since a computer can't just "see" a drawing of a graph, we need a way to turn it into data. There are two main ways to do this:
Method A: The Adjacency Matrix
This is a 2D array (a grid). Both the rows and columns represent the vertices. If there is a connection between two nodes, we put a 1 in the grid; otherwise, we put a 0. For weighted graphs, we store the weight instead of a 1.
Example Matrix for a graph with 3 nodes (A, B, C):
\( \begin{matrix} & A & B & C \\ A & 0 & 1 & 0 \\ B & 1 & 0 & 1 \\ C & 0 & 1 & 0 \end{matrix} \)
Method B: The Adjacency List
This is like an address book. For every node, we keep a list of all the other nodes it is directly connected to.
Example:
A: [B]
B: [A, C]
C: [B]
Which one is better?
• Adjacency Matrix: Great for "dense" graphs (where almost everything is connected). It's very fast to check "Is A connected to B?", but it wastes a lot of memory storing zeros if there aren't many connections.
• Adjacency List: Best for "sparse" graphs (where most nodes aren't connected). It saves memory because it only stores the connections that actually exist.
Did you know? Most real-world graphs, like the World Wide Web, are "sparse." Most websites only link to a tiny fraction of all the other websites in existence!
Key Takeaway: Use a Matrix for lots of connections (speed) and a List for fewer connections (saving space).
3. Graph Traversal: Exploring the Connections
Traversal means "visiting every node in the graph." There are two main ways to do this, and they work differently depending on your goal.
Depth-First Search (DFS)
In DFS, you go as far as you can down one path before back-tracking to find a new one.
Memory Aid: Think of "Depth" as "Deep." You dive deep into the graph.
• Analogy: Exploring a maze by following one path until you hit a dead end.
• Data Structure: It uses a Stack (Last-In, First-Out).
• Common Use: Navigating a maze or checking if a path exists between two points.
Breadth-First Search (BFS)
In BFS, you visit all the immediate neighbors of your starting node first, then all of their neighbors, and so on.
Memory Aid: Think of "Breadth" as "Wide." You spread out wide across the graph.
• Analogy: Throwing a stone into a pond and watching the ripples spread out in circles.
• Data Structure: It uses a Queue (First-In, First-Out).
• Common Use: Finding the shortest path in an unweighted graph (e.g., the fewest number of "jumps" between you and a stranger on LinkedIn).
Quick Review Box:
• DFS: Uses a Stack, goes deep, good for mazes.
• BFS: Uses a Queue, goes wide, finds the shortest path (unweighted).
4. Dijkstra’s Shortest Path Algorithm
While BFS finds the shortest path in terms of the number of "jumps," Dijkstra’s Algorithm finds the shortest path when the edges have weights (like miles or minutes).
How it works (The Concept):
1. Start at your source node and set its distance to 0. Set all other nodes to "Infinity."
2. Look at all unvisited neighbors of the current node.
3. Calculate the distance to each neighbor: (Distance to current node + weight of the edge).
4. If this new distance is smaller than the distance currently stored for that neighbor, update it!
5. Mark the current node as "visited." You will never visit it again.
6. Move to the unvisited node with the smallest distance and repeat until all nodes are visited.
Common Mistake: Students often forget to update the distance if a shorter path is found later. Always check if the new calculated path is "cheaper" than the old one!
Real-World Example: This is exactly how your SatNav or Google Maps calculates the fastest route home. It treats every junction as a node and every road as a weighted edge.
Key Takeaway: Dijkstra's is the "Gold Standard" for finding the shortest route in a weighted graph. It's an optimisation algorithm.
5. Summary Checklist
Before you finish this chapter, make sure you can:
• Define Vertex and Edge.
• Explain the difference between Directed and Undirected graphs.
• Draw an Adjacency Matrix and an Adjacency List for a simple graph.
• Describe how DFS and BFS explore a graph and which data structures they use.
• Explain the purpose of Dijkstra's Algorithm and identify it as a shortest-path tool for weighted graphs.
Keep practicing drawing these out by hand—once you can draw the grid and the list, the logic of the algorithms becomes much easier to visualize!