Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


30. Zusammenhang



Die grundlegende Prozedur der Tiefensuche aus dem vorangegangenen Kapitel findet die zusammenhängenden Komponenten eines gegebenen Graphen; im vorliegenden Kapitel wollen wir damit verwandte Algorithmen und Probleme, die andere Eigenschaften des Zusammenhangs von Graphen betreffen, untersuchen.

Nach der Betrachtung einiger unmittelbarer Anwendungen der Tiefensuche zur Gewinnung von Informationen über den Zusammenhang gehen wir auf eine Verallgemeinerung des Zusammenhangs ein, die zweifacher Zusammenhang (biconnectivity) genannt wird. Hierbei interessieren wir uns dafür, ob mehr als ein Weg existiert, um von einem Knoten in einem Graph zu einem anderen zu gelangen. Ein Graph ist zweifach zusammenhängend dann und nur dann, wenn es wenigstens zwei verschiedene Pfade gibt, die jedes Paar von Knoten verbinden. Demzufolge ist der Graph selbst dann, wenn ein Knoten und alle von ihm ausgehenden Kanten entfernt werden, immer noch zusammenhängend. Wenn es für eine bestimmte Anwendung wichtig ist, daß ein Graph zusammenhängend ist, könnte es auch wichtig sein, daß er zusammenhängend bleibt. Die Lösung für dieses Problem ist ein Algorithmus, der wesentlich komplizierter ist als der Traversierungsalgorithmus aus dem vorangegangenen Kapitel, doch auch er beruht auf der Tiefensuche.

Eine spezielle Variante des Zusammenhangsproblems, die häufig auftritt, betrifft eine dynamische Situation, in der Kanten nacheinander zum Graph hinzugefügt werden, wobei Anfragen eingestreut werden, ob zwei bestimmte Knoten der gleichen zusammenhängenden Komponente angehören oder nicht. Dies ist ein gründlich erforschtes Problem, und wir werden zwei entsprechende »klassische« Algorithmen dafür ausführlich untersuchen. Die Verfahren sind nicht nur einfach und vielfältig anwendbar, sondern sie veranschaulichen auch, wie schwierig die Analyse einfacher Algorithmen sein kann. Das Problem wird manchmal »Vereinigungs-Suchproblem« genannt, eine Bezeichnung, die von der Anwendung der Algorithmen zur Ausführung einfacher Operationen auf Mengen von Elementen stammt.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]