Tips for Graph problems

Hello @all,

I wanted to ask you if you could reccomend me some Codechef problems about graph search algorithms only, if possible, in increasing order of difficulty :slight_smile:

I want to learn BFS and DFS gradually, so I can get a better feel of how to implement these concepts in code :slight_smile:

Any guidance would be extremely helpful :smiley:

Thanks in advance,

Bruno

5 Likes

I suggest you learn both algorithms on a conceptual level first if you have not already. It will help you as you are implementing them. Wikipedia is a good source for the basic knowledge of how a graph gets traversed with each algorithm.

DFS: http://en.wikipedia.org/wiki/Depth_first_search
BFS: http://en.wikipedia.org/wiki/Breadth-first_search

Additionally, the Design and Analysis of Algorithms Part I on Coursera that I showed you earlier has video lectures on both BFS and DFS as well as pseudocode implementations of each. Both algorithms are pretty intuitive, so don’t expect to not understand it or something.

However, you need to know what a Stack and a Queue are. Stacks are used in DFS while Queues are used in BFS. It’s imperative that you know both of those before attempting to implement them (especially for BFS).

As far as problems on CodeChef that are only DFS/BFS, I don’t know any since I don’t participate in the practice section too often. However, I do know that the problem CHEFHACK on the January Challenge did require DFS (but it was a flood-fill implementation, so I suggest you hold off on this problem until you are a bit more solid on the implementations of each).

TopCoder has a nice tutorial on DFS and BFS. It also gives you three practice problems. Unfortunately, they’re also fairly advanced for a beginner.

The only place I know of with DFS/BFS problems for beginners is the USACO Training Gateway. If you have an account there, I can point out which ones you should do.

3 Likes

These links have some problems:

TopCoder Forums

CodeForces Forums

CodeForces Forums

What i do is find questions tagged with some concept.

sort them in decreasing order of no of views, and other parameters of your choice. start solving, because the questions having more views are tend to be easier or interesting most of the time. so here is the list of increasing order of difficulty!!!
Happy coding. :slight_smile:

@kullalok Which section is the one that has graph theory on USACO Training pages ? Also, is there a way to access content from further sections without completing previous ones ?