Anzahl der Kreise Länge 3 in einem ungerichteten Graphen

[YoshiGreen]

Die Matrix ist doch symmetrisch, oder? Damit könnt man doch noch die Laufzeit reduzieren. Wobei bleibt es mit nem Faktor davor trotzdem O(n³)? Fand diese Laufzeitberechnungen zum Kotzen =)

[Schattenläufer]

Ja die Matrix ist symmetrisch, deswegen fang ich auch immer erst ab der Diagonalen an und spare damit ein paar Rechenschritte... nur bei dem Schritt, wo ich den dritten Knoten finde, wusste ich die Symmetrie dann nicht mehr zu nutzen ^^°
Aber ja,wäre dann trotzdem O(n³). Was übrigens auch die Laufzeit einer Matrixmultiplikation und auch diverser anderer gängiger Verfahren mit ähnlichem Hintergrund ist, wie ich feststellen musste, von daher kann es tatsächlich sein, dass diese Laufzeit für das Problem okay ist. (Ist natürlich KLASSE wenn man in der Vorlesung immer nur Beispiele mit n, n log n oder sogar log log n hatte...)

R.F., du hast natürlich Recht >.> Ich hatte irgendwie angenommen, dass ich das in dem Algorithmus berücksichtige, aber das war Quatsch.
Ich finde trotzdem, dass dieses "am Ende durch die Zahl der Rechnungen teilen, die ich mehrfach gemacht habe" eine richtig miese Art ist, das hier zu lösen. Ich meine, man soll laut Aufgabe "jeden Kreis nur einmal zählen". Das mache ich ja letztendlich nicht (und wüsste auch nicht wie das gehen soll).

Ah, sehe gerade den zweiten Teil von R.F.s Post ^^° Stimmt, ich könnte die Kreise als sortierte Tupel speichern und dann abfragen, ob ein gefundener Weg gleich ist. Effizienter ist das zwar nicht (so wie ich das erkenne, ist es nur ein Rechenschritt mehr UND zusätzlicher Speicherverbrauch), aber das ist eigentlich das, was in der Aufgabe gefragt ist.