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)

Summit B passes to during the visit, its distance from A is calculated and summit A is added as the father summit. It is added to the line.

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

Summit C passes to during the visit, its distance from A is calculated and summit A is added as the father summit. It is added to the line.

Marking A as visited and deleting the queue

A is marked as visited (blue color) and removed from the head of the queue

Visit of the neighbours of Summit B (Summit Visit D)

The summit C being marked as during the visit it will not be visited, one visits the summit D one calculates its distance 2 and one notes the summit B as father of summit B.

Marking B and C as visited and deleting the queue

B is marked as visited (blue color) and removed from the head of the line
C is marked as visited (blue color) and removed from the head of the queue (its neighbor D is marked during the visit)

Marking D as visited and end of algorithm

D is marked as visited (blue color) and removed from the head of the queue.
End of the algorithm

Building the tree covering whether the graph is related

If the graph is related, the result of the path is unfolded and the tree is covered with the graph that contains all the peaks.

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

Leave a Reply

Your email address will not be published. Required fields are marked *