2012-04-03 18 views
0

Ich muss ein Diagramm mit Integer-Arrays generieren. Kanten der Graphen werden als Kanten [e] [2] beibehalten, wobei e die Anzahl der Kanten ist. Ich brauche mein Diagramm verbunden, d. H. Sie sollten in der Lage sein, von allen Knoten zu allen Knoten zu gehen.Generieren Array-basierten Graphen mit Java

Kanten [0] = {0,5} bedeutet, dass eine Kante Knoten 0 und Knoten 5 verbindet. Könnten Sie bitte einen Algorithmus vorschlagen?

Und bitte beachten Sie, dass ich Grafiken mit Millionen von Knoten generieren werde, so dass es besser ist, wenn die Komplexität des Algorithmus nicht zu hoch ist.

+1

ist das Hausaufgaben? – Simeon

+0

Was hast du bisher versucht? Wo ist das Problem? –

+0

das ist keine Hausaufgabe. ein Teil meines akademischen Studiums. –

Antwort

1

Wenn jeder Knoten direkt mit jedem Knoten verbunden ist, nicht speichert alle Kanten;)

Wenn jeder Knoten von jedem anderen Knoten erreichbar ist, aber nicht unbedingt direkt, über ein adjacency matrix verwenden. Das ist der einfachste Weg, wenn Sie ganzzahlige Arrays verwenden müssen.

Wenn die Matrix spärlich ist, würde ich es jedoch anders speichern. Die beste Kodierung hängt davon ab, für welche Grafikalgorithmen Sie sie verwenden möchten. The wikipedia article on sparce matrices) listet die wichtigsten auf.