Baum

Hallo!
Ich suche eine Datenstruktur in Form eines Baumes, wo jeder Knoten unterschiedlich viele Unterknoten haben kann. Von einem Knoten ausgehend soll dann geprüft werden, ob irgendein Pfad zu einem bestimmten Knoten führt.
Ist so etwas möglich?

prolog

Diese Datenstruktur nennt sich Graph.

Es gibt typische Algorithmen die auf Graphen arbeiten. Eben auch welche die Feststellen ob es eine Verbindung zwischen zwei Vertices gibt.

Graphen selber sind unterschiedlich implementiert. Die meisten benutzen adjazenzlisten um die Daten zu repräsentieren.

Google einfach nach Graphen oder boost::graph bzw. BGL es gibt auch noch LEDA aber die ist AFAIK kostenpflichtig, also weiss ich nicht ob es da frei Doku zu gibt. Am meisten wirst du wohl aus Vorlesungstexten oder ähnlichem lernen.

Sgt. Nukem

Solange keine zyklischen Pfade vorkommen kann man das auch weiterhin als Baum betrachten...

Danke für eure Antworten!

Kennt denn jemand eine Internetseite, wo ein solcher Baum erklärt wird? Ich suche eine Möglichkeit zu prüfen, ob ein Weg von Knoten X nach Knoten Y über einige Umwege existiert.

prolog

@Sgt. Nukem

Da hast du recht. Ich habs deswegen genannt weil es die typische Datenstruktur für solche Problem ist. Ein Baum ist ja nur ein acyclischer Graph wie du schon sagtest. Es ist nur so dass die meisten Leute an einen Binärbaum denken wenn sie Baum hören. Dass auch mehr Blätter existieren dürfen wird oft ausser Acht gelassen.

prolog schrieb:

acyclischer

rofl

prolog

$=~s/c/z/ && $=~s/c/k/ && print $_;

TheTester

ästchen
*******

Für dein Problem der Pfadsuche ist ein Graph sicher vorzuziehen. Gibts einiges bei wikipedia zu dem Thema Graphen.

Zu dem Baum der unterschiedlich viele Knoten haben kann.

Die Baumdarstellung nach der du suchst nennt sich "The left-child, right-sibling representation" klingt etwas seltsam.
Ich würde ja ein aussagekräftiges Bild posten, da das Forum dies aber nicht unterstützt so wie ich das sehe und ich keinen Webspace hab, muss ich das lassen.

Wenn du es haben möchtest kann ichs dir per mail schicken.

bye

tt

Helium

Jetzt mal ungeachtet dessen, dass es bessere Darstellungsformen und Algorithmen gibt, könnte man das, was in der Aufgabenstellung steht, natürlich auch mal eben so hinschreiben:

struct Tree {
   typedef vector<shared_ptr<Tree> > Container;
   Container sub;
}

bool existsConnection (shared_ptr<Tree> tree, shared_ptr<Tree> node)
{
   if (tree == node)
      return true;

   for (Tree::Container::iterator it=tree.begin(); it!=tree.end(); ++it) {
      if (existsConnection (*it, node))
         return true;
   }

   return false;
}

Wie immer ungetestet.

nman

prolog schrieb:

$=~s/c/z/ && $=~s/c/k/ && print $_;

s/c/z/;
s/c/k/;
print;