Best Roadmap for Graphs for FAANG + CP [2022]

Question

1 Answer

Best answer

Step-0 : Learn about graph representation from here->https://www.hackerearth.com/practice/algorithms/graphs/graph-representation/tutorial/

1)First things first , BFS and DFS , these two topics should be completely clear for you and you should have a strong command in these . As being strong in these two, will make rest of the journey of graphs for you easy . These are the building blocks and the needed fundamentals.

2)Watch these videos and resources to learn these :-

i)

ii)

iii)https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/

iv)https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/tutorial/

In general follow this pathway for your preparation : {Credits->Prabal Jain}

[

Minimalistic RoadMap:
1. Basics of Graph: Dil aur dimag mein baithana hai
2. BFS and DFS: Classicals like cycle finding and counting components + more -> get a basic feel of BFS DFS
3. Basic Classical Algorithms: SSSP[Dijkstra and Bellman] and all pair [Floyd Warshall]
4. Some more Practice of BFS and 3rd point Questions
5. Topological Sort and Kahn's Algo [at least 3 questions to make up in mind]
6. Union Find and MST [5Questions for Mind Makeup]

]

v)Solve these set of problems and use these resources for further steps : -

{If you encounter new topics while solving these graph problems , then watch their videos and resources before trying to solve the problem}.

Their resources :-

For a complete overview of all important algorithms in graphs (especially for top companies’ coding interviews) , you can go through these two youtube playlists :-

i)

{Striver}

ii)

{CodeLibrary}

iii)Abdul Bari has the best videos on a few of the graph topics so do search them a bit.

iv)Knowing BFS,DFS,connected components,and some popular algorithms is enough for your prep for coding interviews. You don’t need to go further than that.

v)https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/

vi)https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/tutorial/

vii)https://www.hackerearth.com/practice/algorithms/graphs/flood-fill-algorithm/tutorial/

viii)https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/

ix)https://www.hackerearth.com/practice/algorithms/graphs/biconnected-components/tutorial/

x)https://www.hackerearth.com/practice/algorithms/graphs/strongly-connected-components/tutorial/

xi)https://www.hackerearth.com/practice/algorithms/graphs/topological-sort/tutorial/

Solve these-

1)https://www.hackerearth.com/challenges/competitive/codemonk-graph-theory-part-i/algorithm/monk-learning-graph-3/description/

2)https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/practice-problems/algorithm/monk-and-the-islands/

3)Resource : https://leetcode.com/discuss/interview-question/1408203/2-bfs-for-graphs

4)Solving these problems will make your graph preparation very strong(some of the later problems are advanced , so solve these according to your preparation level):--->

https://codeforces.com/blog/entry/79518

(Solution to every problem is available on internet}

5)Best list of problems and resources :-

00)https://leetcode.com/discuss/study-guide/1326900/graph-algorithms-problems-to-practice

11)https://leetcode.com/discuss/general-discussion/655708/Graph-For-Beginners-Problems-or-Pattern-or-Sample-Solutions

22)