Breadth-first Search - Applications

Applications

Breadth-first search can be used to solve many problems in graph theory, for example:

  • Finding all nodes within one connected component
  • Copying Collection, Cheney's algorithm
  • Finding the shortest path between two nodes u and v (with path length measured by number of edges)
  • Testing a graph for bipartiteness
  • (Reverse) Cuthill–McKee mesh numbering
  • Ford–Fulkerson method for computing the maximum flow in a flow network
  • Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.

Read more about this topic:  Breadth-first Search