Graphs - DSA Interview Questions

Graphs are a fundamental data structure used to represent connections between entities, such as social networks, road maps, and dependencies in computation. They consist of nodes (vertices) and edges, which can be directed or undirected. Graph algorithms help solve real-world problems like shortest paths, cycle detection, and network traversal.

Practice Graphs DSA Coding Problems with Solutions

Learning Objectives:

Understand how graphs represent relationships and how to traverse them using BFS and DFS. Learn to apply graph algorithms to solve real-world problems like shortest paths, cycle detection, and topological sorting.

Exercise Instructions:

Start with the first problem and attempt to solve it before checking the hint or solution.
Ensure you understand the logic behind each solution, as this will help you with more complex problems.
Use these exercises to reinforce your learning and identify areas that may require further study.

1. Graph Representation

Required Input:

[[0, 1], [0, 2], [1, 2], [2, 3]] 
4

Expected Output:

({0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}, [[0, 1, 1, 0], [1, 0, 1, 0], [1, 1, 0, 1], [0, 0, 1, 0]])

Code In Python

def graph_representation(edges, num_nodes): # Write your logic here pass # Prefilled input edges = [[0, 1], [0, 2], [1, 2], [2, 3]] num_nodes = 4 print(graph_representation(edges, num_nodes))

Run Code?

Click Run Button to view compiled output

2. BFS Traversal

Required Input:

{0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}
0

Expected Output:

[0, 1, 2, 3]

Code In Python

def bfs_traversal(graph, start): # Write your logic here pass # Prefilled input graph = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]} start = 0 print(bfs_traversal(graph, start))

Run Code?

Click Run Button to view compiled output

3. DFS Traversal

Required Input:

{0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}
0

Expected Output:

[0, 1, 2, 3]

Code In Python

def dfs_traversal(graph, start): # Write your logic here pass # Prefilled input graph = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]} start = 0 print(dfs_traversal(graph, start))

Run Code?

Click Run Button to view compiled output

4. Cycle Detection (Undirected)

Required Input:

[[0, 1], [1, 2], [2, 0], [2, 3]]
4

Expected Output:

True

Code In Python

def has_cycle_undirected(graph, num_nodes): # Write your logic here pass # Prefilled input edges = [[0, 1], [1, 2], [2, 0], [2, 3]] num_nodes = 4 print(has_cycle_undirected(edges, num_nodes))

Run Code?

Click Run Button to view compiled output

5. Cycle Detection (Directed)

Required Input:

[[0, 1], [1, 2], [2, 3], [3, 1]] 
4

Expected Output:

True

Code In Python

def has_cycle_directed(graph, num_nodes): # Write your logic here pass # Prefilled input edges = [[0, 1], [1, 2], [2, 3], [3, 1]] num_nodes = 4 print(has_cycle_directed(edges, num_nodes))

Run Code?

Click Run Button to view compiled output

6. Connected Components

Required Input:

[[0, 1], [1, 2], [3, 4]]
num_nodes = 5

Expected Output:

Code In Python

def count_connected_components(edges, num_nodes): # Write your logic here pass # Prefilled input edges = [[0, 1], [1, 2], [3, 4]] num_nodes = 5 print(count_connected_components(edges, num_nodes))

Run Code?

Click Run Button to view compiled output

7. Bipartite Graph

Required Input:

[[0, 1], [1, 2], [2, 3], [3, 0]] 
num_nodes = 4

Expected Output:

True

Code In Python

def is_bipartite(edges, num_nodes): # Write your logic here pass # Prefilled input edges = [[0, 1], [1, 2], [2, 3], [3, 0]] num_nodes = 4 print(is_bipartite(edges, num_nodes))

Run Code?

Click Run Button to view compiled output

8. Clone Graph

Required Input:

{0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}

Expected Output:

{0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}

Code In Python

def clone_graph(graph): # Write your logic here pass # Prefilled input graph = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]} print(clone_graph(graph))

Run Code?

Click Run Button to view compiled output

9. Shortest Path (Unweighted)

Required Input:

[[0, 1], [0, 2], [1, 2], [1, 3], [2, 3], [3, 4]] 
5 
0

Expected Output:

[0, 1, 1, 2, 3]

Code In Python

def shortest_path_unweighted(edges, num_nodes, start): # Write your logic here pass # Prefilled input edges = [[0, 1], [0, 2], [1, 2], [1, 3], [2, 3], [3, 4]] num_nodes = 5 start = 0 print(shortest_path_unweighted(edges, num_nodes, start))

Run Code?

Click Run Button to view compiled output

10. Valid Tree

Required Input:

5
[[0, 1], [1, 2], [2, 3], [3, 4]]

Expected Output:

True

Code In Python

def is_valid_tree(n, edges): # Write your logic here pass # Prefilled input n = 5 edges = [[0, 1], [1, 2], [2, 3], [3, 4]] print(is_valid_tree(n, edges))

Run Code?

Click Run Button to view compiled output

1 of 3