ppppp

will eine (rekusive?)funktion bauen, die nachschaut ob eine geschlossene kette vorliegt:

jedes element x kann ein anderes element y zu seiner freundeliste hinzufügen.
habe folgenden mysql datensatz
id | x | y

also z.b.:
1 | a | f //a will f
2 | f | b //f will b
3 | b | c //b will c
4 | b | e //b will e
5 | e | d //e will d
6 | d | a //d will a

würde dann die geschlossene kette: a->f->b->e->d->a ergeben.

-> wie kann ich algemein auslesen, ob so eine kette vorliegt? thx

Mister Ad

nikosch

Willkommen im Forum!

Damit Du hier nicht mit dem falschen Fuß einsteigst beherzige bitte diesen Thread.
Wichtige Punkte:

• Wir helfen gern, wenn Du Initiative zeigst. Macht mal ist nicht.
• Bitte benutze die Code-Box-Buttons und poste relevanten Code.
• Bitte stelle verständliche Fragen in ordentlicher Sprache. Sei prägnant!
• Bitte verwende für spätere Leser einen Threadtitel, der das Problem kurz beschreibt
• Bitte drängle nicht.
• Bitte markiere abgeschlossene Themen über den "Erledigt"-Link oben links.

Dieses Posting erfüllt nicht die Voraussetzung des Fortgeschrittene-Forums. Und wenn es keinen eigenen Code gibt, nicht mal die für Einsteiger. Also Eigenbeteiligung oder Scriptbörse.

[MOD: verschoben]

__________________
--
One pixel is still too big. Please make it smaller. ASAP.

Initiative Mittelstand.
Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers.
--

ppppp

ok, sorry.

verlange auch kein fertiges script, sondern eher ein paar ratschläge, z.b.:
nehmen wir an ich habe eine rekusive funktion die das hoffentlich wie gewünscht prüft:

pseudocode:sobald ein treffer kommt, will ich die funktion mit break abbrechen.
wenn aber kein treffer kommt, würde die rekusive funktion ewig laufen:
-> wie kann ich das machen, dass jeder eintrag nur 1x getestet wird, also die datenbank max 1x durchlaufen wird (bzw. schon vorher abbricht, wenn trefferkette gefunden wird)?

Flor1an

Schau dir mal dafür den Algorithmus für Breitensuche an!

Was bei dir noch wichtig wäre die besuchten Knoten zwischen zu speichern. Wenn du die eine Klasse bastelst kannst du ein Array nutzen in dem eben alle IDs der besuchten Knoten drin stehen. Und dann kannst du eben doppelte Routen abfangen.

Um abzubrechen wenn du eine Route gefunden hast könntest du eben die gefundene ID per return zurück geben. Und das eben rekursiv wieder nach oben zur "root" Funktion. (Schwer zu erklären aber auf jeden Fall sollte eben bei gefundener Route die komplette Suche abgebrochen werden und alle IDs die in der Route enthalten sind zurückgegeben werden.)

Desweitern solltest du noch eine maximale Tiefe haben die nicht überschritten wird. Ich weiß nicht wie dein System aufgebaut ist aber wenn es sein kann das KEINE Route zwischen zwei Knoten existiert dann terminiert natürlich der Algorithmus wenn alle Knoten besucht wurden (da ja keine doppelt besucht werden dürfen) aber das kann unter Umständen extrem aufwendig werden.
Daher eine maximale Tiefe angeben z.B. 6 Knoten danach wird der Algorithmus abgebrochen.

Kleine Annotation am Schluss: Jeder Mensch ist mit jedem anderen über 6-7 Ecken verbunden. Natürlich im Durchschnitt aber dass man jede andere Person auf der Erde über höchstens 7 Ecken kennt ist schon interessant

nikosch

Ich persönlich finde es gruselig, in einer Schleife massig Selects abzusetzen. Bei einer großen Useranzahl kannst Du dir dann gleich immer nen Wecker stellen oder Kaffee kochen gehen.

__________________
--
One pixel is still too big. Please make it smaller. ASAP.

Initiative Mittelstand.
Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers.
--