Zum Inhalt springen

Diafnsuach

Aus Wikipedia
Diafnsuach

Diafnsuach (dt.: Tiefensuche, englisch: Depth-First Search) is in da Informatik a Vafoahn zan Suachn vo om Knotn in om Graphn. Se zejd za dena uninfoamiadn Suachalgorithmen. A Vabessarung vo da Diafnsuach is de iterative Diafnsuach.

Fia an foingdn Graphn:

A Diafnsuach fongd ba A o. Ognumma, doss de linkn Kantn in om Graphn voa dena rechtn Kantn gwejd wead und ognumma de Suach eainnad voahea bsuachde Knotn und dadat se ned wiedahoit bsuacha (es is jo a kloana Graph), donn dadatn de Knotn in da foingdn Reihnfoig bsuachd wean: A, B, D, F, E, C, G.

Wann de gleiche Suach duachgfiahd wead, ohne doss de voahea bsuachdn Knotn eainnad wean, fiahd des za da foingdn Bsuachsfrequenz A, B, D, F, E, A, B, D, F, E, usw. und bleibd ewig in da A, B, D, F, E Schleifn gfonga und eareichd nia ned C oda G.

Iterative Diafnsuach vameidd de Schleifn und dadat de näxdn Knotn vo da foingdn Diafnebane earreichn, wann ma onimmd, doss vo links noch rechts voagonga wead:

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

(Omeakung: A iterative Diafnsuach hed etzd C woahgnumma, de konventioneje Diafnsuach owa ned)

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

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

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

Fia an Beispui-Graphn guid: Je meaara Diafn dozuakimmd, wean de zwoa Kroas "ABFE" and "AEFB" oafoch länga bevoa da da Algorithmus afgibd und an ondan Zweig vasuachd.

De Diafnsuach is indirekd on vuin komplexan Algorithmen fia Graphn beteiigd. A Beispui is's Affindn vo oin stoakn Zammhongskomponentn vo am Graphn.

 Commons: Diafnsuach – Sammlung vo Buidl, Videos und Audiodateien