Graph Representations and Algorithms Comparison

Implementation of two graph representations and few algorithms with comparison of how fast they perform.

Author: Bartosz Rodziewicz

The task done as a second project for Algorithms and Computational Complexity (Struktury danych i złożoność obliczeniowa, yes, that is official English translation).

The task was to implement a way to store graphs in the app using these two representations:

• Incidence Matrix
• Adjacency List

And implement 5 following algorithms:

• Minimum Spanning Tree
  • Prim's algorithm
  • Kruskal's algorithm
• Shortest Path
  • Dijkstra's algorithm
  • Bellman–Ford algorithm
• Max Flow
  • Ford–Fulkerson algorithm
    • with depth-first search
    • with depth-first and breadth-first search

Using STL or Boost libraries was taken as a disadvantage.

My app covers the most basic solution so I implement both ways of storing graphs using STL structures and two algorithms:

• Prim's algorithm
• Dijkstra's algorithm