What Will You Master in This Lesson?
By completing this lesson, you will deeply understand and be able to implement:
01 Starting with a Intuitive Problem: Highway Transit Networks
Imagine several cities connected by a road network:
Dhaka
|
Gazipur
/ \
Tangail Narsingdi
As a traveler or navigation app, you naturally ask:
- Reachability: Can a vehicle travel from Dhaka to Tangail via roads?
- Connected Nodes: Which cities are directly or indirectly reachable from Dhaka?
- Shortest Route: What is the path with minimum travel time or fuel consumption?
Notice that this is not a simple linear search or sorting problem over a list of strings. The defining characteristic here is: which entity connects to which entity, and through what relationship. To represent and compute over such interconnections, computer science uses a Graph.
02 What is a Graph?
Formal Definition:
A Graph is a mathematical and computational data structure denoted as \(G = (V, E)\), composed of a set of Vertices (or Nodes) representing distinct entities, and a set of Edges representing the pairwise relationships or connections between them.
The distinct entities being modeled: individual people, cities, computers, web pages, or airports.
The link or relationship between two vertices: friendships, roadways, fiber cables, or hyperlinked URLs.
Rahim (Vertex) —— Karim (Vertex)
|
Salim (Vertex)
Connecting lines represent Edges indicating mutual friendship relationships.
03 Directed vs. Undirected Graphs
Not all real-world relationships are symmetric. Based on directional orientation, graphs are categorized into:
Connections are bidirectional by default. If a link exists between \(A\) and \(B\), traversal is valid in both directions: \(A \longleftrightarrow B\).
Examples: Facebook friendship (requires mutual agreement), standard two-way roads.
Connections carry a specific orientation. An edge \(A \to B\) permits movement from \(A\) to \(B\), but does not guarantee or imply a reverse path.
Examples: Instagram/Twitter follow, one-way street corridors, hyperlinked web URLs.
04 Weighted Graphs: Incorporating Edge Costs
Often, knowing that a connection exists is insufficient; we must also know the cost of traversing it. When every edge has an associated numerical attribute (Distance, Latency, Toll, Risk), it is called a Weighted Graph.
A —— 10 —— B
\ /
40 25
\ /
— C —
In Google Maps, weights correspond to kilometers or minutes of traffic delay; in computer networking, weights represent ping latency (ms) or packet drop rates.
05 Graph Traversals: BFS vs. DFS
Systematically visiting every node in a graph without duplication is called Graph Traversal. Computer science provides two legendary traversal architectures:
Philosophy: Expands outward like ripples across water. Inspects all 1-hop immediate neighbors first, before progressing to 2-hop distant nodes.
Philosophy: Dives as deep as possible down a single branch. Upon reaching a dead end, it backtracks one step to explore unvisited forks.
| Dimension | BFS (Breadth-First) | DFS (Depth-First) |
|---|---|---|
| Strategy | Concentric radial ripples (Level-by-level) | Deep branch plunge followed by backtracking |
| Core Data Structure | Queue (First In, First Out) | Stack or Recursion Call Stack |
| Shortest Path (Unweighted) | ✓ Guaranteed optimal hop count | ✗ Does NOT guarantee shortest path |
| Time Complexity | \(O(V + E)\) | \(O(V + E)\) |
| Primary Use Cases | Mutual friends, nearest neighbors, web crawlers | Topological sorting, cycle detection, maze solving |
06 Why a Visited Set is Non-Negotiable: The Cycle Trap
Unlike trees, general graphs frequently contain Cycles (loops):
A → B ↑ ↓ D ← C
\(A \to B \to C \to D \to A \to B \to C \dots\) Infinite Loop!
Without tracking visited vertices, your algorithm will circulate forever, exhausting memory and blowing up the call stack. Hence, every robust graph algorithm maintains a visited = set(). Before exploring any neighboring vertex, it verifies: "Has this node been processed before? If yes, skip it."
07 Dijkstra's Algorithm: Shortest Paths on Weighted Graphs
When edges have weights (distance, latency), BFS cannot guarantee shortest paths because a path with fewer edges may have vastly greater total distance than a multi-edge shortcut (e.g., 1 direct highway edge = 50 km vs. 2 local shortcut edges = 5 km + 5 km = 10 km).
What is Edge Relaxation?
Dijkstra's engine is Edge Relaxation. Suppose your current tentative distance to node \(B\) is 10. During exploration, you uncover an alternate path \(A \to C \to B\) whose combined distance is \(4 + 3 = 7\). You immediately "relax" the edge, updating \(B\)'s tentative distance from 10 down to 7:
if dist[u] + weight(u, v) < dist[v]: dist[v] = dist[u] + weight(u, v)
Because Dijkstra commits greedily to vertices once they are popped from the Min-Priority Queue, it assumes distances can never decrease through downstream edges. If the graph contains Negative Edge Weights, Dijkstra fails. For negative weights, the Bellman-Ford Algorithm must be employed instead.
Interactive Laboratory: Graph Algorithm Simulator
Observe BFS vs. DFS traversal orders and step through Dijkstra's distance table relaxation.
08 Where Do Graph Algorithms Power Real-World Systems?
Intersections form vertices, and roads form edges. Dijkstra and A* search navigate traffic bottlenecks to compute optimal driving directions.
Who are your 2nd or 3rd-degree connections? BFS radial level-by-level sweeps power "People You May Know" recommendations.
Internet core routers continuously run Dijkstra's algorithm across network topologies to forward packets along the lowest-latency fiber routes.
Package dependencies form Directed Acyclic Graphs (DAGs). DFS-based Topological Sort ensures dependencies build before their consumers.
09 5 Diagnostic Questions to Identify Graph Problems
If entities cannot be treated in isolated independence, you are dealing with a graph problem.
Determines whether edges require symmetric bidirectional representation in adjacency structures.
Unweighted shortest path favors BFS; weighted shortest path demands Dijkstra or Bellman-Ford.
Reachability verification (DFS), closest radial expansion (BFS), or cost minimization (Dijkstra)?
Always equip your traversal with a Visited Set to avoid memory exhaustion and infinite loops.
Concept Check: Test Your Intuition
Select the correct option to verify your understanding.
1. Which algorithm is guaranteed to find the shortest path (minimum edge hops) in an unweighted graph?
2. Why is maintaining a Visited Set crucial during graph traversal?
3. Under which condition does Dijkstra's Algorithm fail to guarantee optimal shortest path results?
10 Key Takeaways: Engineering Wisdom to Remember
Whenever connections between entities determine the problem space, model the architecture as a graph.
Queue-driven BFS finds nearest layer-by-layer hops; Stack-driven DFS executes deep branch exploration.
Dijkstra provides optimal shortest paths on non-negative weighted graphs through greedy edge relaxation.
Always employ a Visited Set to protect your traversals from runaway infinite cyclic loops.
Lesson 6.10 — Common Problem-Solving Patterns
Now that we have covered core paradigms, we move from individual algorithms to versatile, reusable coding patterns: Two Pointers, Sliding Window, Prefix Sum, and Fast-Slow Pointers!