 Breitensuche |
IAMLEGEND
unregistriert
 |
|
Moin,
ich wollte mal eine Frage zur Breitensuche stellen. Und zwar liegt die Laufzeit wohl in O(V + E). Meine Frage ist, ob es man eine Instanz (Graphen) konstruieren kann, der besser als O(V + E) laeuft? Ich kann mir das nämlich gar nicht vorstellen, denn egal was für einen Graphen ich habe. Ich muss immer jeden Knoten besuchen, sofern er zusammenhängend ist und ich muss natürlich jeweils die Kanten, die vom Knoten weggehen anschauen. Das jeweils einmal, denn ich besuche jeden Knoten nur einmal. Also liegt Breitensuche immer in O(V+ E) meiner Meinung nach?
|
|
16.06.2011 20:26 |
|
|
|
