Sunday, July 24, 2011

Iterative Deeping algorithm source code in C++

 Source code of iterative deeping search is given.
# include <stdio.h>
# include <iostream>
# include <sstream>
# include <algorithm>
# include <string.h>
# include <string>
# include <math.h>
# include <queue>
# include <vector>



using namespace std;



int node,edge;
vector<int>adj[100];
bool flag[100];
int dist[100],par[100],leb[100];

int bfs(int s,int e,int lev)
{
   int i,cur,head,tail,que[10000],l=0;
   head = tail = 0;
   que[head++] = s;
   flag[s] = 1;
   dist[s] = 0;
   par[s] = -1;
   leb[s] = 0;

   memset(leb,0,sizeof(leb));
   while(head != tail)
   {
       cur = que[tail++];

       if(leb[cur] == lev)
       {
           return 0 ;
       }
       cout << cur <<"= Child : ";

       for(i=0;i<adj[cur].size();i++)
       {
           if(flag[adj[cur][i]] == 0)
           {
               cout << adj[cur][i]<<" ";
               que[head++] = adj[cur][i];

               flag[adj[cur][i]] = 1;
               dist[adj[cur][i]] = dist[cur]+1;
               par[adj[cur][i]] = cur;
               leb[adj[cur][i]] = leb[cur] + 1;
               if(adj[cur][i] == e)
               {
                 return dist[cur];
               }
           }

       }
       cout<<"|";

   }
 return 0;

}

int main()
{
    int i,j,k,l,x,y,c,lev;
    while(cin >> node >> edge)
    {
            for(i=1;i<=edge;i++)
            {
                cin >> x >> y;
                adj[x].push_back(y);
                adj[y].push_back(x);
                flag[x] = flag[y] = 0;
            }
            int s,e;
            cin >> s >> e>> lev;
            for(j=1;j<=lev;j++)
            {
                memset(flag,false,sizeof(flag));
                cout<<"Level :"<<j<<endl;
                l = bfs(s,e,j);
                cout<< endl;
                //cout<< l<<endl;

                //printpath(e);
                if(l == 0)cout<<"Not found Yet"<<endl;
                else {cout<<"Found After traverse : "<<l<<" Depping : "<<j<<endl;break;}

            }

    }

    return 0;

}
/* 4 5 1 2 2 3 3 4 2 4 1 3 1 4 3 */

No comments:

Post a Comment

How to enable hotspot in TPG iPhone

 By default, the hotspot does not work on the phone. It will ask you to contact the provider. This video will help you bypass the network ...