Eine A-Matrix in Deinem Fall musst Du Dir so vorstellen: Für jedes Mitglied i, dass mit dem Mitglied j verbunden ist, steht in der i-ten Zeile und der j-ten Spalte eine 1. Sonst 0. Für weitere Erklärungen, bitte googlen. Da Du sehr viele Nullen und sehr wenig 1en hast, ist Dein Graph nicht vollständig (d.h. nicht jedes Mitgl. kann von jedem Mitgl. aus erreicht werden). Deshalb wäre [sparse Matrix] für eine Implementation in Betracht zu ziehen. Wenn ich richtig davon ausgehe, dass Dein Graph ungerichtet ist (wenn ich mich mit Dir verbinde, bist auch automatisch Du mit mir verbunden), dann kannst Du Dich auf eine obere (untere) Dreiecksmatrix beschränken.
QUOTE Eigentlich kann man bei einem ungewichteten Graphen immer vom Gewicht 1 ausgehen ;-)
;-)
Genau das macht den Dijkstra unnütz, weil er sich den kürzesten Weg am gesammten Gewicht des bisherigen Weges sucht. Das ist aber ein obsoleter Informationsvorsprung wenn alle Kanten dasselbe Gewicht haben und der schöne Algo wird naiv zur Breiten- bzw. Tiefensuche, weil wir alle Äste ablaufen müssen. A propos Dijkstra, sehr schöne Erklärung [manderby dijkstra] von ehm. zürcher Stud.
D.h. wir rechnen am Ende doch alles durch und cachen...
Ich empfehle wirklich @Moritz, dass Du Dich darauf beschränkst die Distanz zu berechnen. Methoden mittels Herauschlösung von Kanten findest Du [kürzester weg ungewichtet graph]. Aber das ist nicht ganz einfach und Du müsstest Sonderbehandlungen einführen, weil Dein Graph nicht zusammenhängt.
Allgemeine Algos um [Spannbäume] (auch [minimaler Spannbaum]) zu berechnen (wahrscheinlich würde ich es so probieren?) sind [Algorithmus von Kruskal] und [Algorithmus von prim]. Dabei ist der Krux aber, dass Dein Graph noch immer nicht gewichtet ist. Wg. des nicht-zusammenhängen musst Du hier wieder schauen, dass Du schnell genug abbrichst, wenn der Erfolg ausbleibt.
Was Sascha im gelinkten Post gepostet hat kann dabei nützlich sein. [bidirectional search]
D.h. mir fällt ganz ernsthaft kein Musterbuch Algorithmus ein, der Dein Problem löst. Es wäre möglich die Anzahl der Kontakte eines Mitgliedes als Kantengewicht zu benutzen, da darin naiv die Whk beschrieben ist, dass ein gesuchtes Mitglied vorkommt. Das hat den unübersehbaren Nachteil, dass dort entsprechend viele weitere Varianten zur nächsten Iteration fällig werden.
Wie sieht denn Dein Datentyp aus?
Alternativ könntest Du - ähnlich wie Google mit Blockrank - versuchen die Mitliedern in Kästchen (also in Untergruppen) einzuteilen, weil Du mit dieser Info den kürzesten Weg schneller berechnen könntest. Das hätte den Vorteil, dass man schnell nach Connectivität zw den beiden Kästchen suchen kann in denen die beiden Mitgliedern sind. Allerdings rate ich davon ab.
Hm, ich weiss wirklich nicht recht. Ich würde mich darauf beschränken die nächsten 6 Ebenen pro Mitglied zu holen (max 12. min 1 queries) und diese zu schneiden. Implementier das mal, das sollte sehr einfach sein, und dann implementierst Du Caching. Evtl. gibt es rein mathematische Lösungen....?
PS: Alles in [] bezeichnet eine Suchabfrage, d.h. Texte in eckigen Klammern sind an Google zu füttern. (Das könnte man grad in den bb Code implementieren...)
