CS502 Assignment 3 Solution Spring 2017

Question. 1  Consider the following Directed Acyclic Graph.                                              (10 Marks)

Run BFS on this graph by taking node ‘1’ as source node and list the vertices in order while running BFS.

Note: Write a list of vertices only, no need to show the intermediate steps.


Question. 2                                                                                                                         (5 Marks)

 Two directed graphs are given below Graph (A) & Graph (B), You are required to answer the following questions

1.      Is “Graph (A)” a connected graph? State Yes / No with valid reason

2.      Is “Graph (B)” contains a Hamiltonian cycle? State Yes / No with valid reason