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.