7-Day Graphs Learning Guide for DSA Interviews
(Python)
Day 1: Graph Terminology & Representation
• Graph basics: A graph is a non-linear data structure of nodes (vertices) and edges (connections)
representing relationships 1 . For example, imagine a map: each city is a vertex and each road is an
edge 1 .
• Graph types: Edges may be directed (one-way) or undirected (two-way) 2 . A directed graph has
ordered edges (like one-way streets), while an undirected graph has bidirectional edges (two-way
streets) 2 . Edges can also be weighted (carry a cost, distance, etc.) or unweighted (all edges
equal) 3 . In a weighted graph (e.g., road network with travel times) each edge has a numeric
weight 4 ; in an unweighted graph edges just indicate connection 5 .
• Representations: Graphs are commonly stored via an adjacency list or adjacency matrix 6 7 . In
an adjacency list, each vertex has a list of its neighbors (memory-efficient for sparse graphs) 7 . In
an adjacency matrix, we use an N×N grid where matrix[i][j] = 1 (or a weight) if there’s an
edge from i to j , else 0 6 .
• Real-world analogy: A social network (friendships) is an undirected graph (mutual connections),
whereas Twitter follow relationships form a directed graph (A follows B doesn’t imply B follows A).
Road networks often use weights (e.g. distances) on edges, so they are weighted graphs.
• Python example: Below is a simple graph in both list and matrix form.
# Adjacency list: neighbors for each vertex
graph_list = {
0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2]
}
# Adjacency matrix: 1 = edge present, 0 = no edge
graph_matrix = [
[0, 1, 1, 0], # vertex 0 connected to 1, 2
[1, 0, 0, 1], # vertex 1 connected to 0, 3
[1, 0, 0, 1], # vertex 2 connected to 0, 3
[0, 1, 1, 0] # vertex 3 connected to 1, 2
]
1
Day 2: Graph Traversal – BFS and DFS
• Breadth-First Search (BFS): BFS explores a graph level by level using a queue 8 9 . Starting from
a source node, it visits all immediate neighbors before going deeper. This guarantees the shortest
path (fewest edges) in an unweighted graph. We mark nodes as visited to avoid repeats. (BFS is used
in many algorithms like shortest paths in unweighted graphs 10 .)
• Depth-First Search (DFS): DFS dives as deep as possible along each branch before backtracking 11 .
It can be implemented recursively (implicit stack) or with an explicit stack. DFS marks nodes visited to
avoid re-visiting. DFS is good for exploring all paths and is used in algorithms like topological sort,
cycle detection, etc.
• Key patterns: In both BFS and DFS, use a visited set (or array) to track seen nodes. BFS uses a
queue ( [Link] in Python); DFS uses recursion or a stack. These are essential
interview patterns for graph problems 12 8 .
• Code examples:
from collections import deque
def bfs(graph, start):
visited, order = set([start]), []
queue = deque([start])
while queue:
u = [Link]()
[Link](u)
for v in graph[u]:
if v not in visited:
[Link](v)
[Link](v)
return order
def dfs_recursive(graph, u, visited=None):
if visited is None:
visited = set()
[Link](u)
for v in graph[u]:
if v not in visited:
dfs_recursive(graph, v, visited)
return visited
def dfs_iterative(graph, start):
visited, order = set(), []
stack = [start]
while stack:
u = [Link]()
if u not in visited:
[Link](u)
[Link](u)
for v in graph[u]:
2
if v not in visited:
[Link](v)
return order
• Real-world analogy: Think of BFS like ripples expanding outward (explore neighbors first), and DFS
like walking through a maze: you go as far as you can down one path (stack/recursion) before
backtracking.
Day 3: Cycle Detection (Directed & Undirected)
• Cycle definition: A cycle is a path that starts and ends at the same vertex without reusing edges.
Detecting cycles is common in interview problems (e.g., deadlocks, scheduling).
• Directed graphs: Use DFS with two markers: one for nodes “visited” at all, and one for nodes in the
current recursion stack 13 . During DFS, if you reach a neighbor that’s already in the recursion stack,
a cycle exists 13 . We then backtrack and remove nodes from the recursion stack.
• Undirected graphs: Also use DFS, but track the parent of each node 14 . If we encounter a visited
neighbor that is not the parent, it indicates a cycle 14 (because in an undirected graph each edge is
two-way, and the parent check avoids the trivial back-edge to where we came from).
• Code examples:
# Directed graph cycle check
def has_cycle_directed(graph):
visited, rec_stack = set(), set()
def dfs(u):
[Link](u)
rec_stack.add(u)
for v in [Link](u, []):
if v not in visited:
if dfs(v):
return True
elif v in rec_stack:
return True
rec_stack.remove(u)
return False
for node in graph:
if node not in visited:
if dfs(node):
return True
return False
# Undirected graph cycle check
def has_cycle_undirected(graph):
visited = set()
def dfs(u, parent):
[Link](u)
for v in [Link](u, []):
if v not in visited:
3
if dfs(v, u):
return True
elif v != parent:
return True
return False
for node in graph:
if node not in visited:
if dfs(node, None):
return True
return False
• Key insight: For directed graphs, use a recursion stack; for undirected, check visited neighbors
against parent 13 14 . This pattern (visited set + parent or recursion-stack) is frequently asked in
interviews.
Day 4: Topological Sorting (Kahn’s Algorithm & DFS)
• Definition: A topological sort of a directed acyclic graph (DAG) is a linear ordering of vertices such
that for every edge u → v, u comes before v in the order 15 . Think of scheduling tasks with
dependencies – prerequisites must come earlier.
• Kahn’s algorithm (BFS-based): Compute the in-degree (count of incoming edges) for each vertex.
Start with all vertices of in-degree 0 in a queue 16 . Repeatedly pop from the queue, append to the
topo order, and decrement the in-degree of its neighbors. If any neighbor’s in-degree becomes 0,
add it to the queue. Continue until done 16 . This yields one valid topological ordering.
• DFS-based approach: Perform DFS from each unvisited node. After visiting all neighbors of a node
recursively, push the node onto a stack. Once all nodes are processed, popping from the stack gives a
topological order 17 . In essence, we add a node to the order after its dependencies, ensuring
prerequisites come first 17 .
• Code examples:
from collections import deque
# Kahn's algorithm (BFS approach)
def topo_kahn(graph):
indegree = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
indegree[v] = [Link](v, 0) + 1
queue = deque([u for u in graph if indegree[u] == 0])
topo_order = []
while queue:
u = [Link]()
topo_order.append(u)
for v in [Link](u, []):
indegree[v] -= 1
if indegree[v] == 0:
[Link](v)
4
return topo_order
# DFS-based topological sort
def topo_dfs(graph):
visited = set()
stack = []
def dfs(u):
[Link](u)
for v in [Link](u, []):
if v not in visited:
dfs(v)
[Link](u) # push after visiting neighbors
for u in graph:
if u not in visited:
dfs(u)
return stack[::-1] # reverse the stack to get order
• Analogy: Topological sort is like ordering courses by prerequisites: you can only take course v after
all courses u that point to v have been taken 15 17 . Both Kahn’s (in-degree queue) and DFS (stack)
are common interview patterns for DAGs.
Day 5: Connected Components & Bipartite Check
• Connected components (undirected): A connected component is a set of nodes where each node is
reachable from any other in that set. To find all components, run a BFS/DFS from each unvisited
node – each full search gives one component 18 . For example, in a social graph, each community of
friends is a component.
• Finding components: Initialize all nodes as unvisited. Loop through nodes; if a node is unvisited,
start a DFS/BFS from it, marking all reachable nodes. Those marked in that search form one
component. Repeat until all nodes are visited 18 .
• Bipartite graph check: A graph is bipartite if its vertices can be divided into two groups with no
edges inside a group (i.e., edges only between the groups) 19 . Equivalently, it’s 2-colorable with no
adjacent same colors. A common method is BFS (or DFS) coloring: start at any uncolored node,
assign it color 0, then assign alternating colors to neighbors. If you ever find a neighbor already
colored the same, the graph is not bipartite 20 . Repeat for all components to handle disconnected
graphs.
• Code examples:
# Connected components via DFS
def connected_components(graph):
visited = set()
components = []
def dfs(u, comp):
[Link](u)
[Link](u)
for v in [Link](u, []):
if v not in visited:
5
dfs(v, comp)
for u in graph:
if u not in visited:
comp = []
dfs(u, comp)
[Link](comp)
return components
# Bipartite check via BFS coloring
def is_bipartite(graph):
color = {}
from collections import deque
for start in graph:
if start not in color:
color[start] = 0
queue = deque([start])
while queue:
u = [Link]()
for v in [Link](u, []):
if v not in color:
color[v] = 1 - color[u] # assign opposite color
[Link](v)
elif color[v] == color[u]:
return False
return True
• Real-world analogy: Think of connected components like islands: each island (component) is
internally connected, but no bridge connects different islands. A bipartite graph is like seating men
and women alternately at a table so no two same-gender neighbors sit together.
Day 6: Dijkstra’s Algorithm (Shortest Paths)
• Purpose: Dijkstra’s algorithm finds the shortest path distances from a single source to all other
vertices in a weighted graph (no negative weights) 21 . It’s essential for interview prep on weighted
graph problems.
• Approach: Maintain a dist map of best-known distances (initialized to ∞, except source = 0). Use
a min-heap (priority queue) to always pick the vertex with the smallest current distance 22 . Pop the
top (smallest dist) from the heap; if it’s outdated (greater than recorded dist), skip. Otherwise, for
each neighbor, see if going through the current node gives a shorter path. If yes, update
dist[neighbor] and push (new_dist, neighbor) into the heap. Continue until the heap is
empty 22 23 . The final dist array has the shortest distances.
• Code example:
import heapq
def dijkstra(graph, src):
6
# graph: dict u -> list of (v, weight)
dist = {u: float('inf') for u in graph}
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = [Link](heap)
if d > dist[u]:
continue
for v, w in graph[u]:
nd = dist[u] + w
if nd < dist[v]:
dist[v] = nd
[Link](heap, (nd, v))
return dist
• Key points: Dijkstra always “visits” the closest unvisited vertex next 22 , ensuring optimality. Using a
priority queue (heap) is crucial for efficiency (O(E log V) time). This pattern (heap + distance updates)
is commonly expected in coding interviews for shortest-path problems.
Day 7: Minimum Spanning Tree (Prim’s & Kruskal’s)
• MST definition: A Minimum Spanning Tree (MST) of a weighted undirected graph connects all vertices
with the minimum total edge weight and no cycles 24 . Algorithms like Prim’s and Kruskal’s are
classic.
• Prim’s algorithm: Start from any vertex and grow the MST one edge at a time 25 . Maintain two
sets: the set inMST of vertices already included, and the rest. Always pick the smallest-weight edge
that crosses from inMST to a vertex outside it 25 . Using a min-heap of candidate edges is effective.
This continues until all vertices are included. Prim’s is like Dijkstra’s but for tree-building.
• Kruskal’s algorithm: Sort all edges by weight and iterate from smallest to largest 26 . For each
edge, if its endpoints are in different components (checked by a Union-Find structure), add it to the
MST and union the sets. Otherwise, skip it (it would form a cycle) 26 . Continue until you have V–1
edges. Kruskal’s makes locally optimal choices by always adding the next-lightest edge that doesn’t
create a cycle.
• Code examples:
import heapq
def prim(graph):
# graph: dict u -> list of (v, weight)
start = next(iter(graph))
visited = {start}
edges = [(w, start, v) for v, w in graph[start]]
[Link](edges)
mst_weight = 0
while edges:
w, u, v = [Link](edges)
if v not in visited:
7
[Link](v)
mst_weight += w
for x, w2 in graph[v]:
if x not in visited:
[Link](edges, (w2, v, x))
return mst_weight
def kruskal(nodes, edges):
# edges: list of (u, v, weight)
parent = {x: x for x in nodes}
rank = {x: 0 for x in nodes}
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
rx, ry = find(x), find(y)
if rx != ry:
if rank[rx] < rank[ry]:
parent[rx] = ry
elif rank[rx] > rank[ry]:
parent[ry] = rx
else:
parent[ry] = rx
rank[rx] += 1
mst_weight = 0
for u, v, w in sorted(edges, key=lambda e: e[2]):
if find(u) != find(v):
union(u, v)
mst_weight += w
return mst_weight
• Key insight: Prim’s adds closest edges from the growing tree 25 ; Kruskal’s adds globally smallest
edges without forming a cycle 26 . Both are greedy and commonly asked in interviews. Use a visited
set/heap for Prim’s, and Union-Find (disjoint set) for Kruskal’s to efficiently detect cycles 26 25 .
Sources: Authoritative references on graph fundamentals and algorithms 1 8 12 13 16 17 18 20
22 25 26 .
1 2 3 4 5 6 7 9 11 12 Introduction to Graph Data Structure - GeeksforGeeks
[Link]
8 10 Breadth First Search or BFS for a Graph in Python - GeeksforGeeks
[Link]
8
13 Detect Cycle in a Directed Graph - GeeksforGeeks
[Link]
14 Detect cycle in an undirected graph - GeeksforGeeks
[Link]
15 16 Topological Sorting using BFS - Kahn's Algorithm - GeeksforGeeks
[Link]
17 Topological sort using DFS - GeeksforGeeks
[Link]
18 Connected Components in an Undirected Graph - GeeksforGeeks
[Link]
19 20 Check whether a given graph is Bipartite or not - GeeksforGeeks
[Link]
21 22 23 Dijkstra's Algorithm - GeeksforGeeks
[Link]
24 26 Kruskal’s Minimum Spanning Tree (MST) Algorithm - GeeksforGeeks
[Link]
25 Prim’s Algorithm for Minimum Spanning Tree (MST) - GeeksforGeeks
[Link]