Explain Breadth First Search traversal of Graph using an example.

Breadth First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in breadth-first order i.e., all the vertices at the current level are visited before moving on to the next level. It uses a queue data structure to keep track of vertices to be explored.

Here is a step-by-step approach to perform BFS traversal on a graph:

1. Start by picking any vertex of the graph as the source vertex and add it to a queue.
2. While the queue is not empty, repeat the following steps:
   • Dequeue a vertex from the queue and mark it as visited.
   • Visit all the unvisited neighbors of this vertex and add them to the queue.

Let's illustrate this with an example. Consider the following graph:

  1----2
  |    |
  |    |
  4----3

We will start BFS traversal from vertex 1.

Step	Queue	Visited vertices
1	1
2	2, 4	1
3	4, 3	1, 2
4	3	1, 2, 4
5		1, 2, 4, 3

Here is the BFS traversal order of vertices: 1, 2, 4, 3

In terms of time complexity, BFS traversal of a graph with 'V' vertices and 'E' edges takes O(V+E) time. This is because each vertex and each edge will be explored only once during the traversal.

In terms of space complexity, BFS traversal takes O(V) space. This is because in the worst case, you might end up adding all the vertices into the queue. For example, in a tree, if you start BFS traversal from the root, all the second level nodes will be in the queue at some point.

BFS traversal is particularly useful in problems where you want to find the shortest path from a source to all other vertices in an unweighted graph, or if you want to check if a graph is connected or not.