Graph traversals
- Graph traversal means visiting every vertex and edge exactly once in a well-defined order.
- While using certain graph algorithms, you must ensure that each vertex of the graph is visited exactly once.
- The order in which the vertices are visited are important and may depend upon the algorithm or question that you are solving.
Breadth First Search (BFS):
- BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layer wise thus exploring the neighbor nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbor nodes.
- As the name BFS suggests, you are required to traverse the graph breadth wise as follows:
- First move horizontally and visit all the nodes of the current layer
- Move to the next layer
Example graph:
Code Implementation:
| void bfs() { int qu[20],i=1,j=0; p=start; while(p!=NULL) { p->status=0; p=p->next; } p=start; qu[0]=p->data; p->status=1; while(1){ if(qu[ j]==0) break; p=start; while(p!=NULL) { if(p->data==qu[ j]) break; p=p->next; } k=p->adj; while(k!=NULL){ q=k->next; if(q->status==0) { qu[i]=q->data; q->status=1; qu[i+1]=0; i++; } k=k->adj; } j++; } j=0; printf(“Breadth First Search Results”); printf(“\n—————————\n”); while(qu[j]!=0){ printf(“%d\t”,qu[j]); j++; } getch(); return; } |
