**Advanced Problems on graph theory**

**1. Implement Dijkstraâ€™s Algorithm.**

Refer to the problem __Dijkstra's shortest path__ to practice the problem and understand the approach behind it. It's common to be asked about the time/space complexity of the algorithm and why it doesn't work for negative edge weights. Refer to the article on __Dijkstra's algorithm__ to learn more about the algorithm.

**2. Find the minimum cost from source to destination (but you can reduce the cost of one edge)**

This problem utilises Dijkstra's algorithm with some modifications. Refer to the __article__ on the problem to get a detailed explanation of its implementation.

**3. Find the minimum spanning tree.**

Refer to the problem on the __minimum spanning tree__, try the problem and refer to the approach for help. You can also do the problem using prim's algorithm learn more about __Prim's algorithm__ and __Kruskal's algorithm__ through the related articles.

**4. Strongly Connected components using Kosaraju's algorithm and Tarjan's Algorithm.**

Refer to the problem on __Kosaraju's Algorithm__ and __Tarjan's Algorithm__. Try the problem using both methods and observe the differences.

**5. Find the Bridge edge in a graph.**

Refer to the problem __bridges in a graph__ to practice the problem and understand its approach.

**6. Implement Flood Fill Algorithm.**

Refer to the problem __flood fill algorithm__ to practice the problem and understand the approaches behind it.

**7. Replace 'O' with 'X'. All the 'O' surrounded by 'X' from all 4 sides will be replaced.**

Refer to the problem __replace o's with x's__ to practice the problem and understand its approach.

**8. Find the presence of a word in a grid of letters.**

Refer to the problem __Word Search__ to practice the problem and understand the approach behind it. As a bonus, try to count the occurrence of the word in the grid. Try the bonus problem __word search 2__.

**9. Write and explain DSU (DIsjoint Set Union).**

Refer to __Learning DSU__ learn about DSU so that you can understand them enough to explain how they work. Try to implement __Kruskal's algorithm using DSU__ you learned just now.

**10. Smallest Vertex in the Connected Components of all the Vertices in the Given Undirected Graph.**

Refer to the article here. It covers the entire approach in detail. This will help you practice a question with a direct application of DSU.

**11. Part 3 of word searching in a matrix.**

Refer to the problem __Word Search 3__ to practice the problem and understand its approach. Previously discussed, __word search 1__ and __word search 2__ were good starting points before this problem.

**12. Critical Connections in a graph**

Refer to the critical connection problem to practice the problem and understand its approach.

**13. Articulation point, what is it and how to find it.**

Refer to the article on __articulation points__ for reference and try to write the code for the following problem by yourself.

**14. You are given an alien language (code language) in a sorted dictionary, and you must find the order of alphabets in the language.**

Refer to the problem __alien dictionary__ to practice the problem and understand its approach.

**15. Solve the problem word ladder.**

Refer to the problem __word ladder__ to practice the problem and understand its approach. As a bonus, you can also try __word break__ and try to understand its approach.

**16. Number of islands in a grid.**

Refer to the problem __number of islands 2__ to practice the problem and understand the approach behind it. Also, refer to the problem __number of islands__ before attempting this question.

**17. What are tries?**

Refer to the problem __trie implementation__ to practice the problem and understand its approach. If this is a new topic, refer to the trie related articles here.

**18. Find the count of palindromic pairs in an array of strings?**

Refer to the problem __count palindromic pairs__ to practice the problem and understand its approach. This question is an application of tries, covered previously.

**Key Takeaways**

This article extensively discussed the advanced problems that you may encounter in your future interviews and online investments. Refer to __learn graphs-1__ to learn about graphs as a beginner, __Important graph problems for Interviews (Basic Problems)__ and learn more about __graph theory algorithms and terminology__ used in competitive programming and interviews.

Recommended Problems:

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

Enroll 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!