Wprowadzenie

Witamy w serii Algorytmy grafowe! Graf to zbiór wierzchołków połączonych krawędziami; może modelować wszystko — od map drogowych po sieci społecznościowe.

Zaczynamy od przeszukiwania w głąb (DFS), jednej z dwóch podstawowych metod eksplorowania grafu. DFS zagłębia się tak daleko, jak to możliwe, wzdłuż każdej gałęzi, zanim się cofnie i spróbuje kolejnej.

W całej tej serii graf jest przekazywany w następującej postaci:

• n — liczba wierzchołków, ponumerowanych od 0 do n - 1.
• edges — płaska tablica, w której każda kolejna para reprezentuje nieskierowaną krawędź: [u0, v0, u1, v1, ...].

Ten kurs obejmuje teorię, implementację, którą zbudujesz samodzielnie, oraz wyzwania do przećwiczenia. Zaczynajmy!