Anzahl der Kanten in einem ungerichteten Graphen

Question

Gegeben eine Adjazenzlisten-Darstellung für einen ungerichteten Graphen. Schreiben Sie eine Funktion, um die Anzahl der Kanten im ungerichteten Graphen zu zählen.

Ich weiß, die Anzahl der Kanten in einem ungerichteten Graphen ist n (n-1)/2, aber ich weiß nicht, wie man eine Funktion dafür schreibt.

In Anbetracht dessen, dass ich eine Liste habe und benutze, zähle ich die Anzahl der Kanten. Wie soll ich anfangen?

Answer 1

n(n-1)/2 ist die maximale Anzahl von Kanten in einem einfachen ungerichteten Graphen, nicht die Anzahl der Kanten für jede solche Graphik.

Vorausgesetzt, dass Sie eine Adjazenzliste Darstellung haben, sei es der Fall, dass die Scheitelpunkte u und v eine Kante zwischen ihnen haben. Dann erscheint v in der Adjazenzliste von u und u erscheint in der Adjazenzliste von v. Dies gilt für alle u und v.

Wenn Sie also die Gesamtzahl der Einträge aller Elemente in der Adjazenzliste jedes Eckpunkts zählen, ist das Ergebnis doppelt so groß wie die Anzahl der Kanten im Diagramm. Wenn Sie diesen Wert durch zwei teilen, erhalten Sie das gewünschte Ergebnis.