Do you understand the graphity of this situation

1. Introduction to Graph theory

Many programming problems can be solved by modeling them as graph problems and using appropriate graph algorithms. A typical example of a graph is a network of roads and cities in a country. Sometimes though, the graph is hidden in the problem and it may be difficult to detect it.

Reading material:

• CPH Ch 11, pg 109 - 116
• Hackerearth [B]
• A collection of several graph algorithms
• Basic Problems - E-Olymp Graph representation

  2. Graph traversal

i. Depth First Search (DFS)

Reading material:

• CPH Ch 12, pg 117 - 118
• Hackerearth [B]
• CP Algorithms
• Basic Problems - E-Olymp DFS
• DFS Applications
  • CPH Ch 12, pg 121 - 122
  • -is-this-fft-‘s legendary blog on CF (for later reading)

ii. Breadth First Search (BFS)

Reading material:

• CPH Ch 12, pg 119 - 120
• Hackerearth [B]
• CP Algorithms
• Basic Problems - E-Olymp BFS

3. Shortest paths

i. Bellman-Ford Algorithm

Reading material:

• CPH Ch 13, pg 123 - 126
• CP Algorithms

ii. Dijkstra’s Algorithm

Reading material:

• CPH Ch 13, pg 126 - 129
• CP Algorithms
  • Dijkstra Algorithm
  • Dijkstra on sparse graphs

iii. Floyd-Warshall Algorithm

Reading material:

• CPH Ch 13, pg 129 - 131
• CP Algorithms

4. Spanning Trees

i. Disjoint Set Union or Union Find

Reading material:

• CPH Ch 15, pg 145 - 147
• CS Academy [B]
• CP Algorithms
• CF EDU on Disjoint Set Union

ii. Kruskal’s Algorithm

Reading material:

• CPH Ch 15, pg 141 - 145
• CP Algorithms
  • Kruskal’s Algorithm
  • Kruskal with DSU

iii. Prim’s Algorithm

Reading material:

• CPH Ch 15, pg 147 - 148
• CP Algorithms