MediumVery High Frequency20 min
Graph Fundamentals
Adjacency list vs matrix, directed vs undirected, weighted graphs, and recognition.
Graph = nodes + edges. Represent as adjacency list. Master DFS and BFS. Track visited to avoid cycles. Identify directed vs undirected, weighted vs unweighted.
Graphs — Vertices and Edges
Graph Operations
Operation
Time
Note
Build adjacency list
O(V+E)
One pass through edges list
BFS traversal
O(V+E)
Queue-based, visits by distance
DFS traversal
O(V+E)
Stack/recursion, visits by depth
Detect cycle (undirected)
O(V+E)
DFS — back edge = cycle
Shortest path (unweighted)
O(V+E)
BFS guarantees shortest path
Shortest path (weighted)
O((V+E) log V)
Dijkstra's with min-heap
See the Graph Structure
Undirected Graph Example1 / 8
Start node
Start BFS at A
Initialize the queue with A. BFS expands level by level from this source.
BFS / DFS Code
Graph BFS
O(V+E)Use BFS for shortest path in unweighted graphsStep-by-step1 / 5
Graphnodes + edges
0: start12345
Start at node 0
Enqueue 0. visited={0}.