Ich betreibe meine eigene Website, auf der Leute die Möglichkeit haben, Freunde zu haben. So speichere ich Freundschaften:
%Vor%Grundsätzlich ist Benutzer-ID 1 mit Benutzer-ID 2 und ID 3 und Benutzer 2 ist Freunde-Benutzer-ID 4.
Was ich versuche zu erhalten, ist, wie zum Beispiel 1 und 4 verbunden sind. Momentan ist es so:
%Vor%Wenn es zwischen 4 und 3 ist, wäre es:
%Vor%Die Idee ist, so schnell wie möglich eine Verbindung zwischen diesen beiden zu finden
Der einzige Weg, über den ich nachdenken kann, ist ein riesiger loop mit vielen Loops und solchen Sachen, die wahrscheinlich besser und effizienter sein können.
Der kürzeste Freundschaftspfad wird normalerweise mit einem Algorithmus namens Zwei-Wege-Suche gefunden. Thw Hauptidee ist, Netz der Freundschaften als ein ungerichteter Graph zu betrachten, in dem du den kürzesten Weg zwischen 2 Knoten suchst. Dieser erwähnte Algorithmus beginnt mit der Suche von beiden Knoten gleichzeitig, entdeckt Nachbarknoten der bereits bekannten Knoten. Wenn sich die zwei Oberflächen bekannter Knoten zuerst überlappen, wird der kürzeste Pfad gefunden.
Bitte beachten Sie, dass bestimmte Sonderfälle behandelt werden müssen, z. B. wenn sich eine der Personen auf einer "Insel" im Diagramm befindet, ein Knoten, der nicht mit anderen Knoten verbunden ist (denken Sie an eine Gemeinschaft ohne Beziehung) die Außenwelt zu schlagen)
Unter dem Strich ist es eine nicht so große while-Schleife.
Was ich zuerst versuchen würde, ist eine Breite-zuerst-Suche.
Beachten Sie, dass der folgende Code nicht ohne Änderungen funktioniert, da ich nicht einmal auf Syntaxfehler überprüft habe. Die Funktion query () sollte eine Liste von Einträgen zurückgeben, wie Sie sehen. Es soll Ihnen eine Idee geben.
%Vor% Dieser Code wurde zur Vereinfachung optimiert. Für alles andere als Spielzeug-Datenbanken sollten Sie eine bidirektionale Suche durchführen, bei der Sie zwei Listen, friended und friends (den Baum der Frustratoren auf f2) behalten. Sie würden die Liste erweitern, die kürzer ist, während Sie nach einer Übereinstimmung in der anderen Liste suchen. Sie können die Komplexität jedoch nicht austricksen, deshalb müssen Sie das Limit für Iterationen sehr niedrig halten, und Sie mögen das Geräusch trashender Server.
Es ist am besten, zuerst in beide Richtungen zu suchen, d. h. von beiden betroffenen Personen, und diesen Prozess zu stoppen, wenn Sie eine Verbindung finden oder das angegebene Tiefenlimit erreichen. Die Idee ist auch, zuerst die populäreren Personen zu erreichen (während der Durchführung von BFS)
Dies wäre mit Kanten mit einem Gewicht von 1. Es gibt eine Beispielcode , um die Verbindung zwischen zwei Freunden in einem sozialen Netzwerk in PHP zu berechnen