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 ...
Get Algorithmische Graphentheorie, 4th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
