Breadth First and Depth First Spanning Trees

[andrew1]

Hi,

I'm currently stuck on how to construct a breadth first and depth first spanning tree for this graph, the algorithm that I'm following is somewhat ambiguous. I'd really appreciate if someone can provide an explanation on how I should go by doing this.

ThanksView attachment 2535

 

[batch3]

Breadth first spanning tree:

In this method we use a queue (FIFO).

You first start with the vertex earliest in the alphabet. Which is vertex P. We add that to the queue.

Step1: queue = P, tree = vertex P

Currently, the front of the queue is P. **

We now have to add the next letter (in alphabetical order) to the end of the queue which is connected to the vertex at the front of the queue (which is P) **.

Step2: queue = PQ, tree = we have a line connecting P and Q

Then we repeat the same process, look for the next letter in alphabetical order, S in this case, which is connected to the vertex at the front of the queue (see ** above) which is still P until there are no other vertices that are connected to P.

So after repeating the steps above we realize that P doesn't connect to anything else. So we take P out of the queue.

We'll then have vertex Q at the start of the queue ***. We again check any vertices (in alphabetical order) connected to Q that is not already in the queue. R is the only one that is not already in the queue.

So we add R at the end of the queue.

Every time we add another vertex at the end of the queue, we draw a line between that and the vertex at the start of the queue.

When all the vertices has been added in the queue, we just need to delete the rest following the first in first out (FIFO) method (delete from vertex at the front of the queue until it's empty).Depth first spanning tree:

We again start at the vertex earliest in the alphabet.

We now use a stack (LIFO).

We push vertex P into the stack.

Step1: stack = P, tree = vertex P

Currently, the top of the stack is P. **

So we need to check which vertex is connected to the vertex at the top of the stack which is P (in alphabetical order). We can see that this is Q. So we push Q into the stack.

Step2: stack = PQ, tree = line connecting P and Q.

Currently, the top of the stack is Q. **

So we now need to check which vertex is connected to the letter at the top of the stack which is Q.

We can see that R is the earliest in the alphabet so we push R into the stack

Step3: stack = PQR, tree = line connecting P and Q, and line connecting Q and R.

Repeat the same process until all the letters has been pushed into the stack.

In the end we get:

Stack = PQRUTS

So we just have to pop everything out of the stack following last in first out (LIFO).

Stack:

PQRUTS
PQRUT
PQRU and so on until the stack is empty.*Assuming we do everything in alphabetical order.

 

[andrew1]

Tried this myself the other night and got QSTUR as the last step in my breadth first spanning tree before taking out all the items from the queue, is this correct?

 

[batch3]

Yes, that is also what I got when I implemented the algorithm.