Question

Please indicate whether the following tasks would be better suited for a Breadth-First Search or a Depth-First Search. Please explain your answer as well.

EX.

Find the minimum element in a binary search tree - DFS

1) Given a node n, find its nearest neighbour.

2) Find the shortest path between 2 vertices(nodes) in a graph.

3) Find the shortest cycle in a directed graph.

4) Find the longest cycle in a directed graph.

5) Which tree traversal scheme uses more memory?

6) Which traversal scheme can be implemented using a queue?

7) Finding the destination of a packet routed through a network.

Thank you :)

8.5.2

Answer 1

Please give positive ratings for my effort. Thanks.

ANSWER

1) Nearest Neighbour can be found using DFS approach.

2) The shortest path between 2 nodes in a graph is found using DFS.

3) The shortest cycle in a directed graph is found using DFS.

4) The longest cycle in a directed graph is found using DFS. Infact cycle detection in a directed graph is always done using DFS.

5) BFS uses more memory.

6) BFS is implemented using queue.

7) DFS is used for finding the destination of a packet routed through a network.