September 2015
Intermediate to advanced
415 pages
12h 24m
German

KAPITEL 4
Suchverfahren in Graphen
In diesem Kapitel werden Suchstrategien für Graphen behandelt. Sie bilden die Grundlage für viele graphentheoretische Algorithmen, in denen die Ecken oder Kanten systematisch durchlaufen werden müssen. In Kapitel 3 wurde dies bereits für Suchbäume abgehandelt. Die vorgestellten Suchstrategien Tiefensuche und Breitensuche verallgemeinern diese Techniken, so dass sie aufbeliebige Graphen anwendbar sind. Es wird zunächst das Grundprinzip der Tiefensuche vorgestellt. Danach werden Anwendungen der Tiefensuche auf gerichtete Graphen diskutiert: Topologische Sortierungen, Bestimmung der starken Zusammenhangskomponenten ...