BFS Graph Practice

Image link for graph I'm using: https://imgur.com/a/vvh7ZyT

BFS:

Add A to the queue (Duncan may specify another vertex as the root which nothing changes behaviourally).

Queue: A

Visit: None


Visit A, remove it from the queue, and add its unexplored neighbours to the queue in order (by default, it’s lexicographical).

Queue: B, E

Visit: A


Visit B remove it from the queue, and add its unexplored neighbours to the queue in order (by default, it’s lexicographical).

Queue: E, C, F

Visit: A, B


Visit E remove it from the queue, and add its unexplored neighbours to the queue in order (by default, it’s lexicographical). Notice that E doesn’t have any unexplored neighbours.

Queue: C, F

Visit: A, B, E


Visit C remove it from the queue, and add its unexplored neighbours to the queue in order (by default, it’s lexicographical).

Queue: F, G

Visit: A, B, E, C


Visit F remove it from the queue, and add its unexplored neighbours to the queue in order (by default, it’s lexicographical). Notice that G is already in the queue, and E has already visited. Nothing is added.

Queue: G

Visit: A, B, E, C, F


Visit G remove it from the queue, and add its unexplored neighbours to the queue in order (by default, it’s lexicographical).

Queue:

Visit: A, B, E, C, G


Notice the queue is now empty, but not all vertices have been visited. As such, we start another BFS from the first unexplored vertex in order (by default, it’s lexicographical). In this case, it’s D.


Add D to queue.

Queue: D

Visit: A, B, E, C, G


Visit D, remove it from the queue, and add its unexplored neighbours to the queue in order (by default, it’s lexicographical).

Queue: H

Visit: A, B, E, C, G, D


Visit H, remove it from the queue, and add its unexplored neighbours to the queue in order (by default, it’s lexicographical).

Queue: L

Visit: A, B, E, C, G, D, H


Visit L, remove it from the queue, and add its unexplored neighbours to the queue in order (by default, it’s lexicographical).

Queue: K

Visit: A, B, E, C, G, D, H, L


Visit K, remove it from the queue, and add its unexplored neighbours to the queue in order (by default, it’s lexicographical).

Queue: J

Visit: A, B, E, C, G, D, H, L, K


Visit J, remove it from the queue, and add its unexplored neighbours to the queue in order (by default, it’s lexicographical).

Queue:

Visit: A, B, E, C, G, D, H, L, K, J


Notice the queue is now empty, but not all vertices have been visited. As such, we start another BFS from the first unexplored vertex in order (by default, it’s lexicographical). In this case, it’s I.


Add I to the queue.

Queue: I

Visit: A, B, E, C, G, D, H, L, K, J


Visit I, remove it from the queue, and add its unexplored neighbours to the queue in order (by default, it’s lexicographical).

Queue:

Visit: A, B, E, C, G, D, H, L, K, J, I


Notice that I don’t have any unexplored neighbours because every vertex in the graph has been visited. Once I is visited, the entire BFS has been completed.