Recap and Next Steps

Recap

Congratulations on finishing this course on graph algorithms in C++! Let’s recap what we learned in each chapter.

• First, we discovered the fundamental concepts and terminology of graph theory, such as directed, undirected, and weighted graphs.
• Next, we explored how graphs can be represented as data structures in programs, using adjacency lists and adjacency matrices.
• We traversed graphs using BFS and DFS and studied applications of graph traversal, such as computing strongly connected components.
• We also computed shortest paths in weighted graphs using Dijkstra’s algorithm and the Floyd-Warshall algorithm.
• We found optimal spanning trees using Kruskal’s algorithm.
• Finally, we solved flow problems using the Ford-Fulkerson method and applied it to find maximum bipartite matchings.

Next steps

With the foundational knowledge of this course under your belt, you’ll be able to explore further topics of graph algorithms or dive deeper into rich fields such as max-flow algorithms. Below are some suggestions for further topics to check out next.

Eulerian trails

Take a closer look at the eulerian trail problem, which was explored in the introductory lesson, and implement efficient algorithms for this problem, such as Fleury’s algorithm or Hierholzer’s algorithm.

General matchings

We applied flow problems to solve the maximum matching problem in bipartite graphs. However, there are also more difficult variants of matching problems that need more complex algorithms to solve them efficiently. Some examples are computing maximum matchings non-bipartite graphs or even computing maximum weighted matchings in weighted graphs.

Traveling salesmen

Explore the Hamiltonian Cycle problem and its weighted variant, the Traveling Salesman problem (TSP). The objective of these problems is to find a cycle that visits all nodes and has minimal weight.