IE$2108$

$3.($a$)$ Write a Python function to perform a Breadth$-$First Search $($BFS$)$ traversal of the graph starting from a start$\_$vertex. The inputs of the function are a graph and the starting vertex. Your function should return a list of vertices visited in the BFS order.

$(5$ Marks$)$

$($b$)$ Write a Python function to check if there exists a path from a start$\_$vertex to a target$\_$vertex in a graph.

$(5$ Marks$)$

$($c$)$ You are given a graph in Figure $3,$ in which the vertices are denoted by letters $(\text{'}$A$\text{'},\text{'}$B$\text{'},\text{'}$C$\text{'},\text{'}$D$\text{'},\text{'}$E$\text{'},\text{'}$F$\text{'}),$ and the edges are represented by lines connecting the vertices. Write down the adjacency list in Python.

$(5$ Marks$)$

$($d$)$ Write a Python program to use the function in part $($a$)$ to return a list of vertices visited in the BFS order for the graph in part $($c$)$ and the starting vertex $\text{'}$A$\text{'}.$ Write down the result of running this program.

$(5$ Marks$)$

$($e$)$ Write a Python program to use the function in part $($b$)$ to check if there exists a path from $\text{'}$A$\text{'}$ to $\text{'}$ F $\text{'}$ in the graph in part $($c$).$ Write down the result of running this program.

$(5$ Marks$)$