What are the most important algorithms needed to solve graph problems?

Source: https://www.quora.com/What-are-the-most-important-algorithms-needed-to-solve-graph-problems

Graphs is an interesting topic as such. Even more, the concepts and algorithms used to tackle graph problems are elegant. Compiling a list of graph theory concepts would  be a lot tedious but if your focus is on sport programming then I might make sense.

My pick would be:

0. The basics – graph notations, graph representations

1. graph traversal (BFS / DFS ) – perhaps the most versatile topic in graph theory. Just look at the applications of these methods, both have their own unique properties.

2. Shortest Path (Dijkstra / Bellman Ford / Floyd-Warshall)

3. Minimum spanning trees (Prim’s / Kruskal’s)

4. Euler tour trees

5. Lowest Common Ancestor (LCA algo : I, II, III, IV)

6. Min cut / Max Flow / Matching : topcoder

7. Strongly connected components : SCC

8. Articulation points and edges : Explanation of Algorithm for finding articulation points or cut vertices of a graph

Also there are some optimization techniques like Heavy light decomposition

These are the basics of graph to get on with graph questions.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.