Wie wird die Anwendung des ersten Algorithmus der Breite auf einen ungerichteten Graphen ein Sterndiagramm erzeugen?

Question

bekam ich diese Frage aus einer Datenstruktur und Algorithmus Lehrbuch

Eine einfache ungerichteten Graphen sagen will, ist vollständig, wenn es eine Kante zwischen jedem Paar verschiedener Ecken enthält. Ein Sterngraph ist ein Baum mit n Knoten, wobei ein Knoten den Scheitelgrad n-1 und der andere n-1 den Scheitelgrad 1 hat.

(a) Zeichnen Sie einen vollständigen ungerichteten Graphen mit 6 Ecken.

(b) Zeigen Sie, dass das Anwenden des ersten Atemalgorithmus auf den ungerichteten Graphen in (a) ein Sterndiagramm erzeugt.

Ich weiß, wie das BFS mit Warteschlangen funktioniert, und ich kann ein Ergebnis der Durchquerung bereitstellen. Worüber ich verwirrt bin, ist Teil (b). Wie kann ich zeigen, dass die Anwendung von BFS auf ein ungerichtetes Diagramm ein Sterndiagramm erzeugt?

Answer 1

In einem gibt es n * (n - 1)/2 Kanten insgesamt.

Es bedeutet, dass es für jeweils zwei Knoten eine Kante zwischen ihnen gibt.

wenn die Anwendung BFS auf (a) unter Verwendung einer Warteschlange, die Schritte wie folgt:

1.) Sie einen zufälligen Knoten aufzunehmen, die die Wurzel des Graphen ist. 2.) Sie gehen vom Wurzelknoten und setzen alle Knoten mit Kanten in die Warteschlange. Außerdem haben Sie ein boolesches Array, um zu markieren, wer bereits verarbeitet wurde.

in 2.) werden alle Knoten außer dem Stamm in die Warteschlange gestellt.

Endlich der Wurzelknoten hat N - 1 Kante, andere haben nur eine Kante, und diese Kante ist mit der Wurzel