#include<iostream> using namespace std; int n; struct vertex { int index; int no_edges; int adj[20]; int predecessor; int d; char color; }v[20]; struct queue{ int data; queue * link; }*front, *rear; void enqueue(int e) { queue * ptr; ptr = new queue; (*ptr).link = NULL; (*ptr).data = e; if(rear == NULL) { front = rear = ptr; } else { (*rear).link = ptr; rear = ptr; } } int dequeue() { queue * temp; int e; if(front == NULL) return 0; else if((*front).link == NULL) { e = (*front).data; temp = front; front = rear = NULL; delete temp; } else{ e = (*front).data; temp = front; front = (*front).link; delete temp; } return e; } void BFS(vertex s); int main() { front = NULL; rear = NULL; int i,j, noe,u, u2; cout<<"Enter the number of edges :"; cin>>n; cout<<"Let the vertices be : "; for(i = 1;i<=n;i++) cout<<i<<" "; cout<<"\n"; for(i = 1;i<=n;i++) { v[i].index = i; cout<<"Enter the number of adjacent vertices for vertex no : "<<i<<" : "; cin>>v[i].no_edges; if(v[i].no_edges != 0) cout<<"Enter the adjacent vertices : "; for(j = 1;j<=v[i].no_edges;j++) cin>>v[i].adj[j]; } cout<<"Enter a vertex no : "; cin>>u; BFS(v[u]); cout<<"Enter another vertex no :"; cin>>u2; cout<<"\nDistance : "<< v[u2].d; if( v[u2].d > 50 ) cout<<"Points ureachable..."; else { cout<<"Path : "<<u2; i = v[u2].predecessor; while(i != 0) { cout<<" -> "<<i; i = v[i].predecessor; } } return 0; } void BFS(vertex s) { int u,i,j,noe,k; for(i = 1; i<=n ;i++) { v[i].color = 'w'; v[i].predecessor = 0; v[i].d = 100; } v[s.index].color = 'g'; v[s.index].predecessor = 0; v[s.index].d = 0; enqueue(s.index); while(front) { u = dequeue(); noe = v[u].no_edges; for(j = 1;j<=noe;j++) { k = v[u].adj[j]; if (v[k].color == 'w') { v[k].color = 'g'; v[k].d = v[u].d + 1; v[k].predecessor = u; enqueue(k); } v[u].color = 'b'; } } }
Thursday, April 19, 2012
Breadth First Search(BFS) in C++
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment