Demystifying Graph Cramming !
It has been long since I have been exploring various data structures and learning about them. My personal favorite are non-linear data structures. Many find them cliché and hard. I personally struggled a lot in begin (this was about six months back). But now I really adore reading about problems that these data structures can solve.
Graphs are a non-linear data structure. For a beginner they are hard to grasp and them many leave this topic in between many times , then start afresh , come to the same point and leave again. But, why do “many” do this ? The problem with graph data structures and problems related to them is just one — Programmers try to learn algorithms and do not actually go in depth that why this is the apt algorithm for the given task? They don't try to understand problems and just cram around 50+ questions from leetcode , just to hate this beautiful structure. I have tried to categorize all possible algorithms in groups and discussing why one should learn them.
I repeat again — Don’t try to learn graphs by googling “All famous interview problems”. It may never help. You will end up hating them. Never take any graph problem new and thinking something different should be used here. Try to view them as your previously learned algorithm version.
How does this blog works for you?
I have included all my learning regarding various algorithms and link to resources that can give you better idea regarding same.
Step 1. What is graph ? Basic terminologies in graph.
Do this together. Just try to increase your graph vocabulary by reading about connected, directed, cyclic — ish types of words. This is going to help you a lot. Believe me :p
Like Romeo is to Juliet , stack is to DFS and queue for BFS!
Step 2. Read about DFS(If you slow at recursion , first try to solve some problems on same.)
You should make DFS your primary tool in graphs. Wait, you think you slow at recursion, don’t go ahead, solve problems on recursion. Recursion is another topic that I adore. You may find this cliché but writing a neat recursive code is pro thing. A small thing that I have used to teach my friends recursion and it may even help you — Try to make function calls on a whiteboard , don’t be lazy, do it , until you can picture them in your head. What kind of recursion problems can help you ? Keypad problem ? No ! You must try tree problems. They are a perfect way to get you up and going with recursion.
Step 3. Read about BFS(This is an absolute cakewalk for you if you are done with DFS :p)
I personally think if you are done with DFS , BFS will be a cakewalk for you. This technique is easier to apply, but give the annoying runtime error or buffer overflow error a lot. Try to be very cautious.
You have made it far! You got your toolbox filled all basic amenities. Try to give adequate amount of time to these algorithms.
But, Hey ? What about those weird words like Kruskal's , Dijkstra's , MST blah blah ?
No , we are not leaving them at all. This is something I have realized — Don’t try to skip basics in haste of learning complicated algorithms. You will break the chain of connection that was building in your mind that was keeping everything connected(If you don’t know what I am talking about, Watch learn how to learn :p).
Step 4 . Cycle detection
Undirected Graph — Simple DFS / BFS ,
Directed Graph — Topological Sort, Union find
You can see I have included some topics like topo sort , union find here itself. The problem with many online tutorials is they will teach these topics a long after you solve cycle detection by dfs/bfs . For a long time I was confused as to where should I even apply them ? Try to find relation between these topics and your problem statement and you will thank yourself later.
Try to take time doing these topics. Specially Union Find :p
Step 5. What is spanning tree ? Use cases , how to make on paper ?
This is a theory topic. Try to frame some problems on paper and solve them. Don’t skip. Do it religiously :P
Step 6. What is Minimum spanning tree ? Prim’s , Kruskal's says here I come kiddo !
Give yourself a pat on back. You have come so far. This is a very important step in your journey. Also, if you want to save your time in future, do Prim’s whole heartedly. Spend time on both these algorithms. Write them on pen paper for better clarity. Don’t stop here. Give a short lecture to your friend on both these topics. If he/she do not get it, making them understand is your duty now.
Step 7. Shortest Path Algorithms — Dijkstra's , Floyd Warshall , Bellman Ford!
This is my favorite step. Not because I finally found Dijkstra's :p , but I actually realized how similar this guy is to Mr. Prim’s from the view of implementation(Gave you a small tip in Step 6). My life was sorted. I understood the most influential algorithm on earth. The other two algorithms are pretty cool and fair to grab. Follow the same ninja technique — Explain your friend until they get it.
We have come pretty far! I will end this blog here. But , Stop! We ain’t done yet. Second and last part of this blog will focus on further algorithms. I hope you found something much sorted on internet for graph. Hope it helps! Tell me about the ways you mastered graphs, I would love to hear them!
I am adding a list of resources that helped me. But I understand that it may not work for everyone, try googling stuff. It may help you explore much better stuff.
YouTube Playlist — Try to follow them in accordance with Steps mentioned.
https://www.youtube.com/watch?v=caAVlibiTkY&list=PLEJXowNB4kPzByLnnFYNSCoqtFz0VKLk5&index=1
Blogs — They are arranged in best possible way on internet.
https://www.hackerearth.com/practice/algorithms/graphs/graph-representation/tutorial/
Practice — Yes , leetcode is wonderful, but for a beginner it’s quite intimidating. Topics from trees , graph , BFS and DFS are quite mixed up. You can try hackerearth for initial practice or easy- medium level problems. If you really wanna do something insane after some practice, try the DSA learning series Basic Graph contest(not so basic :p) on codechef.
