a) What is the difference between a connected and disconnected Graph?

(b) Describe two real-word applications where a graph data structure would the most efficient data structure to be used in their implementations and explain why.

(c) Giving the following undirected graph answer the questions below:

i. Represent the undirected graph as an adjacency matrix.

ii. State in detail how depth-first traversal of the graph, starting from vertex 1, can be performed using a stack or queue. Write down the stack and visited vertices at each stage.

iii. State in detail how breadth-first traversal of the graph, starting from vertex 1, can be performed using a stack or queue. Write down the queue and visited vertices at each stage.

1 2 3 4 5 5 6 6 7 8