data-structures
Attraversamenti grafici

introduzione

Profondità prima ricerca

Profondità Primo attraversamento (o ricerca) per un grafico è simile alla profondità Prima traversa di un albero. L'unica presa qui è, a differenza degli alberi, i grafici possono contenere cicli, quindi possiamo tornare allo stesso nodo. Per evitare l'elaborazione di un nodo più di una volta, usiamo un array visitato booleano.

Al di sotto dell'algoritmo vengono illustrati i passaggi per attraversare il grafico utilizzando DFS:

Algorithm DFS (v);

Input : un vertice v in un grafico

Uscita : un'etichetta dei bordi come bordi di "scoperta" e "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

Larghezza Prima ricerca

Algoritmo BFS (G)

Grafico di immissione G

Etichetta di uscita dei bordi e partizione dei vertici di 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)