Nr 01 · Słownik · Teoria informatyki · Algorytmy i struktury danych

Grafy i algorytmy grafowe

14 pojęć w 6 podgrupach, z prostymi definicjami i źródłami.

Klasy grafow · 1

  • 01graf acykliczny skierowanyDAGGraf skierowany niezawierający cyklu skierowanego; umożliwia sortowanie topologiczne wierzchołków.

Najkrotsze sciezki · 2

  • 01algorytm DijkstryZachłanny algorytm wyznaczający najkrótsze ścieżki z jednego źródła w grafie o nieujemnych wagach krawędzi.
  • 02najkrótsza ścieżkaŚcieżka między dwoma wierzchołkami grafu ważonego o najmniejszej sumie wag krawędzi.

Podstawy grafow · 4

  • 01grafStruktura złożona ze zbioru wierzchołków oraz zbioru krawędzi łączących pary wierzchołków, modelująca relacje między obiektami.
  • 02graf ważonyGraf, w którym każdej krawędzi przypisano liczbową wagę, np. koszt lub odległość.
  • 03krawędźElement grafu łączący parę wierzchołków i reprezentujący relację między nimi.
  • 04wierzchołekwęzełPodstawowy element grafu reprezentujący obiekt; krawędzie łączą pary wierzchołków.

Przeszukiwanie grafu · 3

  • 01przeszukiwanie w głąbDFSAlgorytm przeglądania grafu zagłębiający się maksymalnie wzdłuż każdej gałęzi przed nawrotem do nieodwiedzonych wierzchołków.
  • 02przeszukiwanie wszerzBFSAlgorytm przeglądania grafu odwiedzający wierzchołki warstwami według rosnącej odległości od źródła.
  • 03sortowanie topologiczneLiniowe uporządkowanie wierzchołków grafu acyklicznego skierowanego zgodne z kierunkiem wszystkich krawędzi.

Reprezentacje grafow · 2

  • 01lista sąsiedztwaReprezentacja grafu, w której dla każdego wierzchołka przechowuje się listę jego sąsiadów.
  • 02macierz sąsiedztwaReprezentacja grafu w postaci macierzy kwadratowej, której element wskazuje obecność krawędzi między parą wierzchołków.

Struktury w grafie · 2

  • 01silnie spójna składowaSCCMaksymalny zbiór wierzchołków grafu skierowanego, w którym każdy jest osiągalny z każdego innego.
  • 02spójna składowaMaksymalny podzbiór wierzchołków grafu wzajemnie osiągalnych przez ścieżki, wraz z łączącymi je krawędziami.

Pozostałe grupy — Algorytmy i struktury danych

Grupa pojęć · Algorytmy i struktury danych14 haseł