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.

Beispui

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.

Owendung

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

Schau aa

Literatua

Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, MIT Press, 2nd edition 2001, ISBN 0-262-53196-8
Stuart Russell, Peter Norvig: Artificial Intelligence: A Modern Approach, 2. Aflog, 2002, Prentice Hall.

Im Netz

Commons: Diafnsuach – Sammlung vo Buidl, Videos und Audiodateien