Question

Describe the search space, depth-first search for the given problem. Strategy from Route A to H.

А E B D G Describe the search space, breadth-first search, and depth-first search for the given problem. Strategy from Route A to H.

Answer 1

DFS algorithm:-

A standard DFS implementation puts each vertex of the tree into one of two categories:

1. Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited .

The DFS algorithm works as follows:

1. Start by putting any one of the tree's vertices on top of a stack.
2. Take the top item of the stack and add it to the visited list.
3. Create a list of that vertex's child nodes. Add the ones which aren't in the visited list to the top of the stack.
4. Keep repeating steps 2 and 3 until the stack is empty.

DFS pseudocode (recursive implementation)

The pseudocode for DFS is shown below. In the init() function, notice that we run the DFS function on every node. This is because the graph might have two different disconnected parts so to make sure that we cover every vertex, we can also run the DFS algorithm on every node.

DFS(G, u) u.visited = true for each v ∈ G.Adj[u] if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u) }

DFS Algorithm Complexity

The time complexity of the DFS algorithm is represented in the form of O(V + E), where V is the number of nodes and E is the number of edges.

The space complexity of the algorithm is O(V).

A, B, E, F, C, D, B CE F D G H 1 Visited A Stack E BIB 12. Nisited AB Stack E BIC 13. visited I BTC stack Eol visited BICID L Stack E

5. visited AB stack C 6. Visited LA IB IDEE Stack THGI visited LABCDEFIGI Stack 7. H 8. Visited Visited A B C D E F G7# stack

.