Talk:Breadth-first search

From Wikipedia, the free encyclopedia

Breadth first recursion now redirects here.


Contents

[edit] Request for major editing:

I have been looking at this and also depth-first search and the preliminary explanation has the same meaning. It says that it starts at the root node "or a node", and explores each neighboring node of the "root" fully without making a cycle until it finds the goal. Something needs to be done about this. I'm just a student trying to learn this so I don't think I can really help. Maybe I'll ask my professor to fix this.

No that's not a mistake. Both algorithms have this property. The property you state does not uniquely identify the algorithm. The algorithms use completely different data structures and result in different traversal orders.


I think that since BFS uses a Queue, "push" and "pop" are wrong (stacks, LIFO): a queue uses "enqueue" and "dequeue". Edited. --Folletto 16:00, 21 Jun 2005 (UTC)

"Since all nodes discovered so far have to be saved, the space complexity of breadth-first search is O(|V| + |E|)." I don't see it. Where does the |E| come from?

[edit] Pseudocode

The pseudocode looks funny, and a little too close to an actual implementation. I have taken liberty to modify it a little.


[edit] Djisktra's Algorithm vs. BFS

When BFS is used with a priority queue, it is a total algorithm to find the shortest path between any two nodes in a weighted graph. Clearly, therefore, finding the shortest path between two nodes in a weighted graph is an application of BFS.

Somebody deleted this application because they felt that this should be an application of Djisktra's Algorithm instead. What is the logic here? Clearly it is an application of both DA and BFS. DA is an optimization of the backtracing step of BFS, so you don't have to use back-pointers to remember how you got to the destination. The distinction between BFS and DA therefore has little to do with whether or not the graph is weighted. Finally, BFS is much easier to remember than DA, so BFS is undoubtedly the more popular algorithm to find shortest paths in any graph (weighted or unweighted). Therefore this application should be listed.

Hi, I think I was the one who deleted that passage. Why I did it? BFS simply does not find a shortest path in a weighted graph! It finds the path that has the fewest number of edges, but if edges have edge weights, BFS will find an arbitrary expensive path of n edges instead of the cheap path that has n+1 edges. Therefore BFS is not an application for finding a shortest path in a weighted graph simply because it computes absolute nonsense if run on a weighted graph. BFS will always find the path that has the fewest number of nodes which just happens to be the shortest path if all weights are the same. You certainly can modify BFS to use a priority queue instead of a normal queue so that it then really finds a shortest path. But then DFS is the same as BFS just with a stack instead of a queue. So you would have to add the part about shortest paths in the DFS article, too. All three algorithms differ (mainly) only by just the datastructure used to save the nodes in, but their output is absolutely different. --Regnaron 21:14, 26 September 2006 (UTC)


The original formulation of BFS did not restrict the queue to be a FIFO queue. If you use BFS with a FIFO queue on a weighted graph then you're effectively discarding the edge weights. That's why you get a different result from the algorithm with a priority queue versus FIFO queue: you're changing the input. DFS is completely different because you get a result that you won't get merely by changing the inputs. BFS has been used with a priority queue in scheduling simulators long before Djikstra's algorithm got its name. It is not limited to unweighted graphs!

If you use BFS with a FIFO queue on a weighted graph then you're effectively discarding the edge weights. That's why you get a different result from the algorithm with a priority queue versus FIFO queue: you're changing the input. And exactly that result you get is wrong. It is not a shortest path but the path with fewest nodes. If you use it with a priority queue, the result is correct, but then, where is the difference to Dijkstras algorithm? Find the vertex that is first in the queue, update its value and never look at it again. Just the same as Dijkstra. --Regnaron 05:43, 4 October 2006 (UTC)


Your question, "Where is the difference to Dijkstra's Algorithm?" gets to the heart of the matter. BFS with PQ is easy to remember, is immediately clear to anybody who has learned BFS, and is the oldest and most popular algorithm for finding all shortest paths in a weighted graph. By contrast, Dijkstra's Algorithm is obscure, known only in elite circles, difficult to memorize, and named after a professor. The differences between the algorithms have nothing to do with the problem they are solving, and everything to do with name-dropping elitism and obfuscation.

What you seem to be suggesting is that "Djikstra's Algorithm solves the problem, therefore BFS with PQ does not". BFS and PQ long predate Dijkstra's Algorithm: they were used in the 1940s back in Alan Turing's days when lattice theory, AI, and scheduling systems were first developed for computers. So your statement should be turned around. What problem is Dijkstra's Algorithm solving that BFS and PQ did not already solve? If anything needs to be deleted, it's the Dijkstra's Algorithm entry, not the BFS entry.

[edit] Usage in 2D grids for computer games

It is worth mentioning that when BFS is used in that manner, the neighbour list should be created such that north, east, south and west get priority over north-east, south-east, south-west and north-west. The reason for this is that BFS tends to start searching in a diagonal manner rather than adjacent, and the path found will not be the correct one. BFS should first search adjacent nodes, then diagonal nodes.

I think a better explanation or a reference is required here. As I understand it the resulting path will be zig-zagged if diagonal moves are prioritized over moves to adjacent grid point. The resulting path should still be correct.

This section is mostly unintelligible and describes an obscure application in a very special field. There are thousands of equally obscure applications which are only interesting to their practitioners and add no additional insights to BFS. Suggest to remove it. --Mbetter 07:59, 17 August 2007 (UTC)
I agree this is not helpful and is incorrect as it is currently worded. As Mbetter points out the topic is not especially important to BFS. I am removing it. Add it as a bullet to the applications section if you really feel it is worth mentioning. Jludwig 18:22, 2 October 2007 (UTC)

[edit] C++ implementation

In the sample implementation, why do we use an std::vector<int> to keep track of key-value pairs? The method we currently use wastes more space, runs slower (when attempting to recover path data later on), makes reading the code less clear, and is less versatile (e.g., in expanding the function for a situation where graph size is unknown beforehand) than the much more elegant solution for such an associative array—an std::map<int,int>. I will change the code accordingly if no reasonable objections appear within a week or so. --76.189.119.174 00:41, 10 August 2007 (UTC)

This has been changed accordingly. --76.189.119.174 03:16, 18 August 2007 (UTC)

[edit] Connectedness, search and traversal

The article is vague about stating the problem that BFS is supposed to solve. Is the goal to search for a path to a given vertex, or to traverse all vertices? The distinction is important for instance if the graph is not connected. (The link to "graph search algorithms" actually leads to a page about traversal!) --Mbetter 08:10, 17 August 2007 (UTC)

[edit] Complexity

The sections on complexity are slightly inconsistent and worded incorrectly. I am changing them to correct the reason for the time and space complexity and to reflect the common notation. Jludwig 18:26, 2 October 2007 (UTC)