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.

 

[blue_raver22]

for reaching out! Breadth first and depth first spanning trees are both methods used to traverse a graph and visit all of its vertices. The main difference between the two is the order in which the vertices are visited.

In a breadth first spanning tree, we start at a given vertex and visit all of its adjacent vertices before moving on to the next level of vertices. This means that we explore the graph level by level, starting from the given vertex and moving outward. This can be visualized as a tree with the given vertex at the root and its adjacent vertices at the first level, followed by their adjacent vertices at the second level, and so on.

In a depth first spanning tree, we start at a given vertex and explore as far as possible along each branch before backtracking and exploring the next branch. This means that we explore the graph in a depth-first manner, going as deep as possible before moving on to the next vertex. This can also be visualized as a tree, but the order of the vertices may be different depending on the starting vertex.

To construct a breadth first or depth first spanning tree for a given graph, you can use an algorithm such as Breadth First Search (BFS) or Depth First Search (DFS), respectively. These algorithms use a queue (for BFS) or stack (for DFS) to keep track of the vertices that have been visited and the order in which they should be explored.

I hope this helps clarify the concept of breadth first and depth first spanning trees. If you are still having trouble constructing these trees for your specific graph, please provide more details and I would be happy to assist further.