Basic Graph Algorithms

Does the graph algorithms like BFS,DFS,Dijkstra are enough for programming competetions ? Because I have been searching for the graph algorithms and I found only these 3 mostly.If these are not sufficient then please suggest some new algorithms with reading material which is easy to understand.

BFS and DFS algorithms are basically used for graph traversals. Atleast You must know these algorithms to crack a problem based on graph theory. Most of the sums are based on graph traversals only. To compute in O(n+m) you must represent the graph as adjacency list. If you represent in adjacency matrix it will be computed in O(n^2). here ‘n’ and ‘m’ are nothing but vertices and edges respectively. and also adjacency matrix takes O(n^2) memory too.

1 Like

Yes I Know, my intention is it required to know new algorithms like MaxFlow and MinFlow,…

yeah! MinCost MaxFlow and MaxCost MinFlow are also required

Can you suggest resources which is easy to understand(apart from TopCoder)

I think this link(http://en.wikipedia.org/wiki/Edmonds–Karp_algorithm) will be helpfull to you in understanding… for video lecture this(http://www.youtube.com/watch?v=UtSrgTsKUfU) and this(http://www.youtube.com/watch?v=J0wzih3_5Wo). It might be boring but be patience to look at these tutorials.

Yes sure and thank’s a lot for the help !

Check this thread

This thread will really help u and if any doubt then ask on it.

Follow the above blog it contains graph algorithms which are mostly used in cp.

Thank You :slight_smile: