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

1. Choose the right representation: Use adjacency list for sparse graphs, adjacency matrix for dense graphs

2. BFS vs DFS:

   • Use BFS for shortest path in unweighted graphs
   • Use DFS for cycle detection, topological sort, connected components

3. 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)

4. Common mistakes to avoid:

   • Forgetting to mark nodes as visited
   • Not handling disconnected components
   • Wrong traversal direction in directed graphs

5. 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.