 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Frank Mockenhaupt
Guest
|
 Posted: Thu Jan 26, 2006 8:40 pm Post subject: Kruskal-Algorithmus |
 |
|
Hallo;
Kann mir jemand ein paar Tipps geben wie ich den Kruskal-Algorithmus in
C++ umsetze?
Vielen Dank
MfG
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
 |
Christoph Rabel
Guest
|
| Posted: Fri Jan 27, 2006 12:38 am Post subject: Re: Kruskal-Algorithmus |
|
|
Frank Mockenhaupt wrote:
| Quote: | Hallo;
Kann mir jemand ein paar Tipps geben wie ich den Kruskal-Algorithmus in
C++ umsetze?
|
Hmm, falls du es nicht selber implementieren möchtest:
http://boost.org/libs/graph/doc/kruskal_min_spanning_tree.html
mfg
Christoph Rabel
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Carsten Krueger
Guest
|
|
| Back to top |
|
|
Boris Glawe
Guest
|
| Posted: Fri Jan 27, 2006 3:15 am Post subject: Re: Kruskal-Algorithmus |
|
|
Frank Mockenhaupt wrote:
| Quote: | Hallo;
Kann mir jemand ein paar Tipps geben wie ich den Kruskal-Algorithmus in
C++ umsetze?
|
Das hat eigentlich nichts mit der Sprache C++ zu tun.
Wenn ich mir den Algorithmus ansehe, dann kommen sehr viele Mengenoperationen vor.
Schreibe dir zunächst ein paar Klassen, die die beteiligten Objekte beschreiben:
Knoten, Kanten (als Paar von zwei Knoten mit Gewicht), vielleicht lohnt es sich,
einen Graphen G = (V,E) und die Mengen E und V als eigene Klassen zu
implementieren (um Operationen, wie "finde einen Kreis" zu kapseln) und fange
dann einfach an, den Algorithmus "abzuschreiben".
Am Anfang hast du den Graphen, der die Ausgangsmengen V und E enthält und eine
Objekt, dass die Kantenmenge E' enthält. Also einfach Objekte deiner eben
geschriebenen Klassen instanzieren.
In jedem Schritt fügst du der Kantenmenge E' etwas hinzu. Solche Operationen
sind Mengenoperationen, die man gerne mit den Containernklassen der STL (STL ==
standard template library) macht (http://www.cppreference.com/)
Operationen wie "finde einen Kreis" funktionieren so, dass du eine Tiefensuche
auf dem Graphen startest. In jedem Schritt der Tiefensuche schaust du, ober der
gerade besuchte Knoten schon in der Menge der besuchten Knoten enthalten ist.
Wenn ja, dann hast du einen Kreis. Genaueres dazu liefert dir Google.
Die Kantenmenge E' ist dann dein minimal überspannender Baum.
Fang am besten mal mit der Implementierung an. Ich bin mir sicher, dass du
schnell Fragen zur Benutzund der STL Klassen hast. Die kannst du dann hier
stellen. Bis jetzt klingt deine Frage aber mehr nach "Bitte macht mir meine
Hausaufgaben".
Was du also lernen musst:
- Umgang mit der STL
- rekursives Programmieren für Tiefensuche im Graphen. (ist nicht einfach am
Anfang, lohnt sich aber zu lernen)
Grüße Boris
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Dietmar Kuehl
Guest
|
| Posted: Fri Jan 27, 2006 6:02 am Post subject: Re: Kruskal-Algorithmus |
|
|
Frank Mockenhaupt wrote:
| Quote: | Kann mir jemand ein paar Tipps geben wie ich den Kruskal-Algorithmus in
C++ umsetze?
|
Der wichtigste Schritt für die Implementierung von Algorithmen, ist,
sie mit den richtigen Abstraktionen zu realisieren, damit die fertigen
Algorithmen nicht spezifisch für eine Datenstruktur sind und jedesmal
geändert werden müssen, wenn sich die Datenstruktur ändert.
Für Graphen allgemein besteht eine solche Abstraktion aus folgenden
Konzepten:
- Node-Iterator, um auf alle Knoten zuzugreifen
- Edge-Iterator, um auf alle Kanten zuzugreifen
- Incidence-Iterator für alle Kanten an einem Knoten
- Property-Maps für die Gewichte an Knoten und Kanten
Im Fall von Kruskal's Algorithmus braucht man nur den Edge-Iterator
und passende Property-Maps (eine für das Gewicht der Kanten und eine,
um den Representanten der Knotenmenge darzustellen; letzterer ist
auch dasjenige Objekt, in dem man die Union/Find-Datenstruktur
realisieren kann).
Auf einer solchen Basis läßt sich Kruskal's Algorithmus ziemlich
einfach implementieren und leicht an verschiedene Datenstrukturen
anbinden. In Boost's Graph Library (BGL) ist das wohl auch so
ungefähr gemacht.
--
<mailto:dietmar_kuehl (AT) yahoo (DOT) com> <http://www.dietmar-kuehl.de/>
<http://www.eai-systems.com> - Efficient Artificial Intelligence
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
Jens Müller
Guest
|
| Posted: Sat Feb 11, 2006 12:06 am Post subject: Re: Kruskal-Algorithmus |
|
|
Boris Glawe schrieb:
| Quote: |
Am Anfang hast du den Graphen, der die Ausgangsmengen V und E enthält
und eine Objekt, dass die Kantenmenge E' enthält. Also einfach Objekte
deiner eben geschriebenen Klassen instanzieren.
In jedem Schritt fügst du der Kantenmenge E' etwas hinzu. Solche
Operationen sind Mengenoperationen, die man gerne mit den
Containernklassen der STL (STL == standard template library) macht
(http://www.cppreference.com/)
Operationen wie "finde einen Kreis" funktionieren so, dass du eine
Tiefensuche auf dem Graphen startest. In jedem Schritt der Tiefensuche
schaust du, ober der gerade besuchte Knoten schon in der Menge der
besuchten Knoten enthalten ist. Wenn ja, dann hast du einen Kreis.
Genaueres dazu liefert dir Google.
|
Hab da jetzt nicht so genau drüber nachgedacht, aber könnte das nicht
leicht ineffizient werden, in jedem Schritt (also bei jedem _Versuch_,
eine Kante hinzuzufügen) eine Tiefensuche auf dem gesamten Graphen zu
machen?
Dann doch eher das ganze als Union-Find-Anwendung auffassen: Am Anfang
ist jeder Knoten seine eigene Menge, hinzufügen einer Kante bedeutet
Union der entsprechenden Mengen. Prüfen, ob Hinzufügen der Kante
zulässig ist, funktioniert so, daß für beide inzidenten Knoten die Menge
bestimmt wird und auf Gleichheit geprüft wird. Mengen entsprechen also
immer zusammenhängenden Teilgraphen.
Ablauf also: Kanten nach Gewicht sortieren, durchlaufen, bei jeder Kante
prüfen und ggf. hinzufügen, nach |V|-1 hinzugefügten Kanten kann man
abbrechen.
Vielleicht ist das dann aber gar nicht mehr Kruskal ;-)
Union Find mit Pfadkompression sollte leicht ergooglebar sein, ist
leicht zu implementieren, bloß sehr schwer zu analysieren.
--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
