Graphs

**1.**Breadth first search __________

**2.**Which method of traversal does not use stack to hold nodes that are waiting to be processed?

**3.**The Hamiltonian cycles problem uses the following line of code to generate a next vertex, provided x[ ] is a global array and kth vertex is under consideration:

**4.**

The graph colouring algorithm’s time can be bounded by _________

**5.**

Read the following statements carefully and pick the correct option:

I. The worst time complexity of the Floyd’s algorithm is O(n3).

II. The worst time complexity of the Warshall’s algorithm is O(n3).

**6.**

How many edges are there in a Hamiltonian cycle if the edge cost is ‘c’ and the

cost of cycle is ‘cn’

**7.**Breadth first search

**8.**. Breadth first search uses __________ as an auxiliary structure to hold nodes for future processing.

**9.**

Prims algorithm is based on _____________ method

**10.**kruskal algorithm is based on ___________method