Graphs
Model relationships and connections
Understanding Graphs
Graphs consist of vertices (nodes) connected by edges. They model relationships in social networks, maps, dependencies, and more. The two fundamental traversal algorithms are BFS (breadth-first) and DFS (depth-first).
BFS (Breadth-First)
- • Uses a queue (FIFO)
- • Explores level by level
- • Finds shortest path (unweighted)
- • Good for nearby neighbors
DFS (Depth-First)
- • Uses a stack/recursion (LIFO)
- • Explores as deep as possible
- • Detects cycles, topological sort
- • Good for exploring all paths
Graph Visualization
Start
Current
Visited
Start Node
Run Traversal
Adjacency List
A:[B, C]
B:[A, D]
C:[A, D]
D:[B, C, E]
E:[D]
Complexity Analysis
| Algorithm | Time | Space | Best For |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Shortest path, level-order |
| DFS | O(V + E) | O(V) | Cycle detection, topological sort |
V = vertices (nodes), E = edges. Both traversals visit each vertex and edge once.