Graphs Questions Placement
Graphs Questions for Placement 2026 (with Solutions)
Last Updated: March 2026
Overview
Graphs are one of the most important data structures in computer science and a favorite topic in technical interviews at FAANG and top MNCs. A graph consists of vertices (nodes) connected by edges, representing relationships between objects. Understanding graph algorithms is crucial for solving network routing, social network analysis, dependency resolution, and many real-world problems.
Companies Focused on Graphs
- Google: Heavy focus on graph traversal, shortest path, and system design using graphs
- Meta (Facebook): Social network graphs, friend recommendations
- Amazon: Delivery route optimization, network topology
- Microsoft: Dependency graphs, file system navigation
- Netflix: Content recommendation systems
- Uber: Route optimization, driver-rider matching
Core Concepts
1. Graph Representation
Adjacency Matrix:
A B C D
A [ 0 1 1 0 ]
B [ 1 0 1 1 ]
C [ 1 1 0 1 ]
D [ 0 1 1 0 ]
Adjacency List:
A -> [B, C]
B -> [A, C, D]
C -> [A, B, D]
D -> [B, C]
2. Graph Traversal Algorithms
Breadth-First Search (BFS):
- Explores vertices level by level
- Uses a queue data structure
- Time Complexity: O(V + E)
- Space Complexity: O(V)
Depth-First Search (DFS):
- Explores as far as possible along each branch
- Uses recursion or stack
- Time Complexity: O(V + E)
- Space Complexity: O(V)
3. Shortest Path Algorithms
Dijkstra's Algorithm:
- Single-source shortest path
- Works on weighted graphs with non-negative weights
- Time Complexity: O((V + E) log V) with min-heap
Bellman-Ford Algorithm:
- Handles negative weights
- Time Complexity: O(V × E)
Floyd-Warshall Algorithm:
- All-pairs shortest path
- Time Complexity: O(V³)
4. Cycle Detection
- Undirected Graph: Union-Find or DFS
- Directed Graph: DFS with recursion stack tracking
5. Topological Sort
- Linear ordering of vertices such that for every edge (u, v), u comes before v
- Only applicable to Directed Acyclic Graphs (DAG)
- Applications: Task scheduling, course prerequisites
20 Frequently Asked Coding Questions
Question 1: BFS Traversal of Graph
Problem: Given a directed graph, perform Breadth First Traversal starting from vertex 0.
from collections import deque
class Solution:
def bfsOfGraph(self, V, adj):
"""
V: number of vertices
adj: adjacency list
"""
visited = [False] * V
queue = deque([0])
visited[0] = True
result = []
while queue:
node = queue.popleft()
result.append(node)
# Visit all adjacent vertices
for neighbor in adj[node]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
return result
# Driver Code
V = 5
adj = [[] for _ in range(V)]
edges = [(0, 1), (0, 2), (0, 3), (2, 4)]
for u, v in edges:
adj[u].append(v)
sol = Solution()
print(sol.bfsOfGraph(V, adj)) # Output: [0, 1, 2, 3, 4]
Time Complexity: O(V + E)
Space Complexity: O(V)
Question 2: DFS Traversal of Graph
Problem: Given a connected undirected graph, perform DFS traversal starting from node 0.
class Solution:
def dfsOfGraph(self, V, adj):
"""
V: number of vertices
adj: adjacency list
"""
visited = [False] * V
result = []
def dfs(node):
visited[node] = True
result.append(node)
for neighbor in adj[node]:
if not visited[neighbor]:
dfs(neighbor)
dfs(0)
return result
# Driver Code
V = 5
adj = [[1, 2, 3], [0], [0, 4], [0], [2]]
sol = Solution()
print(sol.dfsOfGraph(V, adj)) # Output: [0, 1, 2, 4, 3]
Time Complexity: O(V + E)
Space Complexity: O(V)
Question 3: Detect Cycle in Undirected Graph
Problem: Given an undirected graph, detect if it contains a cycle.
from collections import deque
class Solution:
def isCycle(self, V, adj):
visited = [False] * V
def bfs(start):
queue = deque([(start, -1)]) # (node, parent)
visited[start] = True
while queue:
node, parent = queue.popleft()
for neighbor in adj[node]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append((neighbor, node))
elif neighbor != parent:
# Found a back edge (cycle)
return True
return False
# Check all components
for i in range(V):
if not visited[i]:
if bfs(i):
return True
return False
# Alternative: DFS approach
def isCycleDFS(V, adj):
visited = [False] * V
def dfs(node, parent):
visited[node] = True
for neighbor in adj[node]:
if not visited[neighbor]:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True
return False
for i in range(V):
if not visited[i]:
if dfs(i, -1):
return True
return False
# Driver Code
V = 5
adj = [[1], [0, 2, 4], [1, 3], [2, 4], [1, 3]]
sol = Solution()
print(sol.isCycle(V, adj)) # Output: True
Time Complexity: O(V + E)
Space Complexity: O(V)
Question 4: Detect Cycle in Directed Graph
Problem: Given a directed graph, detect if it contains a cycle.
class Solution:
def isCyclic(self, V, adj):
# 0 = unvisited, 1 = being processed, 2 = processed
state = [0] * V
def dfs(node):
state[node] = 1 # Mark as being processed
for neighbor in adj[node]:
if state[neighbor] == 1:
# Back edge found - cycle exists
return True
if state[neighbor] == 0 and dfs(neighbor):
return True
state[node] = 2 # Mark as processed
return False
for i in range(V):
if state[i] == 0:
if dfs(i):
return True
return False
# Driver Code
V = 4
adj = [[1], [2], [3], [1]] # Cycle: 1 -> 2 -> 3 -> 1
sol = Solution()
print(sol.isCyclic(V, adj)) # Output: True
Time Complexity: O(V + E)
Space Complexity: O(V)
Question 5: Topological Sort (Kahn's Algorithm - BFS)
Problem: Given a directed acyclic graph (DAG), find its topological ordering.
from collections import deque
class Solution:
def topoSort(self, V, adj):
# Calculate in-degree of each vertex
in_degree = [0] * V
for u in range(V):
for v in adj[u]:
in_degree[v] += 1
# Add all vertices with in-degree 0 to queue
queue = deque()
for i in range(V):
if in_degree[i] == 0:
queue.append(i)
result = []
while queue:
node = queue.popleft()
result.append(node)
# Reduce in-degree of neighbors
for neighbor in adj[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return result
# Driver Code
V = 6
adj = [[], [], [3], [1], [0, 1], [0, 2]]
sol = Solution()
print(sol.topoSort(V, adj)) # Output: [4, 5, 0, 2, 3, 1]
Time Complexity: O(V + E)
Space Complexity: O(V)
Question 6: Topological Sort (DFS)
Problem: Implement topological sort using DFS.
class Solution:
def topoSort(self, V, adj):
visited = [False] * V
stack = []
def dfs(node):
visited[node] = True
for neighbor in adj[node]:
if not visited[neighbor]:
dfs(neighbor)
# Add to stack after processing all children
stack.append(node)
for i in range(V):
if not visited[i]:
dfs(i)
# Reverse to get topological order
return stack[::-1]
# Driver Code
V = 6
adj = [[], [], [3], [1], [0, 1], [0, 2]]
sol = Solution()
print(sol.topoSort(V, adj)) # Output: [5, 4, 2, 3, 1, 0]
Time Complexity: O(V + E)
Space Complexity: O(V)
Question 7: Dijkstra's Algorithm (Shortest Path)
Problem: Given a weighted, undirected graph and a source vertex, find the shortest distance to all vertices.
import heapq
class Solution:
def dijkstra(self, V, adj, S):
"""
V: number of vertices
adj: adjacency list with (neighbor, weight)
S: source vertex
"""
# Distance array
dist = [float('inf')] * V
dist[S] = 0
# Min-heap: (distance, vertex)
pq = [(0, S)]
while pq:
d, u = heapq.heappop(pq)
# Skip if already processed with smaller distance
if d > dist[u]:
continue
for v, weight in adj[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(pq, (dist[v], v))
return dist
# Driver Code
V = 6
adj = [[] for _ in range(V)]
edges = [(0, 1, 4), (0, 2, 4), (1, 2, 2), (2, 3, 3),
(2, 4, 1), (2, 5, 6), (3, 5, 2), (4, 5, 3)]
for u, v, w in edges:
adj[u].append((v, w))
adj[v].append((u, w))
sol = Solution()
print(sol.dijkstra(V, adj, 0)) # Output: [0, 4, 4, 7, 5, 8]
Time Complexity: O((V + E) log V)
Space Complexity: O(V)
Question 8: Bellman-Ford Algorithm
Problem: Find shortest paths from source to all vertices (handles negative weights).
class Solution:
def bellmanFord(self, V, edges, S):
"""
V: number of vertices
edges: list of (u, v, weight)
S: source vertex
"""
dist = [float('inf')] * V
dist[S] = 0
# Relax all edges V-1 times
for _ in range(V - 1):
for u, v, weight in edges:
if dist[u] != float('inf') and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
# Check for negative cycle
for u, v, weight in edges:
if dist[u] != float('inf') and dist[u] + weight < dist[v]:
return [-1] # Negative cycle detected
return dist
# Driver Code
V = 5
edges = [(0, 1, 5), (0, 2, 4), (1, 3, 3), (2, 1, -6), (3, 2, 2)]
sol = Solution()
print(sol.bellmanFord(V, edges, 0)) # Output: [0, -2, 4, 1, inf]
Time Complexity: O(V × E)
Space Complexity: O(V)
Question 9: Number of Provinces (Connected Components)
Problem: Given an adjacency matrix, find the number of provinces (connected components).
class Solution:
def findCircleNum(self, isConnected):
n = len(isConnected)
visited = [False] * n
provinces = 0
def dfs(city):
visited[city] = True
for neighbor in range(n):
if isConnected[city][neighbor] == 1 and not visited[neighbor]:
dfs(neighbor)
for i in range(n):
if not visited[i]:
provinces += 1
dfs(i)
return provinces
# Driver Code
isConnected = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
sol = Solution()
print(sol.findCircleNum(isConnected)) # Output: 2
Time Complexity: O(n²)
Space Complexity: O(n)
Question 10: Flood Fill Algorithm
Problem: Perform flood fill starting from a given pixel with a new color.
class Solution:
def floodFill(self, image, sr, sc, color):
original_color = image[sr][sc]
if original_color == color:
return image
m, n = len(image), len(image[0])
def dfs(r, c):
if r < 0 or r >= m or c < 0 or c >= n:
return
if image[r][c] != original_color:
return
image[r][c] = color
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
dfs(sr, sc)
return image
# Driver Code
image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
sr, sc, color = 1, 1, 2
sol = Solution()
result = sol.floodFill(image, sr, sc, color)
for row in result:
print(row)
# Output: [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
Time Complexity: O(m × n)
Space Complexity: O(m × n)
Question 11: Rotting Oranges
Problem: Calculate minimum time for all fresh oranges to become rotten.
from collections import deque
class Solution:
def orangesRotting(self, grid):
m, n = len(grid), len(grid[0])
queue = deque()
fresh = 0
# Find all rotten oranges and count fresh ones
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
queue.append((i, j, 0)) # (row, col, time)
elif grid[i][j] == 1:
fresh += 1
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
max_time = 0
while queue:
r, c, time = queue.popleft()
max_time = max(max_time, time)
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc, time + 1))
return max_time if fresh == 0 else -1
# Driver Code
grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
sol = Solution()
print(sol.orangesRotting(grid)) # Output: 4
Time Complexity: O(m × n)
Space Complexity: O(m × n)
Question 12: Word Ladder
Problem: Transform beginWord to endWord, changing one letter at a time, with each intermediate word in wordList.
from collections import deque
class Solution:
def ladderLength(self, beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return 0
queue = deque([(beginWord, 1)])
while queue:
word, length = queue.popleft()
if word == endWord:
return length
# Try all possible transformations
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word in wordSet:
wordSet.remove(new_word)
queue.append((new_word, length + 1))
return 0
# Driver Code
beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
sol = Solution()
print(sol.ladderLength(beginWord, endWord, wordList)) # Output: 5
Time Complexity: O(N × M × 26) where N = wordList size, M = word length
Space Complexity: O(N)
Question 13: Clone Graph
Problem: Return a deep copy (clone) of a connected undirected graph.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
class Solution:
def cloneGraph(self, node):
if not node:
return None
# Map original nodes to cloned nodes
visited = {}
def dfs(original):
if original in visited:
return visited[original]
# Create clone
clone = Node(original.val)
visited[original] = clone
# Clone neighbors
for neighbor in original.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)
Time Complexity: O(V + E)
Space Complexity: O(V)
Question 14: Course Schedule (Detect Cycle in Prerequisites)
Problem: Determine if all courses can be finished given prerequisites.
from collections import deque
class Solution:
def canFinish(self, numCourses, prerequisites):
# Build adjacency list and calculate in-degrees
adj = [[] for _ in range(numCourses)]
in_degree = [0] * numCourses
for course, prereq in prerequisites:
adj[prereq].append(course)
in_degree[course] += 1
# Start with courses having no prerequisites
queue = deque()
for i in range(numCourses):
if in_degree[i] == 0:
queue.append(i)
courses_taken = 0
while queue:
course = queue.popleft()
courses_taken += 1
for next_course in adj[course]:
in_degree[next_course] -= 1
if in_degree[next_course] == 0:
queue.append(next_course)
return courses_taken == numCourses
# Driver Code
numCourses = 4
prerequisites = [[1, 0], [2, 1], [3, 2]]
sol = Solution()
print(sol.canFinish(numCourses, prerequisites)) # Output: True
Time Complexity: O(V + E)
Space Complexity: O(V)
Question 15: Alien Dictionary
Problem: Given a sorted dictionary of alien language words, find the order of characters.
from collections import deque, defaultdict
class Solution:
def alienOrder(self, words):
# Build graph
adj = defaultdict(set)
in_degree = {c: 0 for word in words for c in word}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
min_len = min(len(w1), len(w2))
# Check for invalid case: "abc" before "ab"
if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
return ""
for j in range(min_len):
if w1[j] != w2[j]:
if w2[j] not in adj[w1[j]]:
adj[w1[j]].add(w2[j])
in_degree[w2[j]] += 1
break
# Topological sort
queue = deque([c for c in in_degree if in_degree[c] == 0])
result = []
while queue:
c = queue.popleft()
result.append(c)
for neighbor in adj[c]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return "".join(result) if len(result) == len(in_degree) else ""
# Driver Code
words = ["wrt", "wrf", "er", "ett", "rftt"]
sol = Solution()
print(sol.alienOrder(words)) # Output: "wertf"
Time Complexity: O(C) where C = total characters
Space Complexity: O(1) (at most 26 characters)
Question 16: Number of Islands
Problem: Count the number of islands in a 2D grid.
class Solution:
def numIslands(self, grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
islands = 0
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
return
grid[i][j] = '0' # Mark as visited
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
islands += 1
dfs(i, j)
return islands
# Driver Code
grid = [
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]
]
sol = Solution()
print(sol.numIslands(grid)) # Output: 3
Time Complexity: O(m × n)
Space Complexity: O(m × n)
Question 17: Minimum Spanning Tree (Kruskal's Algorithm)
Problem: Find the cost of Minimum Spanning Tree using Kruskal's algorithm.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
class Solution:
def spanningTree(self, V, adj):
# Convert to edge list
edges = []
for u in range(V):
for v, weight in adj[u]:
if u < v: # Avoid duplicates
edges.append((weight, u, v))
# Sort by weight
edges.sort()
uf = UnionFind(V)
mst_cost = 0
edges_used = 0
for weight, u, v in edges:
if uf.union(u, v):
mst_cost += weight
edges_used += 1
if edges_used == V - 1:
break
return mst_cost
# Driver Code
V = 3
adj = [[[1, 5], [2, 1]], [[0, 5], [2, 3]], [[0, 1], [1, 3]]]
sol = Solution()
print(sol.spanningTree(V, adj)) # Output: 4
Time Complexity: O(E log E)
Space Complexity: O(V)
Question 18: Prim's Algorithm for MST
Problem: Find MST cost using Prim's algorithm.
import heapq
class Solution:
def spanningTree(self, V, adj):
visited = [False] * V
min_heap = [(0, 0)] # (weight, vertex)
mst_cost = 0
while min_heap:
weight, u = heapq.heappop(min_heap)
if visited[u]:
continue
visited[u] = True
mst_cost += weight
for v, w in adj[u]:
if not visited[v]:
heapq.heappush(min_heap, (w, v))
return mst_cost
# Driver Code
V = 3
adj = [[[1, 5], [2, 1]], [[0, 5], [2, 3]], [[0, 1], [1, 3]]]
sol = Solution()
print(sol.spanningTree(V, adj)) # Output: 4
Time Complexity: O(E log V)
Space Complexity: O(V)
Question 19: Find Eventual Safe States
Problem: Return all safe nodes in a directed graph (nodes not part of any cycle).
class Solution:
def eventualSafeNodes(self, graph):
n = len(graph)
# 0 = unvisited, 1 = visiting, 2 = safe
state = [0] * n
def dfs(node):
if state[node] != 0:
return state[node] == 2
state[node] = 1 # Mark as visiting
for neighbor in graph[node]:
if not dfs(neighbor):
return False
state[node] = 2 # Mark as safe
return True
safe_nodes = []
for i in range(n):
if dfs(i):
safe_nodes.append(i)
return safe_nodes
# Driver Code
graph = [[1, 2], [2, 3], [5], [0], [5], [], []]
sol = Solution()
print(sol.eventualSafeNodes(graph)) # Output: [2, 4, 5, 6]
Time Complexity: O(V + E)
Space Complexity: O(V)
Question 20: Cheapest Flights Within K Stops
Problem: Find the cheapest price from src to dst with at most k stops.
import heapq
from collections import defaultdict
class Solution:
def findCheapestPrice(self, n, flights, src, dst, k):
# Build adjacency list
graph = defaultdict(list)
for u, v, price in flights:
graph[u].append((v, price))
# (cost, stops, node)
heap = [(0, 0, src)]
# Track minimum cost to reach each node with specific stops
dist = [[float('inf')] * (k + 2) for _ in range(n)]
dist[src][0] = 0
while heap:
cost, stops, node = heapq.heappop(heap)
if node == dst:
return cost
if stops > k:
continue
for neighbor, price in graph[node]:
new_cost = cost + price
if new_cost < dist[neighbor][stops + 1]:
dist[neighbor][stops + 1] = new_cost
heapq.heappush(heap, (new_cost, stops + 1, neighbor))
return -1
# Driver Code
n = 4
flights = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]]
src, dst, k = 0, 3, 1
sol = Solution()
print(sol.findCheapestPrice(n, flights, src, dst, k)) # Output: 700
Time Complexity: O(E × k log(V × k))
Space Complexity: O(V × k)
MCQ Questions
Question 1
Which data structure is used in BFS traversal?
- A) Stack
- B) Queue
- C) Priority Queue
- D) Tree
Question 2
What is the time complexity of Dijkstra's algorithm with a binary heap?
- A) O(V²)
- B) O(V + E)
- C) O((V + E) log V)
- D) O(V × E)
Question 3
Which algorithm can handle negative edge weights?
- A) Dijkstra's
- B) Prim's
- C) Bellman-Ford
- D) Kruskal's
Question 4
Topological sorting is applicable to:
- A) Undirected graphs
- B) Directed Acyclic Graphs (DAG)
- C) Cyclic graphs
- D) Complete graphs
Question 5
In Union-Find, what is the time complexity with path compression and union by rank?
- A) O(n)
- B) O(log n)
- C) O(α(n)) - Inverse Ackermann
- D) O(1)
Interview Tips for Graphs
-
Choose the right representation: Use adjacency list for sparse graphs, adjacency matrix for dense graphs
-
BFS vs DFS:
- Use BFS for shortest path in unweighted graphs
- Use DFS for cycle detection, topological sort, connected components
-
Practice these patterns:
- Island problems (Number of Islands, Max Area)
- Shortest path variations (BFS, Dijkstra, Bellman-Ford)
- Topological sort (Course Schedule, Alien Dictionary)
- Union-Find (Connected Components, MST)
-
Common mistakes to avoid:
- Forgetting to mark nodes as visited
- Not handling disconnected components
- Wrong traversal direction in directed graphs
-
Edge cases to test:
- Empty graph
- Single node
- Disconnected components
- Self-loops
- Negative weights (for shortest path)
Frequently Asked Questions
Q1: When should I use BFS vs DFS?
A: Use BFS when you need the shortest path in unweighted graphs or level-order traversal. Use DFS for cycle detection, topological sorting, and when you need to explore all paths.
Q2: How do I detect a cycle in a directed graph?
A: Use DFS with three states: unvisited, being processed (in current recursion stack), and processed. If you encounter a node that's being processed, a cycle exists.
Q3: Can Dijkstra handle negative weights?
A: No, Dijkstra's algorithm cannot handle negative weights. Use Bellman-Ford instead, which can also detect negative cycles.
Q4: What's the difference between Kruskal's and Prim's algorithm?
A: Kruskal's sorts all edges and adds them in order, using Union-Find. Prim's starts from a vertex and grows the MST by adding the minimum edge connected to the current tree.
Q5: How do I find the shortest path in an unweighted graph?
A: Use BFS. It naturally finds the shortest path in terms of number of edges in O(V + E) time.
This guide covers essential graph algorithms for placement preparation. Practice these problems multiple times and understand the underlying concepts thoroughly.