Anzahl der Kreise Länge 3 in einem ungerichteten Graphen

[Schattenläufer]

Hallo, ich übe gerade auf meine Informatik-Klausur demnächst und bin wieder über diese Aufgabe gestolpert, bei der ich das letzte Mal unter Klausurbedingungen gescheitert bin...

Ein ungerichteter Graph ist in Adjanzenzmatrix-Darstellung (n x n) gegeben, die Matrix sei A. Man soll einen möglichst effizienten Pseudocode schreiben, der die Anzahl der Kreise der Länge 3 zählt.
Ich hab mir mal Gedanken dazu gemacht und eine Lösung erstellt, aber ich bin mir nicht sicher ob das effizient ist, und auch nicht ob es richtig ist. Ganz ehrlich, Adjazenzmatrix-Darstellung finde ich sehr unübersichtlich und ich bin auch einfach nicht gut darin, meine Ansätze zu verifizieren.

Hier ist jedenfalls meine Lösung:


int z = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if A[i][j] = 1
for (int k = 0; k < n; k++)
if A[j][k] = 1 AND A[k][i] = 1 then z++;
return z/3;

Was denkt ihr? Könnte das so stimmen? Und wenn ich das richtig überblicke, wäre die Laufzeit doch O(n³), oder? Das gilt ja als effiziente Laufzeit... aber ginge es noch besser?

Bedenkt die Klausurbedingungen. Ich habe mittlerweile eine Lösung gefunden, wo man die Matrix so oft mit sich multipliziert, wie der Kreis lang sein soll, und dann die Diagonale aufsummiert... das ist ja schön und gut, aber sowas fällt mir in einer Klausur nicht ein. :)

[R.F.]

Wenn ich das richtig sehe, müsste der Algorithmus z/6 zurückgeben. Du gehst ja jeden Knoten durch und erhälst dabei immer zwei Wege des selben Kreises, ist ja ungerichtet. Sprich bei den Knoten x,y,z hättest du ja als gefundene Kombinationen: xyz,xzy,yxz,yzx,zxy,zyx

Alternativ könnte man alle gefundenen Kreisknoten in eine Liste speichern und dann in der if-Anweisung noch abfragen, wenn ein Kreis gefunden wurde, ob alle drei zugehörigen Knoten bereits erfasst wurden.

Von der Laufzeit her müsste es aber gleich bleiben.

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