Skip to main content
Computer Science

Return to Answer

replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

Breadth-first-search is the algorithm that will find shortest paths in an unweighted graph.

There is a simple tweak to get from DFS to an algorithm that will find the shortest paths on an unweighted graph. Essentially, you replace the stack used by DFS with a queue. However, the resulting algorithm is no longer called DFS. Instead, you will have implemented breadth-first-search.

The above paragraph gives correct intuition, but over-simplifies the situation a little. It's easy to write code for which the simple swap does give an implementation of breadth first search, but it's also easy to write code that at first looks like a correct implementation but actually isn't. You can find a related cs.SE question on BFS vs DFS hereBFS vs DFS here. You can find some nice pseudo-code here.

Breadth-first-search is the algorithm that will find shortest paths in an unweighted graph.

There is a simple tweak to get from DFS to an algorithm that will find the shortest paths on an unweighted graph. Essentially, you replace the stack used by DFS with a queue. However, the resulting algorithm is no longer called DFS. Instead, you will have implemented breadth-first-search.

The above paragraph gives correct intuition, but over-simplifies the situation a little. It's easy to write code for which the simple swap does give an implementation of breadth first search, but it's also easy to write code that at first looks like a correct implementation but actually isn't. You can find a related cs.SE question on BFS vs DFS here. You can find some nice pseudo-code here.

Breadth-first-search is the algorithm that will find shortest paths in an unweighted graph.

There is a simple tweak to get from DFS to an algorithm that will find the shortest paths on an unweighted graph. Essentially, you replace the stack used by DFS with a queue. However, the resulting algorithm is no longer called DFS. Instead, you will have implemented breadth-first-search.

The above paragraph gives correct intuition, but over-simplifies the situation a little. It's easy to write code for which the simple swap does give an implementation of breadth first search, but it's also easy to write code that at first looks like a correct implementation but actually isn't. You can find a related cs.SE question on BFS vs DFS here. You can find some nice pseudo-code here.

Source Link
Joe
Joe
  • 4.1k
  • 1
  • 20
  • 38

Breadth-first-search is the algorithm that will find shortest paths in an unweighted graph.

There is a simple tweak to get from DFS to an algorithm that will find the shortest paths on an unweighted graph. Essentially, you replace the stack used by DFS with a queue. However, the resulting algorithm is no longer called DFS. Instead, you will have implemented breadth-first-search.

The above paragraph gives correct intuition, but over-simplifies the situation a little. It's easy to write code for which the simple swap does give an implementation of breadth first search, but it's also easy to write code that at first looks like a correct implementation but actually isn't. You can find a related cs.SE question on BFS vs DFS here. You can find some nice pseudo-code here.