How will applying breadth first algorithm on an undirected graph produce a star graph?

0
votes

I got this question from a data structure and algorithm textbook saying

A simple undirected graph is complete if it contains an edge between every pair of distinct vertices. A star graph is a tree of n nodes with one node having vertex degree n-1 and the other n-1 having vertex degree 1.

(a) Draw a complete undirected graph with 6 vertices.

(b) Show that applying breath-first algorithm on the undirected graph in (a) will produce a star graph.

I know how the BFS works using queues and I can provide a result of the traversal. What I'm confused about is on part (b) how can I show that applying BFS on an undirected graph will produce a star graph?

1
data-structuresgraph

1 Answers

0
votes

In a, there is n * (n - 1) / 2 edges in total.

It means that for every two nodes, there is an edge between them.

if applying BFS on (a) using a queue, Steps as follow:

1.) you pick up a random node, which is the root of the graph. 2.) you travel from the root node, and put all the nodes having edges with it to the queue. In addition, you have a boolean array to mark who is already processed.

in 2.), all the nodes except the root will be put into the queue.

At last, the root node have N - 1 edges, others have only one edge, and this edge is with the root