data-structures
Przejazdy przez wykres

Wprowadzenie

Głębokie pierwsze wyszukiwanie

Głębokość pierwszego przejścia (lub Wyszukaj) dla wykresu jest podobna do głębokości pierwszego przejścia drzewa. Jedynym haczykiem jest to, że w przeciwieństwie do drzew, wykresy mogą zawierać cykle, więc możemy ponownie dojść do tego samego węzła. Aby uniknąć przetwarzania węzła więcej niż jeden raz, używamy boolowskiej tablicy odwiedzin.

Poniższy algorytm przedstawia etapy przechodzenia przez wykres za pomocą DFS:

Algorytm DFS (v);

Dane wejściowe : wierzchołek v na wykresie

Wyjście: a oznakowanie krawędzi jak „odkrycie” krawędzi „i” backedges

for each edge e incident on v do

    if edge e is unexplored then

    let w be the other endpoint of e
    if vertex w is unexplored then
        label e as a discovery edge
        recursively call DFS(w)
    else
    label e as a backedge

Szerokość Pierwsze wyszukiwanie

Algorytm BFS (G)

Wykres wejściowy G

Wyjściowe etykietowanie krawędzi i podział wierzchołków G

    for all u ∈ G.vertices()
        setLabel(u, UNEXPLORED)
    for all e ∈ G.edges()
    setLabel
    (e, UNEXPLORED)
    for all v ∈ G.vertices()
        if getLabel(v) = UNEXPLORED
            BFS(G, v)