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
*/
Comments
Post a Comment