data-structures
Diagrammdurchquerungen

Einführung

Tiefe erste Suche

Tiefes Durchqueren (oder Suchen) für ein Diagramm ähnelt dem Tiefsten Durchlauf eines Baums. Der einzige Haken ist hier, dass Diagramme im Gegensatz zu Bäumen Zyklen enthalten können, sodass wir möglicherweise wieder zu demselben Knoten kommen. Um zu vermeiden, dass ein Knoten mehr als einmal verarbeitet wird, verwenden wir ein boolesches besuchtes Array.

Der folgende Algorithmus zeigt die Schritte für die Diagrammdurchquerung mit DFS:

Algorithmus DFS (v);

Eingabe : Ein Scheitelpunkt v in einem Diagramm

Ausgabe : Eine Beschriftung der Kanten als "Discovery" -Kanten und "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

Breite erste Suche

Algorithmus BFS (G)

Eingabegraph G

Ausgang Beschriftung der Kanten und Teilung der Ecken von 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)