Diafnsuach

Aus Wikipedia
Wexln zua: Navigation, Suach
Diafnsuach

Diafensuach (Depth-First Search) is in da Informatik a Vaforn zum Suachn vo am Knotn in am Graphn. Se zäid zua dena uninformiatn Suachalgorithmen. A Vabessarung vo da Diafnsuach is de iterative Diafnsuach.

Beispui[VE | Weakln]

Fia an foigendn Graphn:

Graph.traversal.example.svg

A Diafnsuach fongt ba A o. Ognumma dass de linkn Kantn in am Graphn voa dena rechtn Kantn gwäid wead und ognumma de Suach eainnat voahea besuachte Knotn und dadat se ned wiedahoit besuacha (es is jo a kloana Graph), dann dadatn de Knotn in da foigenden Reihnfoig besuacht wean: A, B, D, F, E, C, G.

Wann de gleiche Suach duachfiat wead, ohne dass de voahea besuachtn Knoten eainnat wean, fiat des zua foigendn Besuachsfrequenz A, B, D, F, E, A, B, D, F, E, usw. und bleibt ewig ind da A, B, D, F, E Schleifn gfanga und eareicht nia C oda G.

Iterative Diafnsuach vameidet de Schleifn und dadat de nextn Knotn vo da foigendn Diafnebene earreichn, wann ma onimmt dass vo links noch rechts voaganga wead:

  • 0: A
  • 1: A (wiadahoit), B, C, E

(Omeakung: A iterative Diafnsuach häd etzt C worgnumma, de konventionelle Diafnsuach owa ned)

  • 2: A, B, D, F, C, G, E, F

(Omeakung: C wead worgnumma, owa. E wead iwa an ondan Weg worgnumma und F wead zwoamoi besuacht.)

  • 3: A, B, D, F, E, C, G, E, F, B

Fian an Beispui-Graphn guit: Je meara Diafn dazuakimmt, wean de zwoa Kroas "ABFE" and "AEFB" oanfoch länga bevoa da da Algorithmaus afgibt und an ondan Zweig vasuacht.

Owendung[VE | Weakln]

De Diafnsuach is indirekt an vuin komplexan Algorithmen fia Graphn beteiligt. A Beispui is des Affindn vo oin storkn Zammahangskomponentn vo am Graphn.

Schaug aa[VE | Weakln]

Literadua[VE | Weakln]

Im Netz[VE | Weakln]

 Commons: Diafnsuach – Sammlung vo Buidl, Videos und Audiodateien