# Wide course in The Graphs (BFS)

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)
• 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)
• Dequeue (F)
• Visi[t]t 2

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 Summit A (Summit Visit B)

Visit of the neighbours of Summit A (Summit Visit C)

Marking A as visited and deleting the queue

Visit of the neighbours of Summit 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