### Simplified Breadth-first Search

Given a graph*= (*

**G***,*

**V***) and a distinguished*

**E****source**vertex

*, breadth-first search systematically explores the edges of*

**s***to “discover” every vertex that is reachable from*

**G***. It computes the distance (smallest number of edges) from*

**s***to each reachable vertex. It also produces a “breadth-first tree” with root*

**s***that contains all reachable vertices. For any vertex reachable from*

**s***, the simple path in the breadth-first tree from*

**s****to corresponds to a “shortest path” from**

*s***to**

*s***in**

*v**, that is, a path containing the smallest number of edges. The algorithm works on both directed and undirected graphs.*

**G**
We should also learn the time complexity of BFs. This link also provide a better implementation of Breadth First search using python.

ReplyDelete