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 Generate and use the ssh key on Gerrit, github.io, gitlab, and bitbucket.

 Details can be found here -