In a reputable Algorithmic book , it was mentioned that breadth first search is a greedy algorithm. But I searched for it but I found many links that doesn't say so.
My question: Is breadth first search a Greedy Algorithm and why ?
Can you give me a notable reference for your answer ?!
The term "greedy algorithm" refers to algorithms that solve optimization problems.
BFS is not specifically for solving optimization problems, so it doesn't make sense (i.e., it's not even wrong) to say that BFS is a greedy algorithm unless you are applying it to an optimization problem. In that case, the statement is true or not depending on how it is applied.
The "reputable algorithm book" probably refers to BFS in the context of a specific optimization problem, and is probably correct to say that it is a greedy algorithm in that context... which you have omitted in your question.
The simple answer is YES. To better understand this I would suggest reading on greedy vs heuristics algorithm.
Greedy algorithms supply an exact solution! Heuristic algorithms use probability and statistics in order to avoid running through all the possibilities and provide an "estimated best solution" (which means that if a better solution exists, it will be only slightly better).
A greedy algorithms follow locally optimal solution at each stage. While searching for the best solution, the best so far solution is only updated if the search finds a better solution. Whereas this is not always the case with heuristic algorithms (e.g. genetic, evolutionary, Tabu search, ant search, and so forth). Heuristic algorithms may update the best so far even if it's worse than the best so far to avoid getting trapped in a local optimal solution.
Therefore, in nutshell BFS/DFS generally fall under greedy algorithms.
I understand greedy as "try the best you've got for a given moment".
A BFS, when visiting a node, just adds its children to a queue. There isn't really a "better child" in a BFS since it travels the graph by covering layer by layer. When a node is visited, any order of its children can be added to the queue, so no child seem to be a better choice, hence it doesn't make sense to me that it is greedy, once there is no necessarily a better choice for each moment of the algorithm.
I think there's a confusion here. Maybe you read BFS Greedy and you think it's Breadth First Search Greedy, but the truth is it's Best First Search Greedy. This is another way to call the usual Greedy algorithm applied to searches.
