Wer kennt wen?


  • gerhardt
  • 1852 Aufrufe 7 Antworten

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Wer kennt wen?

    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.
    :rot: 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

  • 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?

  • 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
    Auf dem Abstellgleis sah man ihn liegen,
    Auf dem Abstellgleis zwischen Schwelle und Gestein,
    Auf dem Abstellgleis im strömenden Regen,
    Auf dem Abstellgleis allein.

  • 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.

  • 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 :D).

    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.
    Wo ist der Discord Server