[Python-de] Kleine Aufgabe, große Wirkung

[Walter Dörwald]

Martin v. Löwis wrote:

> Michael Janssen wrote:
> 
>> wieviel Sinn macht so ein Baum? Sag es mir bitte einer, denn ich bin kein
>> Informatikstudent.
> 
> 
> Typisches Beispiel: Ein Dateibaum. Wurzelverzeichnis (C:\, oder /), 
> Unterverzeichnisse (\WINNT oder /usr). Sortierkriterium: Keines, ausser
> vielleicht der Ordnunssinn der Systemautoren.
> Suchaufgabe: Finde alle Dateien, die am 23.12.2001 geändert wurden.
> 
> "Breite zuerst" ist hier Geschmacksfrage, weil es z.B. als schöner
> empfunden wird, wenn die kurzen Pfadnamen zuerst rauskommen.

Ein sinnvolleres Beispiel ist etwa folgendes: Du willst beginnend von
einer Web-URL den Links auf der Web-Seite folgend eine komplette Website
absaugen, du willst Dich aber auf maximal 1000 Seiten beschränken.
Dann macht es Sinn den Durchlauf durch die Webseiten als breadth-first
(d.h. per Queue) statt als depth-first-Algorithmus (d.h. rekursiv)
zu implementieren, da es wohl wenig Sinn macht, dem ersten Link auf
der ersten Seite 999 Links weit hinterherzurennen und die anderen
unberücksichtigt zu lassen. Mit breath-first erhält man für alle
Links ungefähr dieselbe Linktiefe.

Ein anderer interessanter Nebeneffekt ist, daß es bei depth-first
passieren kann, daß man nachdem man eine Webseite besucht hat, beim
zweiten Auftauchen eines Links dies evtl. über einen kürzeren Pfad
passieren kann als beim ersten. Bei breath-first Durchlauf ist das
erste Auftreten eines Links zugleich auch das mit dem kürzesten
Pfad.

breath-first Bäume zu durchlaufen kann also durchaus ein Problem
sein, das in der Programmierpraxis auftritt.

Bis demnächst,
    Walter Dörwald