Lesson 4.1: Introduction to Graphs
Graphs are dynamic data structures used to represent relationships between entities. A graph is made of vertices (nodes) and edges (connections), and it can be either directed or undirected. These structures are extremely powerful in modeling real-world networks, such as social media relationships, road maps, flight routes, and more. Graphs are widely used in areas like AI, network routing, recommendation engines, and compilers. Understanding graphs provides the foundation for mastering advanced algorithms like Dijkstra’s, BFS, DFS, and topological sort.
🌐 Key Points
- Graphs can be directed (like Twitter follow) or undirected (like Facebook friends).
- Edges may carry weights (distance, cost, time) or be unweighted.
- Represented via adjacency list or matrix.
- Used in shortest path problems (Dijkstra, Bellman-Ford).
- Helps detect cycles, connectivity, and strongly connected components.
- Useful in scheduling (via topological sort).
- Applied in search algorithms like DFS and BFS.
🧪 Examples
// Example 1: Adjacency List in C++
vector> graph(n);
graph[0].push_back(1);
graph[1].push_back(2);
# Example 2: Graph using dict in Python
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['E'],
'D': [],
'E': []
}
Lesson 4.2: BFS & DFS
Breadth-First Search (BFS) and Depth-First Search (DFS) are two fundamental graph traversal algorithms. BFS explores the nearest nodes level by level using a queue, while DFS dives deep into one path before backtracking, using a stack or recursion. BFS is excellent for shortest path discovery in unweighted graphs, whereas DFS excels in cycle detection, pathfinding, and solving puzzles like mazes or sudoku.
🧠 Key Points
- BFS uses a queue and explores in layers.
- DFS uses a stack or recursion to explore depth-wise.
- BFS is ideal for shortest path in unweighted graphs.
- DFS is useful for cycle detection and topological sorting.
- Both can be used on trees and graphs (directed/undirected).
- DFS is used in maze solvers and puzzle algorithms.
- BFS is used in social network analysis (e.g., friend recommendations).
🧪 Examples
# Example 1: BFS in Python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
queue.extend(graph[node])
# Example 2: DFS in Python
def dfs(graph, node, visited):
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
Lesson 4.3: Weighted Graphs & Dijkstra's Algorithm
Weighted graphs associate weights with edges to represent costs like distance or time. Dijkstra’s Algorithm is a popular method to find the shortest path from a source to all other nodes in such graphs. It uses a priority queue (min-heap) to always explore the least-cost path first. It’s widely used in navigation apps (like Google Maps), network routing, and logistics planning.
🔍 Key Points
- Edge weights represent cost (distance, time, etc.).
- Dijkstra uses a priority queue to get the minimum distance node.
- Only works on graphs with non-negative weights.
- Time complexity is O(E + V log V) using a min-heap.
- Used in GPS, airline routing, and telecom networks.
- Frequently applied in real-time systems for route optimization.
- Foundational for advanced algorithms like A*.
🧪 Examples
// Example 1: Priority Queue Initialization in C++
priority_queue
, vector>, greater>> pq;# Example 2: Dijkstra Algorithm Step (Python)
import heapq
heap = [(0, start)]
dist = {start: 0}
while heap:
cost, u = heapq.heappop(heap)
for v, weight in graph[u]:
if dist.get(v, float('inf')) > cost + weight:
dist[v] = cost + weight
heapq.heappush(heap, (dist[v], v))