Wenn alle Kanten gleich schwer sind, kann man BFS verwenden, um einen minimalen Spannbaum zu erhalten?

Wenn gegeben, dass alle Kanten in einem Diagramm $G$ sind gleich schwer $c$ Kann man die Breitensuche (BFS) verwenden, um einen minimalen Spannbaum in linearer Zeit zu erzeugen ?

Intuitiv klingt dies richtig, da BFS einen Knoten nicht zweimal besucht und nur vom Scheitelpunkt aus durchquert $v$ zum Scheitelpunkt $u$ wenn es nicht besucht hat $u$ vorher, so dass es keine Zyklen geben wird, und wenn $G$ verbunden ist, wird es schließlich alle Knoten besuchen. Da das Gewicht aller Kanten gleich ist, spielt es keine Rolle, welche Kanten das BFS ausgewählt hat.

Ist meine Argumentation sinnvoll?

algorithms graphs spanning-trees TheNotMe
quelle

Antworten:

Wenn Ihr Diagramm ungewichtet ist oder gleichwertig alle Kanten das gleiche Gewicht haben, ist jeder Spannbaum ein minimaler Spannbaum. Wie Sie festgestellt haben, können Sie ein BFS (oder sogar ein DFS) verwenden, um einen solchen Baum zeitlich linear in der Anzahl der Kanten zu finden.

Juho
quelle

Aber was ist mit dem widersprüchlichen Beispiel Collapsar?

TheNotMe

@TheNotMe BFS wird normalerweise als linearer Algorithmus bezeichnet, da dies der Fall ist

O (| V | + | E |)

$O(|V| + |E|)$ . Im schlimmsten Fall (wie im Beispiel von Collapsar)

| E | = | V |^{2}

$|E| = |V|^2$ so kann BFS als gedacht werden

O (| V |^{2})

$O(|V|^2)$ . Die Algorithmen von Prim und Kruskal für MSTs enthalten jedoch auch

| E |

$|E|$ in ihrer zeitlichen Komplexität und sind daher auch im Sinne von Collapsar nicht "linear". Welchen Algorithmus verwenden Sie als Benchmark? Umfasst seine zeitliche Komplexität?

| E |

$|E|$ ? Wenn ja, ist BFS nicht schlechter als es.

Patrick87

Wenn alle Kantenkosten gleich sind, ist jeder Spanning Tree auch ein minimaler Spanning Tree. In diesem Fall löst jeder Algorithmus, der REACHABILITY löst, auch MST.

Let S = {v0} be a set of nodes initially containing v0
Mark v0
Parent[v0] = -1
While S is not empty
  Remove a vertex v from S
  For all edges (v,u)
    If u is unmarked
      Mark it and add it to S
      Parent[u] = v

Sie können den Baum aus der ParentBeziehung wiederherstellen . Wenn S.Removeund S.Addnehmen Sie konstante Zeit, dann dauert der Algorithmus $\cal O(v+e)=\cal O(v^2)$ wo $v,e$ sind die Anzahl der Eckpunkte und Kanten.

saadtaame
quelle

-3

Wenn alle Kanten gleich schwer sind, können wir verwenden:

-BFS -DFS -Dijkstra-Algorithmus -Prim-Algorithmus

Aber du kannst nicht verwenden

-kruskals Algorithmus

Nandkishor Nangre
quelle

Das ist nicht wahr. Sie können den Kruskal-Algorithmus verwenden.

Evil

Wie ist es möglich, weil es am Ende alle Kanten gibt, wenn wir zuerst mit dem geringsten Gewicht beginnen !!

Nandkishor Nangre

Es wird einen auswählen, jeder, es kann auch zufällig auswählen.

Evil

Ja, ich habe deinen Punkt verstanden !! aber ist es in kruskal algo anwendbar ... weil ich noch nie einen Code von kruskal gesehen habe, der das obige Phänomen

angibt

Die Frage, ob wir "BFS" verwenden können und Ihre Antwort sagt nur "Ja", ohne mehr darüber zu sagen, warum. Wir suchen nicht nach Antworten, die nur behaupten, die Antwort sei ja. Wir suchen nach Antworten, die Erklärungen, Gründe, Rechtfertigungen oder Beweise für ihre Schlussfolgerung liefern. Ich ermutige Sie, Ihre Antwort zu bearbeiten, um zu erklären, warum. In der Frage wurde auch nicht gefragt, wie wir das machen können, sondern ob BFS funktioniert. Wenn Sie also andere Algorithmen bereitstellen, wird die gestellte Frage nicht beantwortet.