Write short notes on: 1. Breadth First traversal of graph 1. TOH

a) Breadth first traversal (BFS) of a graph

BFS visits a graph level by level: first the starting vertex, then all its neighbours, then their unvisited neighbours, and so on. It uses a queue.

Algorithm:

1. Mark the start vertex visited and insert it into the queue.
2. While the queue is not empty: delete a vertex v from the queue and visit it; insert every unvisited neighbour of v into the queue and mark it visited.

Example: for edges A–B, A–C, B–D, C–D, D–E starting at A, the BFS order is A, B, C, D, E.

BFS takes O(V + E) time with an adjacency list. It finds the shortest path (fewest edges) in an unweighted graph, and is used in networking (broadcasting), GPS and social-network "friends of friends".

b) Tower of Hanoi (TOH)

There are three pegs (source, auxiliary, destination) and n discs of different sizes on the source peg, largest at the bottom. All discs must be moved to the destination peg with two rules: move one disc at a time, and never place a larger disc on a smaller one.

Recursive solution:

1. Move the top n−1 discs from source to auxiliary (using destination).
2. Move the largest disc from source to destination.
3. Move the n−1 discs from auxiliary to destination (using source).

void toh(int n, char src, char aux, char dst) {
    if (n == 1) {
        printf("Move disc 1 from %c to %c\n", src, dst);
        return;
    }
    toh(n - 1, src, dst, aux);
    printf("Move disc %d from %c to %c\n", n, src, dst);
    toh(n - 1, aux, src, dst);
}

The number of moves is 2ⁿ − 1 (7 moves for 3 discs), so the time complexity is O(2ⁿ).