MHB Breadth First and Depth First Spanning Trees

  • Thread starter Thread starter andrew1
  • Start date Start date
  • Tags Tags
    Depth Trees
andrew1
Messages
20
Reaction score
0
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
 

Attachments

  • fHhlAH4.jpg
    fHhlAH4.jpg
    56.7 KB · Views: 108
Physics news on Phys.org
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.
 
Last edited:
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?
 
Yes, that is also what I got when I implemented the algorithm.
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.

Similar threads

Replies
11
Views
3K
Replies
8
Views
2K
Replies
2
Views
2K
Replies
11
Views
2K
Replies
1
Views
2K
Replies
2
Views
3K
Back
Top