The graph width path (BFS) is an algorithm used to browse graph data structures. BFS implements a specific strategy to visit all the tops of a graph

BFS starts with a summit, then checks the neighbors of the initial summit, then the neighbors of the neighbors, etc.

At the entrance to the algorithm there is the G graph and a starting point D for which the distance is considered to be 0.

Out of the algorithm are calculated all the distances between the top D and each top of the G graph as well as the tree covering whether the G graph is related (i.e. for any pair of topthere there is a path between them in the graph).

The following tables are used:

- Distanc[.]e: Stores the distance between D (starting top) and another top of the graph.
- Fathe[.]r: Stores the father top of a top of the graph traveled.
- Visit[.]: Stores the visit status of the summit, possible list of values 0:not yet visited,1:Visit in progress,2:Visited

The following functions are used for an F-lane:

- First (F): Returns the item to the top of the F-lane without removing it.
- Dequeue(F): Returns the item to the top of the F-line by removing it.
- Append (F, A): Put element A in the F-lane at the back of the line.

The steps are:

**Initialization phase**- 1. For all the summits do
- Visit – 0 (Not visited yet)
- Pere – null (Initializes the table)
- Distance – -1

- 2. Append (F,D) (adds the starting element)
- 3. Distanc[R]e – 0 (starting premise)

- 1. For all the summits do
**Action phase (G graph route)**- As long as the F-line is not empty
- t – First (F)
- For all neighbors v t do
- If Visit[v] 0 (summit not visited) then
- Visit [v]- 1 (Visit in progress)
- Distance[v] – Distance[t] – 1
- Father[v] – t
- Append (F,v)

- If Visit[v] 0 (summit not visited) then
- Dequeue (F)
- Visi[t]t 2

- As long as the F-line is not empty

If we detail the steps with the case of the example graph below.

**Initialization phase:**

Initializing element A is the remote starting element 0, it is colored orange to indicate that the visit is underway.

**Visit of the neighbours of Sum**mit A (Summit Visit B)

**Visit of the neighbours of Sum**mit A (Summit Visit C)

**Marking A as visited and deleting the queue**

**Visit of the neighbours of Su**mmit B (Summit Visit D)

**Marking B and C as visited and deleting the queue**

**Marking D as visited and end of algorithm**

**Building the tree covering whether the graph is related**

Application: The width path of a graph (BFS) is useful for:

- Check whether a graph is related (all tops are then marked as visited at the end of the algorithm).
- Calculate distances from a given peak
- Build a tree covering a graph