Hallo Java-Forum,
mein Problem ist eigentlich nicht java-spezifisch, aber ich versuche es mit java zu loesen. Gegeben habe ich einen ungerichteten, zusammenhaengenden Graphen G mit n Knoten (Vector von Knoten, ein Knoten besitzt einen Vector aller Nachbarknoten). Weiter habe ich integer d<n gegeben. Ich moechte mir nun alle Teilgraphen von G ausgeben lassen, die d Knoten besitzen und zusammenhaengend sind. (Ausgabe zB alle entsprechenden Knoten Arrays der groesse d)
Ich koennte nun natuerlich alle d-Kombinationen betrachten und pruefen, ob Sie zusammenhaengend sind oder eine beschraenkte Breite-/Tiefensuche (von jedem Knoten aus) machen. In beiden Faellen betrachte ich aber sehr viele unnoetige Kombinationen oder viele Kombinationen mehrfach.
Meine Frage also: kennt jemand einen geschickten Algorithmus, der das Problem loest?
Vielen Dank, peetpan
ps: Das ist keine Hausaufgabe, gehoert also nicht in das entsprechende Unter-Forum
mein Problem ist eigentlich nicht java-spezifisch, aber ich versuche es mit java zu loesen. Gegeben habe ich einen ungerichteten, zusammenhaengenden Graphen G mit n Knoten (Vector von Knoten, ein Knoten besitzt einen Vector aller Nachbarknoten). Weiter habe ich integer d<n gegeben. Ich moechte mir nun alle Teilgraphen von G ausgeben lassen, die d Knoten besitzen und zusammenhaengend sind. (Ausgabe zB alle entsprechenden Knoten Arrays der groesse d)
Ich koennte nun natuerlich alle d-Kombinationen betrachten und pruefen, ob Sie zusammenhaengend sind oder eine beschraenkte Breite-/Tiefensuche (von jedem Knoten aus) machen. In beiden Faellen betrachte ich aber sehr viele unnoetige Kombinationen oder viele Kombinationen mehrfach.
Meine Frage also: kennt jemand einen geschickten Algorithmus, der das Problem loest?
Vielen Dank, peetpan
ps: Das ist keine Hausaufgabe, gehoert also nicht in das entsprechende Unter-Forum