Breath-First_search(BFS) Source Code using Queue

 Implementation BFS algorithm using C++
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
#define M 10000
vector<int> edges[M];
vector<int> cost[M];

void Bfs(int n,int source)
{
  queue<int>Q;
  Q.push(source);;
  int taken[100]={0},distance[100];
  taken[source]=1;
  distance[source]=0;
  while(!Q.empty())
  {

      int u=Q.front();
      int a=edges[u].size();
      for(int i=0;i<a;i++)
      {
          int v=edges[u][i];
          if(!taken[v])
          {

              distance[v]=distance[u]+1;
              taken[v]=1;
              Q.push(v);
          }
      }
      Q.pop();
  }
  for(int i=1;i<=n;i++)
  {

      printf("%d to %d distance %d\n",source,i,distance[i]);
  }

}



int main()
{
    int N,E,i;
    int esize,source;
    scanf("%d%d",&N,&E);//how many nodes and edges
    for(i=1;i<=E;i++)
       {
           int x,y;
           scanf("%d%d",&x,&y);
           edges[x].push_back(y);
           edges[y].push_back(x);
           cost[x].push_back(1);
           cost[y].push_back(1);
       }
printf("plz enter source node:");
scanf("%d",&source);
       Bfs(N,source);
 
       return 0;
}

Read more ...

Breath-First-Search(BFS) Source Code without using Queue :)

 Implementation BFS algorithm using C++
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define M 10000
vector<int> edges[M];
//vector<int> cost[M];                     // u can use it later

void Bfs(int n,int source)                  // number of nodes and source point(node)
{

    vector<int> v1,v2;             // declare 2 vector instead of queue
    v1.push_back(source);     
    int taken[100]={0};
    printf("Level 0 :: %d\n",source);
    for(int loop=1;loop<n;loop++)
    {

        printf("Level %d ::",loop);
        for(int i=0;i<v1.size();i++)
        {

            int u=v1[i];
            for(int j=0;j<edges[u].size();j++)
            {
                int v=edges[u][j];               // we found an edge from u to v
                if(!taken[v])                    // we can not go same node twice
                   { printf("%d ",v);          // just process
                    taken[v]=1;                // processed an edge and puts a tag
                    v2.push_back(v);         // where we found v1's node and push it v2
                }
            }
        }

        if(v2.empty())
        {puts("Empty");break;         // can not process any more
        }
        else{                                 // process again
            puts("");
            v1.clear();
            v1=v2;
            v2.clear();
        }
    }
}



int main()
{
    int N,E,i;
    int esize,source;                      // esize==edge size
    scanf("%d%d",&N,&E);       //how many nodes and edges
    for(i=1;i<=E;i++)
       {
           int x,y;
           scanf("%d%d",&x,&y);
           edges[x].push_back(y);
           edges[y].push_back(x);
          // cost[x].push_back(1);       // we can use it future
          // cost[y].push_back(1);        // we can use it future
       }
printf("plz enter source node:");
scanf("%d",&source);
       Bfs(N,source);
 
       return 0;
}
// i followed this code by shafayet's lecture....Thanks shafayet :)

Read more ...

Programming Quotes of all times

• "Copy and Paste is the Design Error."   -David Parnar

• "First, solve the problem. Then Write the code."   -John Johson

• " Programs must be written for people to read, and only incidentally for machines to execute. "-Ableson

Read more ...

QuickSort.java


package Sorting;
import java.util.*;
public class QuickSort {
public static void main(String[] san){
    while(true){
    Scanner input=new Scanner(System.in);
    int num=input.nextInt();   // input how many numbers
    int[] a=new int[num+1]; 
    for(int i=1;i<=num;i++)
        a[i]=input.nextInt();     // array input
   
    quickSort(a,1,a.length-1);
   
   
    for(int i=1;i<=num;i++)
        System.out.printf("%d ",a[i]);
    }
}

public static void quickSort(int [] a,int p,int r){     //first of all p=pivot=1 and r= last element of the array A
    int q;
    if(p<r){
        q=Partition(a,p,r);
        quickSort(a,p,q-1);                // Left Sub Group
        quickSort(a,q+1,r);               // Right Sub Group
    }
}

public static int Partition(int [] a,int p,int r){
    int x,i,j,t;
    x=a[r];
    i=p-1;
    for(j=p;j<=r-1;j++){
        if(a[j]<=x)           //if A[j]>x   do nothing
        {
            i++;
            t=a[i];
            a[i]=a[j];
            a[j]=t;   
        }
    }
    t=a[i+1];
    a[i+1]=a[r];
    a[r]=t;
   
   
    return i+1;
}
}

Read more ...

QuickSort Algorithm

According to the CLRS(Cormen, Leiserson, Rivest,    Stein) Book
  The PseudoCode of the QuickSort is as follows:

  QUICKSORT(A,p,r)   :: initial call is
   QUICKSORT(A,1,length[A])
         1. if p<r
         2.   then q=PARTITION(A,p,r)
         3.             QUICKSORT(A,p,q-1)
         4.             QUICKSORT(A,q+1,r)



Patitioning the array:

 The Key to the algorithm is the PARTITION procedure.Which rearranges the subarray A[p....r] in place.

The Pseudo Code of the PARTITION is as follows:

PARTITION(A,p,r)
    1. x=A[r]
    2. i=p-1
    3. for j=p to r-1
    4.       do if A[j]<=x
    5.                then i=i+1
    6.                       exchange A[i] and A[j]
    7. exchange A[i+1] and A[r]
    8. return i+1

The Source Code of the QuickSort.java

Read more ...

Divide and Conquer Algorithm: MergeSort

import java.util.*;
public class MergeSort {
   
    public static void main(String[] shan){
        while(true){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++)
            arr[i]=input.nextInt();
       
        Merge_sort(arr,0,arr.length-1);
        for(int i=0;i<arr.length;i++)
            System.out.printf("%d ", arr[i]);
        }
    }
   
    public static void Merge_sort(int[] arr,int low,int high){
       
        if(low<high){   
        int mid=(low+high)/2;
        Merge_sort(arr,low,mid);
        Merge_sort(arr,mid+1,high);
       
        Merge(arr,low,mid,high);
       
        }
    }
   
    public static void Merge(int[] arr,int l,int mid,int h){
    int len=arr.length;
        int[] b=new int[len];
        for(int i=0;i<len;i++)
            b[i]=arr[i];
       
        int st=l;
        int Midtem=mid+1;
       
        while(st<=mid && Midtem<=h){
           
            if(b[st]>=b[Midtem])
                arr[l++]=b[Midtem++];
            else
                arr[l++]=b[st++];       
        }
        while(st<=mid){
            arr[l++]=b[st++];
        }
        while(Midtem<=h){
            arr[l++]=b[Midtem++];
        }
    }
}

Read more ...