You are not logged in. Please login at www.codechef.com to post your questions!

×

Doubt regarding DFS,BFS

What algorithm paradigms do DFS and BFS search belong to? Are search algorithms different from dp or greedy or have some of their characteristics?EG Best first search(greedy)(making locally optimal choices) https://stackoverflow.com/questions/8374308/is-greedy-best-first-search-different-from-best-first-search

asked 01 Sep '17, 15:43

dgupta's gravatar image

0★dgupta
175
accept rate: 0%

edited 01 Sep '17, 16:28


The following observations are only valid if you use DFS/BFS to find an element in a graph. DFS/BFS is also often used for different purposes. E.g. when you want to explore the complete graph, either in a depth first or breath first manner.

Both algorithms fall in the category "Search".

I think also the paradigm "dynamic programming" applies to both. Because in both algorithms you mark nodes as "visited", so that you doesn't search at nodes, which you searched before.

DFS can also be seen as a "greedy" algorithm. At least if you look for a path to an element, it will report the first one that it finds, and the length of the path might not be optimal. BFS on the other side is not greedy. But "bruteforce" might apply here.

Generally I find paradigms a bit fuzzy and they leave room for a lot of interpretation. So the answer is not 100% correct. Depending on what you define as paradigm, the answer will vary a bit.

link

answered 01 Sep '17, 16:04

afaxnraner's gravatar image

6★afaxnraner
5665
accept rate: 25%

edited 01 Sep '17, 16:33

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,221
×243
×6

question asked: 01 Sep '17, 15:43

question was seen: 199 times

last updated: 01 Sep '17, 16:33