Minimaler Spannbaum SS12
Aus ProgrammingWiki
Archivierte Version vom 2012-03-13T09:11:59+00:00. Aktuelle Version
Inhaltsverzeichnis |
Wozu?
Minimale Spannbäume können für viele Probleme genutzt werden. Ein Problem, dass man mit MST lösen kann ist das verbinden mehrerer Inseln mit Brücken. Man möchte, dass alle Inseln miteinander verbunden sind und die Brücken minimale Länge haben und damit minimale Kosten entstehen. Dabei sollen die Inseln so verbunden werden, dass man alle Inseln über die Brücken berreisen kann und keine redundanten Brücken entstehen. Redundante Brücken sind Brücken mit der man eine Insel erreicht, die man auch über einen anderen ggf. längeren Weg hätte erreichen können. Längerer Weg heißt in diesem Fall, dass man über (eine) andere Brücke(n) reisen muss um die Insel zu erreichen.