basic graph algo related problems

Can anyone provide me the list of problems related to graph algos like
1.BFS, DFS
2.Euler’s path
3.prim and kruskal for minimum spanning tree
4.dijkstra , bellman ford for shortest path
5.warshall
If there are more related algorithms please add it
If we can accumulate a list it would be great
Thank you :slight_smile:

6 Likes

Here are a few. I am excluding the algorithm that solves them in hopes that you will benefit from being able to identify which algorithm would be best to use in each case.

EDIT: @abeyaar Since you also requested problems from other websites I would like to point you to the UVA Online Judge but more specifically once you have an account you can access UHunt which offers a balanced and very well organized section on specifically graph problems(~250 problems only pertaining to graphs) covering all the topics you emphasized and more. You may even be interested in buying the corresponding book Competitive Programming 3, which is a great reference corresponding to the UVA problems.

If you want a better idea of this check out my profile here. If you scroll down past my statistics to the “Competitive Programming Exercises” on the right hand side of the screen you will see a box with a green heading and the 4th section will be labeled 4. Graph. From there click on the 2nd progress bar to show all 250 problems. That should be enough to keep you busy for a while. Enjoy!

EDIT: @abeyaar There is definitely a trade off when using UVA as a problem solving platform. You get a bulk of problems at the cost of well thought out editorials and nice discussion pages. I hope this can make you appreciate what CodeChef offers for its users a little bit more! This isn’t a completely negative thing though. If you push yourself and apply a little creativity UVA can be very rewarding. What I mean by this is don’t be discouraged by the lack of editorials use it an an opportunity to really test your coding skills. Now when I mention creativity I mean you should take advantage of UVA Toolkit which allows you to enter test cases for many of the questions on UVA and see what the correct output would be. This is definitely a great way to practice generating test cases and testing your solutions which are invaluable skills in actual contests where you aren’t able to ask other people what is wrong with your code.

Also remember that if you get stuck on a problem many people have likely solved the same problem and posted their approach and code on a blog or something similar and normally you can find a link to one of these after a quick Google search which you can use kind of like an editorial. If that fails you can always come here for help!

The Escape

The Kings Idea

Kingdom Unity

Coal Scam

Obstacle Course

Election Campaign

Greedy Trip

Delivery Boy

Codechef Password Recovery

9 Likes

@felic92 thanks a lot :slight_smile:

Codechef now provides the facility of tags…so searching of problems has become much more easier :slight_smile:
Graph related problems :

2 Likes

Thanks @re_hash :slight_smile:

It would be nice if someone can provide link to questions from other websites :slight_smile:

Woah!! Thats just what I needed thanks a ton !! :))

1 Like

As problems from other platforms are allowed, UVA was already suggested. So I will suggest

Keep practicing!

1 Like

Compiling all Graph related problem resources I know.

http://discuss.codechef.com/questions/7436/list-of-problems-to-practice-on-graph

http://www.stanford.edu/class/cs97si/assn6.html

http://www.stanford.edu/class/cs97si/assn7.html

https://groups.google.com/forum/#!msg/acm_guc/wHzFsJW5Ml8/y-9ZsA_hzgEJ

https://groups.google.com/forum/#!topic/acm_guc/QpWPNeVUcUA

Problem Classifiers

http://codeforces.com/problemset/tags/graphs

https://www.hackerrank.com/tracks/algorithms/graph-theory

http://problemclassifier.appspot.com/

http://www.codechef.com/tags/problems/graph

http://community.topcoder.com/tc?module=ProblemArchive

http://uhunt.felix-halim.net/

This one is quite famous (includes every problem domains for competitive programming)
https://docs.google.com/document/d/1MlbFmE6ji3Yb6mNmZDHcNIBiZzlhzf31iz2wUe3iS0M/edit?authkey=COyc9Uc&pli=1

For Learning Purposes:

http://machlearner.blogspot.in/2013/10/cpsig-week-3-basic-data-structures-and.html

http://www.geeksforgeeks.org/tag/graph/

Tell me more I ll add in this answer :slight_smile:

2 Likes

@felic92 the discuss pages of uva online judge are not easy to get…also I find no editorials for problems there :frowning:
But yes the problem quality is good there

1 Like

@felic92 http://uvatoolkit.com heres the link thanks :slight_smile:

1 Like

Fixed it, thanks.

Thanks @prakhs123

//