Question

5. Chapter 22. Give the BFS(G.s) algorithm 6. Computing Complexities Chapter. What is the Hamiltonian Cycle Problem? Hamiltonian cycle problem 7. Computing Complexities Chapter. Define an NP-Complete problem. Do not give an example. Rather tell what it is. Be formal about the definition NP-Complete problems are in NP, the set of all decision probleus whose solutions can be verified in polynomial time 8. Computing Complexities Chapter. What is PSPACE? Set of all decision problems that can be by a turing machine using a polynomial of space. solved amount

Answer 1

Answer 5

BFS -> Breadth first search.

o>It is graph traversing algorithm.

o> It is similar to level order traversing in tree.

o> Here queue is used .

Algorithm-

{Status 1=Ready , Status 2 = processing , Status 3= processed}

1. Initialize all nodes to ready state(Status 1).

2. Put starting node in Queue and change it's status from 1 to 2.

3. Repeat steps 4 and 5 until queue is empty.

4. Remove front node of queue, and change it's status from 2 to 3.

5. Add to rear of queue all neighbors of front node of queue that are in ready state(Status 1) and change their status to 2.

Example to show working of above algorithm.

here we have used above algorithm of bfs to traverse graph.

result of traversal came out to be 1 2 3 4 5 6 .

Queue is used here to store value of vertices temporarily.

(3) 2 1(4 1 1. Queue Gueue : 23|| RESULT = RESULT: RESULT : 1 3. 31% 3. AZ3 32x (4 5)X2 2* (4) 22(4) 5 1 (5)x2 22 Gueee 5 |6 | Pueue- +|5] Gueue - 3 | RESULT : 12 Result: 123 Result: 123 4 3(2) 3. 3 3) 5) 3 Queue - |6 Result : 12345 Quee : RESULT = 1234-56