Introduction to Graphs: Definitions, Traversal, Depth-First Search

kuruma · July 19, 2013, 2:15pm

Thanks for your positive feedback sir

v_akshay · July 19, 2013, 10:46pm

@admin , why does it say “asked n days ago by kuruma” shouldn’t it rather say “posted n days ago by kuruma” ? btw @Kuruma, really nice and helpful post

r93sachdeva55 · July 20, 2013, 1:18am

GALACTICK could be solved using Disjoint Sets data structure instead of DFS and BFS. This would have sped up the code by many times

kuruma · July 22, 2013, 11:22pm

Thank you @v_akshay, I’m glad you liked this About the asked vs posted part, as this was a “question”, it says asked, but, I guess that is just how the forums work

re_hash · July 23, 2013, 1:29pm

Nice work kuruma…keep it up.It was written in a neat and crisp way.This tutorial was required by many newbies. One can expect people implementing this tutorial’s code from the next contests

kuruma · July 23, 2013, 7:27pm

Thank you very much for the positive feedback @re_hash! I hope I can implement all these ideas in next contests myself as well

sayan_paul · September 18, 2013, 10:19pm

Awesome post !! Easy to understand and really good for a beginner . .

I tried my hand on implementing some of the graph algorithms in python and I’ve uploaded it on github link , if someone wants to go through them , its available . It might be a bit messy though , I’ve tried my best to make it look good and readable . Hope it helps !!

garakchy · January 21, 2014, 5:34am

to ADMIN staff, pls pin algo tutorials like these on static algo tutorials page. topcoder has that

kuruma · January 21, 2014, 6:22am

Do we have a “static algo tutorials page” here on Discuss? The closest thing seems to be the tutorials and references posted at Codechef for Schools page, but, if we could pin a “sub-forum” grouping all tutorials or even better all editorials on its own “sub-forums”, that would be really useful

buro · February 17, 2014, 5:02pm

@Kuruma
its really helpful thanks!!

r3gz3n · February 17, 2014, 5:13pm

I solved the problem first by Disjoint Sets and then by DFS. Learned a lot about DFS from GALACTIK that helped me in FEB14 in solving DRGHTS.

v_nishanth · February 3, 2015, 10:19pm

Have a look at this blog it contains nice stuff on graphs and trees…

amanjain7793 · June 22, 2015, 10:56am

i am not getting what is sz_connct_compt is? could u please explain me?

bradley · August 23, 2015, 10:59am

The best Explanation of Graphs, I have seen so far.

I did not attempted the Graph Problems, as I was thinking that it was not my cup of cake, but now I will try it.

Thanks @kuruma

bradley · August 23, 2015, 11:02am

It tells that a particular friend has sz_connct_compt number of connected friends.

Means, if 1->2 and 2->3 and 3->5,6
so when we dfs(1) the sz_connct_compt will become 5, as there are 5 friends that will be liking to escape by same route.

I hope now you have understood. @amanjain7793

manikanta001 · September 2, 2015, 11:32pm

Tanq so much

yrahul · December 9, 2015, 11:25pm

@kuruma Could you explain how you calculate the number of ways to select the captains? I didn’t understand that part.

kishynivas_13 · March 11, 2017, 6:17pm

Nice tutorial, made DFS so clear as you used it to solve a problem, This is a great help for beginners please continue this kind of tutorials.

alpha12 · April 4, 2017, 11:03pm

following link is be very useful for u to understand binary tree traversal(pre-order, in-order, post-order) in detail including graphs: