Breadth First Search(BFS) implementation in C

In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on.

Following c program will perform Breadth First Search

#include<stdio.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v)
{
 for(i=1;i<=n;i++)
  if(a[v][i] && !visited[i])
   q[++r]=i;
 if(f<=r)
 {
  visited[q[f]]=1;
  bfs(q[f++]);
 }
}
int main()
{
 int v;

 printf("\n Enter the number of vertices:");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
  q[i]=0;
  visited[i]=0;
 }
 printf("\n Enter graph data in matrix form:\n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   scanf("%d",&a[i][j]);
 printf("\n Enter the starting vertex:");
 scanf("%d",&v);
 bfs(v);
 printf("\n The node which are reachable are:\n");
 for(i=1;i<=n;i++)
  if(visited[i])
   printf("%d\t",i);
  else
   printf("\n Bfs is not possible");
 getch();
}


Advertisements

Depth First Search(DFS) implementation in C

Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.

Following c program will perform Depth First Search

#include<stdio.h>
#include<conio.h>
int a[20][20],reach[20],n;
void dfs(int v)
{
 int i;
 reach[v]=1;
 for(i=1;i<=n;i++)
  if(a[v][i] && !reach[i])
  {
   printf("\n %d->%d",v,i);
   dfs(i);
  }
}
int main()
{
 int i,j,count=0;

 printf("\n Enter number of vertices:");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
  reach[i]=0;
  for(j=1;j<=n;j++)
   a[i][j]=0;
 }
 printf("\n Enter the adjacency matrix:\n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   scanf("%d",&a[i][j]);
 dfs(1);
 printf("\n");
 for(i=1;i<=n;i++)
 {
  if(reach[i])
   count++;
 }
 if(count==n)
  printf("\n Graph is connected");
 else
  printf("\n Graph is not connected");
}

C program to insert an element at any position of singly linklist.

Following program will insert an element at any position  of  singly link list.

  //////////////////////////////////////////////////////////////////
  /// -:Insert an element at any position of singly link list:- ///
  ////////////////////////////////////////////////////////////
  /*****************************************************************
                 https://wbutassignmentshelp.wordpress.com
  *****************************************************************/

# include<stdio.h>
# include<conio.h>
# include<alloc.h>
# include<stdlib.h>

 struct node
     { int data;
     struct node *link;
     };
     void append(struct node **,int);
     void in_middle(struct node **q,int loc,int num);
     void display(struct node *);
     void main()
     { struct node *p; /* p = start ptr */
     p=NULL;
     int num,loc,c;
     char choice;
     do
     { clrscr();
     printf("Program to Insert an element at any position of singly link list ");
     printf("\n===================================================================");
     printf("\n\n1.Create \\ Appending The List");
     printf("\n2.Insert Node In Middle");
     printf("\n3.Displaying the list");
     printf("\n4.Exit");
     printf("\n\nEnter ur Choice : ");
     choice=getch();
     switch(choice)
     {
     case '1':
     char ans;
     do
     {
     printf("How many times you want to enter  : ");
     scanf("%d",&c);
     for(int i=0;i<c;i++)
     {
     printf("Enter any number : ");
     scanf("%d",&num);
     append(&p,num);
     }
     printf("Enter more (y/n) :");
     fflush(stdin);
     ans=getchar();
     }while(ans !='n');
     break;
     case '3':
     display(p);
     getch();
     break;
     case '2':
     printf("\nEnter The Position :");
     scanf("%d",&loc);
     printf("\nEnter The Data : ");
     scanf("%d",&num);
     in_middle(&p,loc,num);
     break;
     case '4':
     clrscr();
     gotoxy(1,10);printf("\n visit https://wbutassignmentshelp.wordpress.com for more program");
     getch();
     exit(0);
     break;

     default:
     printf("Invalid choice.Please Enter Correct Choice");
     getch();

     }
     }while(choice !=7);
     }
         void append(struct node **q,int num)
     { struct node *temp,*r;
     temp = *q;
     if(*q==NULL)
     { temp = (struct node *)malloc(sizeof(struct node));
     temp->data=num;
     temp->link=NULL;
     *q=temp;
     }
     else
     { temp = *q;
     while(temp->link !=NULL)
     { temp=temp->link;
     }
     r = (struct node *)malloc(sizeof(struct node));
     r->data=num;
     r->link=NULL;
     temp->link=r;
     }
     }



     void display(struct node *q)
     { if(q==NULL)
     { printf("\n\nEmpty Link List.Can't Display The Data");
     getch();
     goto last;
     }
     while(q!=NULL)
     { printf("\n%d",q->data);
     q=q->link;
     }
     last:
     }
     int count(struct node *q)
     { int c=0;
     if(q==NULL)
     { printf("Empty Link List.\n");
     getch();
     goto last;
     }
     while(q!=NULL)
     { c++;
     q=q->link;
     }
     last:
     return c;
     }





     void in_middle(struct node **q,int loc,int num)
     { struct node *temp,*n;
     int c=1,flag=0;
     temp=*q;
     if(*q==NULL)
     { printf("\n\nLink List Is Empty.Can't Insert.");
     getch();
     goto last;
     }
     else
     while(temp!=NULL)
     { if(c==loc)
     { n = (struct node *)malloc(sizeof(struct node));
     n->data=num;
     n->link=temp->link;
     temp->link=n;
     flag=1;
     }
     c++;
     temp=temp->link;
     }
     if(flag==0)
     { printf("\n\nNode Specified Doesn't Exist.Cant Enter The Data");
     getch();
     }
     else
     { printf("Data Inserted");
     getch();
     }
     last:
     getch();
     }

 

 

C program to insert an element at the beginning of singly linklist.

Following program will insert an element at the beginning of  singly link list.

//////////////////////////////////////////////////////////////////
  /// -:Insert an element at the beginning of singly link list:- ///
  ////////////////////////////////////////////////////////////
  /*****************************************************************
                 https://wbutassignmentshelp.wordpress.com
  *****************************************************************/

# include<stdio.h>
# include<conio.h>
# include<alloc.h>
# include<stdlib.h>
 struct node
     { int data;
     struct node *link;
     };
     void append(struct node **,int);
     void in_begin(struct node **,int);
     void display(struct node *);
     void main()
     { struct node *p; /* p = start ptr */
     p=NULL;
     int num,loc,c;
     char choice;
     do
     { clrscr();
     printf("PROGRAM TO CREATE SINGLY LINKED LIST AND DISPLAY IT ");
     printf("\n======================================================");
     printf("\n\n1.Create \\ Appending The List");
     printf("\n2.Insert Node At Begining");
     printf("\n3.Displaying the list");
     printf("\n4.Exit");
     printf("\n\nEnter ur Choice : ");
     choice=getch();
     switch(choice)
     {
     case '1':
     char ans;
     do
     {
     printf("How many times you want to enter  : ");
     scanf("%d",&c);
     for(int i=0;i<c;i++)
     {
     printf("Enter any number : ");
     scanf("%d",&num);
     append(&p,num);
     }
     printf("Enter more (y/n) :");
     fflush(stdin);
     ans=getchar();
     }while(ans !='n');
     break;
     case '3':
     display(p);
     getch();
     break;
     case '2':
     printf("Enter The Data : ");
     scanf("%d",&num);
     in_begin(&p,num);
     break;
     case '4':
     clrscr();
     gotoxy(1,10);printf("\n visit https://wbutassignmentshelp.wordpress.com for more program");
     getch();
     exit(0);
     break;

     default:
     printf("Invalid choice.Please Enter Correct Choice");
     getch();

     }
     }while(choice !=7);
     }
         void append(struct node **q,int num)
     { struct node *temp,*r;
     temp = *q;
     if(*q==NULL)
     { temp = (struct node *)malloc(sizeof(struct node));
     temp->data=num;
     temp->link=NULL;
     *q=temp;
     }
     else
     { temp = *q;
     while(temp->link !=NULL)
     { temp=temp->link;
     }
     r = (struct node *)malloc(sizeof(struct node));
     r->data=num;
     r->link=NULL;
     temp->link=r;
     }
     }
     void display(struct node *q)
     { if(q==NULL)
     { printf("\n\nEmpty Link List.Can't Display The Data");
     getch();
     goto last;
     }
     while(q!=NULL)
     { printf("\n%d",q->data);
     q=q->link;
     }
     last:
     }
     int count(struct node *q)
     { int c=0;
     if(q==NULL)
     { printf("Empty Link List.\n");
     getch();
     goto last;
     }
     while(q!=NULL)
     { c++;
     q=q->link;
     }
     last:
     return c;
     }
     void in_begin(struct node **q,int num)
     { struct node *temp;
     if(*q==NULL)
     { printf("Link List Is Empty.Can't Insert.");
     getch();
     goto last;
     }
     else
     { temp=(struct node *)malloc(sizeof(struct node));
     temp->data=num;
     temp->link=*q;
     *q=temp; /* pointing to the first node */
     }
     last:
     getch();
     }

 

 

C program to create / Appending singly linklist and display it.

This program will create /Append  singly link list and display the link list.

//////////////////////////////////////////////////////////////
  ////////// -:  CREATE SINGLY LINKED LIST AND DISPLAY IT :- /////////
  ////////////////////////////////////////////////////////////
  /*****************************************************************
                 https://wbutassignmentshelp.wordpress.com
  *****************************************************************/

# include<stdio.h>
# include<conio.h>
# include<alloc.h>
# include<stdlib.h>
 struct node
     { int data;
     struct node *link;
     };
     void append(struct node **,int);
     void display(struct node *);
     void main()
     { struct node *p; /* p can be said as the head or a start ptr */
     p=NULL;
     /* Printing the menu */
     int num,loc,c;
     char choice;
     do
     { clrscr();
     printf("PROGRAM TO CREATE SINGLY LINKED LIST AND DISPLAY IT ");
     printf("\n======================================================");
     printf("\n\n1.Create \\ Appending The List");
     printf("\n2.Displaying the list");
     printf("\n3.Exit");
     printf("\n\nEnter ur Choice : ");
     choice=getch();
     switch(choice)
     {
     case '1':
     char ans;
     do
     {
     printf("How many times you want to enter  : ");
     scanf("%d",&c);
     for(int i=0;i<c;i++)
     {
     printf("Enter any number : ");
     scanf("%d",&num);
     append(&p,num);
     }
     printf("Enter more (y/n) :");
     fflush(stdin);
     ans=getchar();
     }while(ans !='n');
     break;
     case '2':
     display(p);
     getch();
     break;
     case '3':
     clrscr();
     gotoxy(1,10);printf("\n visit https://wbutassignmentshelp.wordpress.com for more program");
     getch();
     exit(0);
     break;
     break;
     default:
     printf("Invalid choice.Please Enter Correct Choice");
     getch();

     }
     }while(choice !=7);
     }
         void append(struct node **q,int num)
     { struct node *temp,*r;
     temp = *q;
     if(*q==NULL)
     { temp = (struct node *)malloc(sizeof(struct node));
     temp->data=num;
     temp->link=NULL;
     *q=temp;
     }
     else
     { temp = *q;
     while(temp->link !=NULL)
     { temp=temp->link;
     }
     r = (struct node *)malloc(sizeof(struct node));
     r->data=num;
     r->link=NULL;
     temp->link=r;
     }
     }
     void display(struct node *q)
     { if(q==NULL)
     { printf("\n\nEmpty Link List.Can't Display The Data");
     getch();
     goto last;
     }
     while(q!=NULL)
     { printf("\n%d",q->data);
     q=q->link;
     }
     last:
     }
     int count(struct node *q)
     { int c=0;
     if(q==NULL)
     { printf("Empty Link List.\n");
     getch();
     goto last;
     }
     while(q!=NULL)
     { c++;
     q=q->link;
     }
     last:
     return c;
     }

   
   OUTPUT
    


Structure programming in c

Develop a C program to create a structure emp with the members : name ,age & address .take 10 values through keyboard and detailed information about employees in tabular format . Also display the name of the employees whose age is more than 20.

#include<stdio.h>
#include<conio.h>
struct employee
{
               char name[20],address[100];
               int age;
       };
       int main()
       {
               struct employee emp[10];
  int i;
               for(i=0;i<10;i++)
               {
                       
                             printf(“ENter the name of the employee: “);
                               fflush(stdin);
                               gets(emp[i].name);
                               printf(“Enter the address: “);
               fflush(stdin);
                               gets(emp[i].address);
                               printf(“Age: “);
                               scanf(“%d”,&emp[i].age);
               }
              
               for(i=0;i<10;i++)
         {
                      printf(“\n%s\t%s\t%d\n”,emp[i].name,emp[i].address,emp[i].age);
            }
     for(i=0;i<10;i++)
         {
     if(emp[i].age>20)
             printf(” \n\n\nname of the employees whose age is more than 20 are : “);
             printf(“\n%s\t%s\t%d\n”,emp[i].name,emp[i].address,emp[i].age);
            }

               
               
               getch();
       }

OUTPUT

Enter the name of the employee: RAM
Enter the address: MUMBAI
Age: 18
Enter the name of the employeet: SHAM
Enter the address: DELHI
Age:    
Enter the name of the employee: MADHU
Enter the address: KOLKATA
22
………………………………………………………….
………………………………………………………….
…………………………………………………………
RAM                MUMBAI           18
SHAM             DELHI              21
MADHU           KOLKATA       22       
…………………………………………………………
………………………………………………………….
………………………………………………………….
…………………………………………………………
name of the employees whose age is more than 20 are :
SHAM             DELHI              21
MADHU           KOLKATA       22    

C program to delete an element from an array in any position .

Following code will delete an element from an array in any position.

Compiled with DEV C++

#include <stdio.h>
#include <conio.h>
int main()
{
  int a[50],i,pos,size;
 
  printf(“\nEnter size of the array: “);
  scanf(“%d”,&size);
  printf(“\nEnter %d elements in to the array: “,size);
  for(i=0;i<size;i++)
            scanf(“%d”,&a[i]);
  printf(“\nEnter position where to delete: “);
  scanf(“%d”,&pos);
  i=0;
  while(i!=pos-1)
            i++;
  while(i<10)
  {
            a[i]=a[i+1];
            i++;
  }
  size–;
  printf(“\nAfter implementation”);
  for(i=0;i<size;i++)
            printf(“\n%d”,a[i]);
  getch();
}

C program to insert an element into an array in any position .

#include<conio.h>
#include<stdio.h>
int main()
{
    int i,k=0,a[100],n,loc,b,j;
    printf(“enter the array size: “);
    scanf(“%d”,&n);
    printf(“enter the element: “);
    for(i=1;i<=n;i++)
    {
     scanf(“%d”,&a[i]);
     }
    printf(“enter the location “);
    scanf(“%d”,&loc);
    loc=loc-1;
    printf(“enter the element::”);
    scanf(“%d”,&b);
    for(j=n;j>=loc;j–)
    {
      a[j+1]=a[j];
      }
    a[loc]=b;
    n=n+1;
    printf(“after implementation :\n”);
    for(i=0;i<n;i++)
    {
     printf(“%d\n”,a[i]);
                    }
  getch();
}

OUTPUT

You might be also interested in :

C Program to sort elements using MERGE SORT

C programming code for  Merge SORT  to sort numbers or arrange them in ascending order.

#include <stdio.h>
    #include <conio.h>
    int merge(int *left,int *right,int *result,int nl,int nr)
    {
        int i=0,j=0,k=0;
        while(nl>0 && nr>0)
        {
            if(left[i] <= right[j])
            {
                result[k] = left[i];
                i++;
                k++;
                nl–;
            }
            else
            {
                result[k] = right[j];
                j++;
                k++;
                nr–;
            }
        }
        while(nl>0)
        {
            result [k] = left[i];
            i++;
            k++;
            nl–;
        }
        while(nr>0)
        {
            result[k] = right[j];
            j++;
            k++;
            nr–;
        }
    }

    int main()
    {
        int a[10],b[10],x,y;
        int c[20],i;
        printf(“\nThe no of element in first array : “);
        scanf(“%d”,&x);
        printf(“enter %d no of digits\n\n”,x);
        for (int i=0;i<x;i++)
        {
        printf(“%d no : “,i+1);
        scanf(“%d”,&a[i]);
        }
        printf(“\nThe no of element in 2nd array : “);
        scanf(“%d”,&y);
        printf(“enter %d no of digits\n\n”,y);
        for (int i=0;i<y;i++)
        {
        printf(“%d no : “,i+1);
        scanf(“%d”,&b[i]);
        }
        merge(a,b,c,x,y);
        printf(“\n The sorted list is: “);

        for(i=0;i<x+y;i++)
            printf(“\n %d”,c[i]);
  getch();
 }

OUTPUT

You might be also interested in :

C Program to Insert and Delete elements in Queue

C programming code for Queue. This  program will  Insert and Delete elements in Queue

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

int q[25], n ,front=-1 , rear=-1 , item;

void insertion()
{
       
     if((rear==n) && (front==(rear+1))||(front==rear+1))
     {
       printf(“\nQueue Overflow\n”);
     }
       
       else if (rear==0)
       front = rear = 1;
       
       else if(rear==n)
       rear=1;
       
       else
       rear=rear+1;
       
       printf(“Enter the item : “);
       scanf(“%d”,&item);
       q[rear] = item;
       printf(“%d is inserted\n\n”,item);
       
     }
     
void deletion()
{
     if(front==0)
     {
                    printf(“\nQueue Underflow\n\n”);
           
          }
          
     item=q[front];
          
     if(front==rear)
     {
               front=0;
               rear=0;
     }
     
     else if (front=n)
     front=1;
     
     else
     front=front+1;
     
      printf(“\n%d is deleted\n\n”,item);
 }  
     
void show()         
{
     for(int i=0;i<=rear;i++)
     printf(“%d\t”,q[i]);

 }
     
     
     
int main()
{   
    int op;
    
    printf(“Enter the size of the queue : “);
    scanf(“%d”,&n);
    
    do
          {
             printf(“\n1 : Insert”);
             printf(“\n2 : Delete”);
             printf(“\n3 : Print”);
             printf(“\n4 : Exit”);
             printf(“\nEnter your choice : “);
             scanf(“%d”,&op);
          
             switch(op)
             {
                    case 1:
                              insertion();
                              break;
                              
                    case 2:
                              deletion();
                              break;
                              
                    case 3:
                              show();
                              break;
                    
                                   
                    //default:
                      //        printf(“Invalid Option. Try again.”);
                    
              }
        }while(op!=4);
        
        printf(“\n—THE END—\n”);
    }
OUTPUT

 

You might be also interested in :