Algorithms and Datastructures BFS and DFS are two primary graph traversal algori

Question

Algorithms and Datastructures

BFS and DFS are two primary graph traversal algorithms that we have discussed in the class. As we have discussed, we can use both DFS and BFS in developing web crawling applications.

a) Briefly explain how you can use BFS in developing web crawling applications.

b) Briefly explain how you can use DFS in in developing web crawling applications.

c) Compare and contrast the two techniques described in (a) and (b) above highlighting applicability, strengths, and weaknesses of each approach.

Explanation / Answer

BFS is implemented with a QUEUE which uses FIFO. It finds pages or links along shortest paths. It will first explore all the links on the page and then ii will go to the next level of links.

B. Depth First Search can be implemented with a STACK which uses LIFO. In DFS way, cralers will take a link and keep on opening pages till they get a page which has no links.After finishing a link on the page , it will take up the next link.

C. Both the

techniques are different as one is going in the depth of a link while other is first going

to links at the same level that is the same page.As far as gathering information about a

particular site is considered it is better to go for the BFS at it will gather more information about the site rather than a particular link.With DFS we are not sure how many pages we need to visit whereas it is known in the case of BFS. Also there are chances of getting into infinite loop in case of DFS. However more or less it is scenario based also because we need to know what kind of information we are looking asd what kind of

site it is.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.