I have Graph-phobia. How do I overcome it?

I always try to ignore graph related questions during contests. But I want to overcome this fear of graphs. What should I do? From where should I start? and is it good to copy paste ready made graph functions from internet (like bfs,dijkstra) and use in my code?

13 Likes

First read about traversal ie BFS and DFS.And then try to implement it yourself.

also whenever you are solving graph problem try to use C++ STL(for EX. vector).,they will help you in implementing graph very fast.

For BFS & DFS watch this video http://www.youtube.com/watch?v=zLZhSSXAwxI and think how you can implement them(Hint:make good use of queue, stack and pair from STL).

When you are done with traversal its time to apply them.

Try to solve http://www.spoj.com/problems/PPATH/ using DFS.

and for BFS here solve this http://www.spoj.com/problems/CAM5/ .


here few more easy problem which you can solve using only BFS and DFS. http://www.codechef.com/JUNE14/problems/DIGJUMP
http://www.spoj.com/problems/PRATA/
http://www.spoj.com/problems/ONEZERO/
http://www.spoj.com/problems/PPATH/
http://www.spoj.com/problems/PARADOX/
http://www.spoj.com/problems/HERDING/
http://www.spoj.com/problems/PT07Z/
http://www.spoj.com/problems/NICEBTRE/
http://www.spoj.com/problems/CERC07K/
http://www.spoj.com/problems/BUGLIFE/
http://www.spoj.com/problems/COMCB/
http://www.spoj.com/problems/NAKANJ/
http://www.codechef.com/IOPC2013/problems/IOPC13N/
http://www.codechef.com/IOPC2013/problems/IOPC13G/
http://www.codechef.com/IOPC2013/problems/IOPC13C

Note: only after solving these problem proceed to other algorithm like dijsktra,prims,maxflow etc. because they will be lot easier then.

31 Likes

try this one:


It is a good question and requires knowledge of only bfs or dfs.

nice collection of graph problems…
there’s a lot of graph probs on uva hunting.Many of those are for beginners.

1 Like