 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Frank Mockenhaupt
Guest
|
 Posted: Thu Jan 26, 2006 3: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: Thu Jan 26, 2006 7:38 pm 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: Thu Jan 26, 2006 10:15 pm 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 1: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 |
|
|
|
|
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
