Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <list>
- using namespace std;
- class Graph
- {
- int V;
- list<int> *adj;
- public:
- Graph(int V);
- void addEdge(int v, int w);
- void BFS(int s,int d);
- };
- Graph::Graph(int V)
- {
- this->V = V;
- adj = new list<int>[V];
- }
- void Graph::addEdge(int v, int w)
- {
- adj[v].push_back(w);
- }
- void Graph::BFS(int s,int d)
- {
- bool *visited = new bool[V];
- for (int i = 0; i < V; i++)
- visited[i] = false;
- list<int> queue;
- visited[s] = true;
- queue.push_back(s);
- list<int>::iterator i;
- while (!queue.empty())
- {
- s = queue.front();
- cout << s << " ";
- if(s==d) break;
- queue.pop_front();
- for (i = adj[s].begin(); i != adj[s].end(); ++i)
- {
- if (!visited[*i])
- {
- visited[*i] = true;
- queue.push_back(*i);
- }
- }
- }
- }
- int main()
- {
- Graph g(6);
- g.addEdge(0, 1);
- g.addEdge(0, 2);
- g.addEdge(1, 3);
- g.addEdge(1, 5);
- g.addEdge(2, 0);
- g.addEdge(2, 3);
- g.addEdge(3, 2);
- g.addEdge(3, 4);
- g.addEdge(4, 3);
- g.addEdge(4, 5);
- g.addEdge(5, 1);
- g.addEdge(5, 4);
- cout << "Please provide the Source: \n";
- int a;
- cin>>a;
- cout << "Please provide the Destination: \n";
- int d;
- cin>>d;
- cout << "Breadth First Traversal of the following graph is \n";
- g.BFS(a,d);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement