data-structures
Grafversioner

Introduktion

Djup första sökning

Djup First Traversal (eller Sök) för en graf liknar Djup First Traversal av ett träd. Den enda fångsten här är, till skillnad från träd, kan grafer innehålla cykler, så vi kan komma till samma nod igen. För att undvika att bearbeta en nod mer än en gång använder vi en boolesisk besökt matris.

Nedanstående algoritm presenterar stegen för grafversion med DFS:

Algoritm DFS (v);

Input : Ett toppunkt v i en graf

Output : En märkning av kanterna som "upptäckt" kanter och "backs"

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

Utöka första sökningen

Algoritm BFS (G)

Inmatning graf G

Utmatningsmärkning av kanterna och uppdelningen av vertikalerna i 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)