**Problems to help you get started with graph theory**

**1. Print the adjacency matrix and the adjacency list of a graph.**

Refer to the article on __various graph representation__ methods to learn more about various such methods. Refer to the article __implementation of graph representations__ for the implementation details.

**2. Print a DFS traversal of a graph.**

This problem utilises the depth-first search algorithm. Try the problem by doing __dfs traversal__, which also covers the approach to do the problem if you get stuck.

**3. Print a BFS traversal of a graph.**

This problem utilises the breadth-first search algorithm. Try the problem __bfs in a graph__ that also covers the approach to do the problem if you get stuck.

**4. Find Transitive Closure of a graph.**

Refer to the problem, __transitive closure of a directed graph__ to practice the problem and understand the approach behind it.

**5. Find the number of connected components in a directed graph.**

This problem can be solved with 3 different methods. You can try the problem by doing the problem, __finding the number of states__ and learning about all the various methods.

**6. Find the number of connected components in an undirected graph.**

This problem is commonly asked in various interviews, usually not directly, but it's an important stepping stone. Try to solve the problem using the 3 methods discussed for (5).

**7. Find the number of '0' islands in a binary matrix (containing only '1' and '0').**

This problem utilises the ideas covered in problem 6, and you can try it by doing the problem __count islands__.

**8. Detect a cycle in an undirected graph.**

This problem again directly applies graph traversal algorithms. Refer here to solve the problem __detect cycle in an undirected graph__. The approach covers the BFS method. Try solving the problem using __DFS Algorithm__.

**9. Print a topological sort of a directed acyclic graph. (As a bonus, you can try printing the lexicographically minimum topological sort)**

This problem can be done using different algorithms (Kahn's Algorithm, modified DFS, etc.). Check out the __topo sort__ problem and try solving it. Here is the article on __Kahn's algorithm__ for reference.

HINT: The bonus problem can be solved using Kahn's Algorithm and a min-heap.

**10. You are given N tasks, and certain tasks have prerequisites (these prerequisites must be completed before completing that task). Find if it's possible to complete the set of tasks and if it's possible, print an order in which you can complete all the tasks.**

The set of tasks can only be completed if the graph is a DAG (directed acyclic graph), and the next task is to print the topological sort for the graph (if it's a DAG).

**11. Print the Hamiltonian Cycle in a graph.**

Refer to the problem __find hamiltonian cycle__ and refer to the optimised approach for the implementation and explanation of the approach. Refer to __Euler and hamiltonian paths__ as prerequisites for solving the problem.

**12. Find if an array of strings (words) can be arranged into a cycle.**

Refer to the problem __circle of words__ to practise the problem and understand the approach behind it.

**13. A snake and ladder board is given as input to find the minimum number of dice moves required to reach the bottom-leftmost point to the top-rightmost point.**

Refer to the problem __snake and ladder__ to practise the problem and understand the approach behind it.

**14. Given a graph, determine if the graph is bipartite.**

Refer to the problem __check if graph is bipartite__ to practise the problem and understand the approach behind it. Refer to the article on __bipartite graphs__** **as a prerequisite.

**15. Find the maximum bipartite matching in a graph.**

The problem is a good exercise after the previous problem. This problem can be solved using the Ford Fulkerson algorithm or Kuhn's Algorithm. Refer to the article on F__ord Fulkerson and min-cut__ for reference.

**16. Detect the presence of a cycle in a directed graph.**

Refer to the problem on __detect cycles in a directed graph__ to practise the problem and understand the approach behind it.

**17. Find whether a path exists between two vertices.**

Refer to the problem, __check if a path exists__ to solve the problem and understand the approach behind it.

**18. Find the node level in a tree rooted at some node.**

Refer to the problem on __node level__ to practise the problem and understand the approach behind it.

**19. Print all the possible paths between two vertices in a graph.**

Refer to the article on __printing all paths from a source to a destination vertex__ to understand the approach in detail with implementation to help you understand it better.

**20. Distance of nearest cell in a binary matrix (containing 0 and 1 only) to the cell having 1 in it.**

Refer to the problem of finding__ the distance between nearest 1__ to practise the problem and understand the approach behind it.

**21. A grid contains fresh and rotten oranges. Every second, all oranges adjacent to the rotten ones also become rotten. Find the minimum time before which all oranges become rotten, or print -1 if it's impossible for all oranges to become rotten.**

Refer to the problem __rotting oranges__ to practise the problem and understand the approach behind it. The problem's approach is very similar to the previous question.

**22. Find the minimum number swaps required to sort an array (you can swap any two indices).**

Refer to the problem on __minimum swaps required__ to practise the problem and understand the approach behind it.

**23. Find the minimum number of steps a knight requires to reach a square on a grid.**

Refer to the problem on __minimum steps to reach the target by a knight__ to practise the problem and understand its approach. In problems like these, instead of using Dijkstra, bellman ford, etc., we will be using BFS to find the minimum distance in an unweighted graph.

**Key Takeaways**

In this article, we have extensively discussed the basic problems that you may encounter in your future interviews and online contests. Refer to __learn graphs-1__ to learn about graphs as a beginner and learn more about __graph theory algorithms and terminology__ used in competitive programming and interviews.

Refer to our __guided paths on Coding Ninjas Studio__ to learn more about DSA, Competitive Programming, JavaScript, System Design, etc.

Enrol in our __courses__ and refer to the __mock test__ and __problems__ available.

Take a look at the __interview experiences__ and __interview bundle__ for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Coding!