Zusammenhängend Komponente suchen(Graph)

[fatfox]

Hallo alle,

Ich habe einen ungewichteten und ungerichteten Graph, der sehr groß ist. Und ich möchte wissen wie viele zusammenhängende Komponente gibt es und wie sieht die Komponente aus.

Ich habe im Internet gesehen, es gibt ein Graphibrary heißt "JGraphT". Ich habe keine funktion gefunden, die zusammenhängende Komponenten finden kann. Muss man das wirklich seblst machen?

Wenn man selbst schreiben muss, welche Algorithmus soll ich nehmen? Breitesuche? Kann man irgendwas von "JGraphT" benutzen?


Viele Grüße

 

[Marco13]

Bei JGraphT würde man das mit irgendeinem GraphIterator machen - BreadthFirstIterator oder so, aber eben schauen, wie man mitkriegt, wann eine Komponente fertig ist. NUR dafür JGraphT einzubinden wäre aber wohl ein Overkill. Wie sieht denn deine Graph-Klasse im Moment aus (relevante Funktion: Nachbarn finden) ? Eigentlich sollte so eine Suche mit ein paar Zeilen erledigt sein, nur wenn es wirklich ein GROSSER Graph ist, muss man sich vielleicht was überlegen...

 

[fatfox]

Hi Macro13,

Ich möchte zuerst mit kleinem Graph anfangen, aber ich weiß gar nicht, wie... 🙁

Wo ist der BreadthFirstIterator in JGraphT? undr gibt es irgendwo Beispiele für JGraphT?

 

[Marco13]

Man kann wohl an einen BreadthFirstIterator (JGraphT : a free Java graph library) einen TraversalListener (JGraphT : a free Java graph library) hängen, und kriegt dann einen ConnectedComponentTraversalEvent (JGraphT : a free Java graph library) wenn eine Komponente fertig ist. Aber wie gesagt: Je nachdem, wie der Graph bisher aussieht, gibt es da vielleicht einfachere Möglichkeiten...

 

[fatfox]

Hi Macro13,

Vielen Dank für deine Tips! Ich probiere es jetzt!!! 😀