Grafy i algorytmy grafowe

Graf skierowany niezawierający cyklu skierowanego; umożliwia sortowanie topologiczne wierzchołków.

Zachłanny algorytm wyznaczający najkrótsze ścieżki z jednego źródła w grafie o nieujemnych wagach krawędzi.

Ścieżka między dwoma wierzchołkami grafu ważonego o najmniejszej sumie wag krawędzi.

Struktura złożona ze zbioru wierzchołków oraz zbioru krawędzi łączących pary wierzchołków, modelująca relacje między obiektami.

Graf, w którym każdej krawędzi przypisano liczbową wagę, np. koszt lub odległość.

Element grafu łączący parę wierzchołków i reprezentujący relację między nimi.

Podstawowy element grafu reprezentujący obiekt; krawędzie łączą pary wierzchołków.

Algorytm przeglądania grafu zagłębiający się maksymalnie wzdłuż każdej gałęzi przed nawrotem do nieodwiedzonych wierzchołków.

Algorytm przeglądania grafu odwiedzający wierzchołki warstwami według rosnącej odległości od źródła.

Liniowe uporządkowanie wierzchołków grafu acyklicznego skierowanego zgodne z kierunkiem wszystkich krawędzi.

Reprezentacja grafu, w której dla każdego wierzchołka przechowuje się listę jego sąsiadów.

Reprezentacja grafu w postaci macierzy kwadratowej, której element wskazuje obecność krawędzi między parą wierzchołków.

Maksymalny zbiór wierzchołków grafu skierowanego, w którym każdy jest osiągalny z każdego innego.

Maksymalny podzbiór wierzchołków grafu wzajemnie osiągalnych przez ścieżki, wraz z łączącymi je krawędziami.