Program implementujący dwie reprezentacje grafu:

• Macierz Incydencji
• Lista Sąsiedztwa

Dla każdej z nich:

• algorytm Prima oraz algorytm Kruskala,
• algorytm Dijkstry oraz algorytm Forda-Bellmana,
• algorytm Forda-Fulkersona

Ponadto:

• Ograniczyć wykorzystanie bibliotek, całkowicie wykluczyć STL
• umożliwić tworzenie grafu spójnego na podstawie pliku oraz danych losowych (przy podanej liczbie wierzchołków oraz gęstości wypełnienia)
• zaimplementować precyzyjne odmierzanie czasu, na podstawie których powstanie analiza algorytmów w sprawozdaniu
• umożliwić wyświetlenie podglądu zawartości grafu dla obu reprezentacji
• dynamiczna alokacja pamięci

Przykład ważonej skierowanej macierzy incydencji oparty na założeniach opisanych w artykule.

$ \begin{bmatrix} 6 & 1 & 0 & 0 & 0 \[1em] -6 & 0 & -8 & 0 & 0 \[1em] 0 & -1 & 8 & 9 & -3 \[1em] 0 & 0 & 0 & -9 & 3 \[1em] \end{bmatrix} $

Implementacja dynamicznej Macierzy Incydencji w C++ przy wykorzystniu wskaźników na tablicę wskaźników (wytłumaczone w tym filmie)