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