---

Geschrieben von IAMLEGEND am 16.06.2011 um 20:26:

  Breitensuche

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?

---

Geschrieben von ed209 am 18.06.2011 um 13:40:

 

Ja, der Algorithmus schreibt ja gerade vor, jeden Knoten und jede Kante abzulaufen.
Wenn Du natürlich deinen Graph so konstruiierst daß der Knoten den suchst direkt an deinem Ausgangspunkt liegt, dann durchsuchst du nicht alles