University:
Boston University
Course:
CAS MA 555 | Numerical Analysis I
Academic year:

2022
Views:

471

Pages:

18
Author:

Cameron Roberts

First Step: DEQUEUE! (take a node out of the queue) Example L0 A A B C E Queue: A Dequeue A  Queue: D F Second Step: ENQUEUE THE NEW NEIGHBORS! (put the nodes into the queue) Example L0 A A B C E D F What are the new neighbors of A? Queue: Example L0 A A L1 B C E D F Enqueue new neighbors of root A. Queue: B C D Example L0 A B A L1 B C E Queue: B C D Dequeue B  Queue: C D D F Example L0 A B A L1 B C E D F There are none! Enqueue new neighbors of B. Queue: C D Example L0 A B C A L1 B C E Queue: C D Dequeue C  Queue: D D F Example L0 A B C A L1 B C D L2 E Enqueue new neighbors of C. Queue: D E F F Example L0 A L1 B C D L2 E Queue: D E F Dequeue D  Queue: E F F A B C D Example L0 A L1 B C D A B C D L2 E F F is already visited! Enqueue new neighbors of D. Queue: E F Example L0 A L1 B C D L2 E Queue: E F Dequeue E  Queue: F F A B C D E Example L0 A L1 B C D A B C D E L2 E F There are none! Enqueue new neighbors of E. Queue: F Example L0 A L1 B C D L2 E Queue: F Dequeue F  Queue: F A B C D E F Example L0 A L1 B C D L2 E A B C D E F F There are none! Enqueue new neighbors of F. Queue: Example L0 A L1 B C D L2 E Queue: A B C D E F F The next step would be to dequeue. But since the queue is empty, we’re done! Now you try it! Enqueue root 1. Dequeue ____. Dequeue ____. Dequeue ____. Dequeue ____. Dequeue ____. Dequeue ____. Dequeue ____. Dequeue ____. Dequeue ____. Dequeue ____. Dequeue ____. Dequeue ____. Queue: Queue: Queue: Queue: Queue: Queue: Queue: Queue: Queue: Queue: Queue: Queue: Now you try it! Enqueue root 1. Dequeue __1_. Queue: 2 3 4 Dequeue __2_. Queue: 3 4 5 6 Dequeue __3_. Queue: 4 5 6 Dequeue __4_. Queue: 5 6 7 8 Dequeue __5_. Queue: 6 7 8 9 10 Dequeue __6_. Queue: 7 8 9 10 Dequeue __7_. Queue: 8 9 10 11 12 Dequeue __8_. Queue: 9 10 11 12 Dequeue __9_. Queue: 10 11 12 Dequeue _10_. Queue: 11 12 Dequeue _11_. Queue: 12 Dequeue _12_. Queue: