Graph Algorithms in Competitive Programming

general
, ,
1

Is graph an important topic in Competitive Programming?
If yes, what are the algorithms that are frequently asked ?

EDIT :- I did googling and found some awesome stuff on graphs . I am sharing it with you all. Hope it might be helpful.

1 : Hopcroft–Karp algorithm : An algorithm that takes as input a bipartite graph and produces as output a maximum cardinality matching.

2 : Ford–Fulkerson algorithm : Maximum possible flow from source to destination.

3 : Breadth-first search : Searching or traversing in a graph

4 : Depth-first search : Traversing or searching tree or graph data structures

5 : Floyd-Warshall ALgorithm : Shortest path algorithm

6 : Dijkstra’s algorithm : Single-source shortest-path problem when all edges have non-negative weights.

7 : Prim’s algorithm : Minimum Spanning Tree

8 : Kosaraju’s algorithm : Problem of finding connected components

9 : Hungarian algorithm : Assignment problem

10 : Topological sorting : Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering.

11 : Minimum spanning tree : An edge-weighted graph is a graph where we associate weights or costs with each edge. A minimum spanning tree (MST) of an edge-weighted graph is a spanning tree whose weight (the sum of the weights of its edges) is no larger than the weight of any other spanning tree.

12 : Priority queue : In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

13 : Kruskal’s algorithm : Minimum Spanning Tree Algorithm

14 : PageRank algorithm : The Mathematics of Google Search

15 : Coloring algorithm : It is an assignment of labels traditionally called “colors” to elements of a graph subject to certain constraints.

14 Likes
2

Yes it is quite important. Basic algorithms like bfs, dfs Djikstra’s algorithm, floyd-warshal etc should be known to you.

2 Likes
3

Yes, it is important topic…
Basically, in last AUG14 contest … 1 question is directly base on dijsktra algo… so, Graph is important topic.

BFS , DFS, Dijsktra and etc. algo

8 Likes
4

Hi, the latest and the most interesting graph problems you will see are often the hidden ones.

For example, the following problem is really nice (I don’t know the source though):

Given a NxM grid, where a ‘.’ represents water, ‘*’ represents ice, ‘P’ represents a penguin and ‘S’ represents a safe place. For example the grid can look like this:

**S.*
P**P*
.P**.

A penguin can only move down, up, left and right. It can not step into the water and can only step on to the ice. If a penguin moves from x to y, then ice x will disappear. We must find an optimal plan to safe the maximum number of penguins by moving them to the safe place.

Can you spot the well known graph problem?

To solve such hidden graph problems, it requires some elementary graph algorithms, which you can find in “Introduction to Algorithms” by Cormen.

4 Likes
5

Generally, Dijktra’s and prim’s(or kruskal’s) algorithm are quite helpful in solving Graph problems.

16 Likes
6

@vikasnitt:

Very Useful links … Thnx for Sharing! :slight_smile:

2 Likes
7

Please update these links the don’t work anymore.

1 Like
8

Nice links! But it’s also nice to know some algorithms specifically designed for a special graph. For example, LCA (lowest common ancestor) is something, which you have in trees and there exists O(n log n) algorithms for preprocessing them.

9

gdisadtery, yeah that also can be done. I will update the answer as soon as I get the the problems. If you also have some links then please edit this.

1 Like
10

Sorry I cannot edit, but Topcoder seems to have good resources.

11

Nice links. I followed some links and it is given in full explanation. Please add some problems on the given algo also.

12

Yes, I will add some problems on this also. I request you If you get some good prob then edit this.

13

I followed some links. The tutorials are very helpful. Thanks a lot. :slight_smile: Please add some problems also.