Indirekte Beziehungen abbilden?

[Igotcha]

Hallo zusammen,

nehmen wir an, es gibt die folgenden direkten Beziehungen:

A kennt B
B kennt C
C kennt D

wie könnte man es realisieren, dass man auf die indirekte Beziehung A kennt D kommt?

Vorliegend ist eine Tabelle, die wie oben aufgebaut ist:

A | B
B | C
C | D

Gruß Igotcha

[mkinzler]

In dem du die Tabelle rekursiv durchsuchst

[Igotcha]

Bis zu welcher Tiefe, bzw. wieviel Iterationen? Das ist nämlich genau der Punkt wo ich mit meinen Überlegungen gerade hänge.

1. Ermittle die Menge aller direkten Beziehungen von A
2. Ermittle die Menge aller direkten Beziehungen zu der ermittelten Menge aller direkten Beziehungen von A
3. etc.

Wo hört man auf und wie vermeidet man Dopplungen, denn wenn A -> B gilt auch B -> A.

Gruß Igotcha

[marabu]

Hallo,

ich erkenne hier ein graphentheoretisches Problem. Die "Tabelle" stellt die einzelnen Segmente (Kante mit ihren zwei Knoten, binary relation) des Graphen dar. Der ist ursprünglich ungerichtet. Zur Lösung der Frage "kennt A D?" kann ausgehend von A ein gerichteter Graph aufgebaut werden. Dazu werden alle Paare schrittweise aufgenommen, so wie du es selbst schon formuliert hast. Dazu müssen lediglich alle Paare normiert (deine Beispieldaten sind es schon) werden, dass heißt das geordnete Tupel (D, C) müsste zuerst in (C, D) transformiert werden, bevor es eingebaut werden kann. Sobald ein normiertes Tupel (x, D) gefunden wird ist die transitive Beziehung erwiesen.

Eine Adjazenzmatrix wäre eine äquivalente Darstellung. An die Stelle des Baums (der Bäume, mehrere sind möglich) tritt dann ein Suchalgorithmus mit Backtracking und Kantenmarkierung.

Gute Nacht