data-structures
Grafiek doorkruisen

Invoering

Diepte eerste zoekopdracht

Depth First Traversal (of Search) voor een grafiek is vergelijkbaar met Depth First Traversal van een boom. De enige vangst hier is, in tegenstelling tot bomen, dat grafieken cycli kunnen bevatten, dus we kunnen weer naar hetzelfde knooppunt komen. Om te voorkomen dat een knoop meer dan eens wordt verwerkt, gebruiken we een booleaanse bezochte array.

Onderstaand algoritme presenteert de stappen voor grafiekverplaatsing met behulp van DFS:

Algoritme DFS (v);

Input : een hoekpunt v in een grafiek

Output : Een label van de randen als "ontdekkingsranden" en "ruggen"

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

Breedte eerste zoekopdracht

Algoritme BFS (G)

Invoer grafiek G

Uitvoeretikettering van de randen en verdeling van de hoekpunten van 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)