Breadth First Search (BFS) is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes.

In BFS the vertices have three adjacent different statuses during the process of traversal or searching, the status being : unknown, discovered and visited.

EXAMPLE

In the figure given below, we can see the graph given initially, in which only source S is discovered.

Figure 1 : Initial Input Graph

Figure 2 : After we visit S

Figure 3 : After we visit A

Figure 4 : After we visit B

Figure 5 : After we visit C

Figure 6 : After we visit D

Figure 7 : After we visit E

Figure 8 : After we visit F

Figure 9 : After we visit G

Breadth First Search Programming in C
 #include #include //Global Function Declaration void BFS(); // Global Variable Declaration int number_of_vertices, number_of_edges, discover_top=-1, visited_top=-1, v, i, j, k; int edges[25][2], discovered[25], visited[25]; // main( ) function begins void main() { // Input number of vertices present in the graph printf("\n Enter number of vertices : "); scanf("%d",&number_of_vertices); // Input number of edges present in the graph printf("\n Enter number of edges : "); scanf("%d",&number_of_edges); for(i=0; i 0 means that the vertices present in the temp[ ] array are not discovered or visited if(pos > 0) { // Sort the temp[ ] array using Bubble Sort for(i=1;i temp[j]) { v=temp[j-1]; temp[j-1]=temp[j]; temp[j]=v; } } } // Put all the vertices present in the temp[ ] array into discovered[ ] array for(i=0;i

QuestionSolves.com is an educational website that helps worldwide students in solving computer education related queries.

Also, different software like Visual Studio, SQL Server, Oracle etc. are available to download in different versions.

Moreover, QuestionSolves.com provides solutions to your questions and assignments also.

MORE TOPIC

WHAT WE DO