Breitensuche Warteschlange

Question

ich bei dieser Aufgabe suchen:

Betrachten wir zwei Ecken a und b, die von s in einem ungerichteten Graphen während der Ausführung von Such erste Breite an derselben Stelle gleichzeitig auf der FIFO-Warteschlange sind.

Welche der folgenden Aussagen zutrifft?

1. die Anzahl der Kanten auf dem kürzesten Weg zwischen s und a atmost eine mehr als die Anzahl von Kanten auf dem kürzesten Weg zwischen s und b.
2. Die Anzahl der Kanten auf dem kürzesten Weg zwischen s und a ist mindestens 1 kleiner als die Anzahl der Kanten auf dem kürzesten Weg zwischen s und b.
3. Es gibt einen Pfad zwischen a und b.

Mögliche Antworten:

a) 1 nur

b) 1 und 2 nur

c) 2 nur

d) 1, 2 und 3

Ich weiß, wie man es löst, bu t im gerade diese Aussage im Sinne Zweifel mit

..., die an derselben Stelle während der Ausführung von Breitensuche gleichzeitig auf der FIFO-Warteschlange sind ...

Was ist die genaue Bedeutung davon?

Answer 1

Wie @beaker bereits kommentiert, gibt es einen Tippfehler bei der Zuordnung. Das Wort gleiche soll einig gelesen werden:

Betrachten zwei Ecken a und b, die zuerst von s in einem ungerichteten Graphen Bei some Punkt während der Ausführung der Breite gleichzeitig auf der FIFO-Warteschlange sind.

Durch die Definition von Breiten Zuerst finden die Knoten, die Sie in der Warteschlange nach der n-ten Iteration der Suche sind n Schritte entfernt vom Startknoten s. Wenn auf die nächste Iteration geht, wird dieser Abstand um 1 erhöht, und jeder Knoten in der Warteschlange aus der Warteschlange einer nach der anderen, um in ihren Nachbarn zu verschieben genommen, die weiter von s ein Schritt entfernt sind. Während dieser Prozess auf halber Strecke ist, gibt es somit Knoten in der Warteschlange, bis alle diejenigen der Entfernung n verarbeitet und aus der Warteschlange entfernt wurden.

Dies bedeutet, dass zu jedem Zeitpunkt zwei beliebige Knoten in der Warteschlange nicht mehr als 1 Schritt in ihrem Abstand zu s abweichen können.

Ich muss sagen, dass der Satz „mindestens eins kleiner als“ in Prämisse 2 ist ein bisschen zweideutig: „mindestens“ ist mathematisch interpretiert werden, dh als „nicht kleiner als“: dist(a,s)>=dist(b,s)-1.

Schließlich, da dies ein ungerichteten Graphen, und wir haben einen Weg von s-ein gefundenen und einem anderen Weg von s-b, gibt es auch einen Weg von einen-b (über s).

Dies löst die Frage.