Efficient way to practice graph theory algorithms

Question

I just read about the breadth-first search algorithm in the Introduction to Algorithms book and I hand simulated the algorithm on paper. What I would like to do now is to implement it in code for extra practice.

I was thinking about implementing all the data structures from scratch (the adjacency list, the "color", "distance", and "parent" arrays) but then I remembered that there are currently graph libraries out there like the Boost graph library and some other graph APIs in Python. I also tried looking for some BFS-related problems on UVA and Sphere Judge Online but I can't tell which problems would require a BFS solution.

My question is what would be the most painless way to practice these graph algorithms (not just limited to BFS, but will also come in useful when I want to implement DFS, Dijkstra, Floyd-Warshall, etc). Sites with practice problems are welcomed.

Answer 1

I personally think that the best way to understand those would be implementing the graph representation yourself from scratch.

On the one hand, that would show you actual implementation caveats from which you learn why or why not a particular algorithm might be interesting / good / efficient / whatever. On the other hand, I think that understanding graphs and their real life use, including its implications (recursion, performance/scalability, applications, alternatives, ...), is made easier through the bottom-up approach.

But maybe that's just me. The above is very personal taste.

Answer 2

I found your question interesting, I googled a bit and I found JGraphEd.

It does not cover all graph algorithms but it looks like a good tool for experimentation.

Answer 3

I agree with balpha. The best way to really learn and understand algorithms is to do the implementation. Just pick an algorithm and implement it. When you reach a point where you get stuck or are unsure, look at a number of existing examples. You will then be able to compare your own thinking with that of others from a position of understanding instead of simply accepting what is offered.

Once you have learned what you want to, the best way to solidify your understanding is to try teach it to or describe it to somebody else. You might have some people willing to listen to you, or at the very least you could write a blog entry for people new to the algorithm you have just studied.

But if you are looking for "painless", then maybe you should stay clear of algorithms altogether ;-)

Answer 4

This site could help you

Here you have description of every problem on acm problemset. You can see category of each problem, and hint to solve it. Just browse for graph related problems. Good advice is to use those hints only if you tried to solve problem yourself and failed.