Question

We have a system which uses Quora pages to measure the similarity between two things. The length of the shortest path of links between two things gives how closely the two concepts are related. If the system uses a depth-first tree search to find a path from one thing to another, it doesn’t find a route reliably, and the routes it finds are typically inefficient. Why is the depth first tree ineffective here? What’s a better way to go about this?

Answer 1

While using the depth-first search (DFS) here the system will keep on surfing the links that are found in the related section because there is no end to the links and so it will be diverted from the original topic for which it was finding the link. Hence, DFS is inefficient for situations where there is no certainty or end point.

The alternative to DFS can be depth limited DFS in which we provide a depth limit e.g. 5 so the system will go to a depth of 5 if it doesn't find the appropriate link it will search other nodes and will not go deeper.