Wer kennt wen?

[gerhardt]

Hallo,
ich habe ein kleines Problem und hoffe auf gute Ideen.

Ich habe eine Tabelle mit Usern. Dabei hat jeder User eine ID.
Dann gibt es eine Tabelle in der vermerkt ist, wen der User kennt.
Somit hat die Tabelle nur 2 Spalten (USER_ID / KENNT_ID).

Nun möchte ich die kürzeste Verbindung zwischen zwei Usern finden.
(Ähnlich wie XING das auch tut)

Beispiel
Erwin kennt Thomas
Thomas kennt Jörg
Also kennt Erwin, Jörg über Thomas.

Mein Problem ist nun, dass evtl. viele Verbindungen zu Jörg gehen, ich aber die kürzeste brauche.

Ach ja Lösen muss ich das in PHP und SQL. Ist aber kein Problem, wenn ich einen guten Ansatz habe.
Bisher versuche ich mich an Schleifenlösungen, die aber nicht sehr effektiv sind. Ich suche quasi am obigen Beispiel von Erwin vorwärts und Jörg rückwärts. Alle anfallenden IDs in ein Topf und immer vergleichen lassen.

Schon mal vielen Dank für gute Ideen
Gerhardt

 

[karlmosh]

Im Endeffekt müsstest du einen Graphen aufbauen und mit Hilfe von Breiten- oder Tiefensuche eine Verbindung zwischen den beiden Knoten Erwin und Thomas aufbauen.
Ich denke etwas anderes als Schleifen geht da wohl nicht...

Bzw. ich habe mal gelesen, dass in Oracle DBMS rekursive Datenbankanfragen leicht implementiert sind. Welches DBMS benutzt du?

 

[gerhardt]

Welches DBMS benutzt du?

Es wird eine WEB-Anwedung. Mir steht nur MySQL und PHP zur Verfügung.

Gruß
Gerhardt

 

[Broken Sword]

Hi,
dazu brauchst du erstmal theoretische Grundlagen, bevor du es in die Praxis umsetzen kannst.
Schau dir mal das hier an: Dijkstra-Algorithmus – Wikipedia bzw nochmal verständlicher erklärt findest du das hier Dijkstra-Algorithmus
PHP-Beispiel findest du hier: Dijkstra's algorithm - GISWiki

Sonst gibt es durchaus noch andere Verfahren, wie A*-Algorithmus – Wikipedia oder
Algorithmus von Floyd und Warshall – Wikipedia

Über Goole kommt man auch zu einem Thread, wie es mit Oracle geht
[Oracle] Wer kennt wen über wen? Pfade in einem Graph auflisten - Relationale Datenbanksysteme @ tutorials.de: Forum, Tutorial, Anleitung, Schulung & Hilfe

Nun wünsch ich dir viel Spaß beim Lesen und bei weiteren Problemen einfach rufen

Gruß
Broken Sword

 

[Crazylein]

Wer kennt wen gibt es doch bereits im Internet
www. wer-kennt-wen . de

 

[Markus83Muc]

Dafür solltest du dich am besten erstmal in die Graphentheorie einarbeiten. Für die Lösung deines Problems gibt es verschiedene Möglichkeite

• A*-Algorithmus
• Algorithmus von Dijkstra
• Bellman-Ford-Algorithmus
• Floyd-Warshall-Algorithmus
• Johnson-Algorithmus

Welcher für deinen Fall der beste ist weiß ich nicht sicher, aber mit Dijkstra liegst du dabei selten falsch.
Falls du allerdings nicht zwangsläufig den besten Pfad suchst, sondern dir eine Nährung reicht kannst du auch einen typischen Greedy verwenden.

 

[Skyte]

Nun, da die Kanten keine Gewichtung haben, brauchst du nur Breitensuche, sonst nichts! Dijkstra ist für (kanten)gewichtete.
Und ich schreib übermorgen ne Klausur über Graphen und ähnliches, ich muss es wissen (sollte ich zumindestens ).

Sobald die Breitensuche einen Pfad findet, ist es automatisch der kürzeste. (ist ja eigentlich klar)

Wie du den Graphen intern modellieren kannst, steht z.B. auf der 12-mpgi2-graph.pdf Folie: Index of /temp/temp/graph

Breitensuche ist in 13-mpgi2-graphalgo.pdf beschrieben.

 

[Markus83Muc]

Und ich schreib übermorgen ne Klausur über Graphen und ähnliches, ich muss es wissen (sollte ich zumindestens ).

Bin ich froh das ich Vorlesungen wie Diskrete Strukturen oder HM schon lange hinter mir habe.
Aber jetzt wo du das mit den Kanten erwähnst erinnere ich mich leise wieder.