Przeszukiwanie w gląb

Przeszukiwanie w głąb (ang. Depth-first search, w skrócie DFS) – w informatyce algorytm przeszukiwania grafu używany do przechodzenia lub przeszukiwania drzewa lub grafu. Przeszukiwanie zaczyna się od korzenia i porusza się w dół do samego końca gałęzi, po czym wraca się o jeden poziom i próbuje kolejne gałęzie itd.

Pseudokod wersji z rekurencją:

dfs (graf G)
{
    czas <- 0

    for każdy wierzchołek v należący do G
    {
        kolor[v] <- BIAŁY
        poprzednik[v] <- NIL
        odwiedzenie[v] <- NIL
        przetworzenie[v] <- NIL
    }

    for każdy wierzchołek v należący do G
    {
        if kolor[v] = BIAŁY
        {
            dfs-visit(v)
        }
    }
}

dfs-visit (wierzchołek v)
{
    kolor[v] <- SZARY
    odwiedzenie[v] <- czas <- czas + 1

    for każdy wierzchołek u będący sąsiadem v
    {
        if kolor[u] = BIAŁY
        {
            poprzednik[u] <- v
            dfs-visit(u)
        }
    }

    kolor[v] <- CZARNY
    przetworzenie[v] <- czas <- czas + 1
}

Realizacja przeszukiwanie w głąb z rekurencją w c++
Plik spakowany do formatu zip: recursion_dfs

Pseudokod wersji bez rekurencji:

dfs (graf G)
{
    czas <- 0
    S <- NIL

    for każdy wierzchołek v należący do G
    {
        kolor[v] <- BIAŁY
        miejsce[v] <- 0
        poprzednik[v] <- NIL
        odwiedzenie[v] <- NIL
        przetworzenie[v] <- NIL
    }

    for każdy wierzchołek v należący do G
    {
        if kolor[v] = BIAŁY
        {
            dfs-visit(v)
        }
    }
}

dfs-visit (wierzchołek v)
{
    kolor[v] <- SZARY
    dodaj v do stosu S
    odwiedzenie[v] <- czas <- czas + 1

    while S nie jest pusty
    {
        v <- wierzchołek ze szczytu stosu S

        for każdy wierzchołek u będący sąsiadem v
        {
            miejsce[v] <- miejsce[v] + 1
            if kolor[u] = BIAŁY
            {
                kolor[u] <- SZARY
                poprzednik[u] <- v
                dodaj u do stosu S
                odwiedzenie[u] <- czas <- czas + 1
                break
            }
        }

        if miejsce[v] = stopień wierzchołka v
        {
            kolor[v] <- CZARNY
            zdejmij wierzchołek ze stosu S
            przetworzenie[v] <- czas <- czas + 1
        }
    }
}

Realizacja przeszukiwanie w głąb bez rekurencji w c++
Plik spakowany do formatu zip: dfs