Breadth-first search

wikipedia Breadth-first search

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'[1]), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

NOTE:

1、"level"让我想到了hierarchy

Pseudocode

Input: A graph G and a starting vertex root of G

Output: Goal state. The parent links trace the shortest path back to root[7]

 1  procedure BFS(G, root) is
 2      let Q be a queue
 3      label root as discovered
 4      Q.enqueue(root)
 5      while Q is not empty do
 6          v := Q.dequeue()
 7          if v is the goal then
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10              if w is not labeled as discovered then
11                  label w as discovered
12                  Q.enqueue(w)

Applications

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

• Copying garbage collection, Cheney's algorithm
• Finding the shortest path between two nodes u and v, with path length measured by number of edges (an advantage over depth-first search)[12]
• (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.
• Construction of the failure function of the Aho-Corasick pattern matcher.
• Testing bipartiteness of a graph.

geeksforgeeks Depth First Search or DFS for a Graph

Dijkstra's algorithm and breadth-first search

Dijkstra's algorithm和breadth-first search非常类似