Der effizienteste Algorithmus, um zu wissen, ob ein ungerichteter Graph verbunden ist

Question

Ich habe versucht, einen Algorithmus zu finden, um zu suchen, ob ein Graph verbunden ist. Der Graph ist ungerichtet und ich möchte nur eine Lösung finden (es kann mehrere geben) oder wenn es keine gibt. Ich war auf der Suche nach einem Alg. das führt fast lineare Zeit, vielleicht O (logN) oder O (NlogN).

Kann DFS der Aufgabe gewachsen sein oder gibt es eine andere Alternative für dieses spezielle Problem?

Answer 1

Es wird auf abhängen, wie Sie N definieren, wenn N Anzahl der Ecken ist, der Eingang selbst O(N^2) von Größe sein kann, und Sie werden mehr brauchen, alles zu lesen (es sei denn, Sie einige spezifische Reihenfolge des Eingangs haben und dann könnte sich das ändern).

DFS wird in O(|V|+|E|) (Anzahl der Knoten + Anzahl der Kanten) ausgeführt und kann feststellen, ob der Graph durch einfaches Zählen der Anzahl neuer Eckpunkte verbunden ist. Wenn Sie fertig sind, überprüfen Sie, ob diese Zahl |V| ist.