C++ Graphs Help! The Assignment: Reachability from a source vertex s is the prob

Question

C++ Graphs Help!

The Assignment:

Reachability from a source vertex s is the problem to find the set of vertices S such that v S if exists a path from s to v. You will create a C++ program to find reachable vertices using Breath First Search (BFS) algorithm.

There is an imput file with an sparse matrix. Given the source the program needs to display all reachable vertices.

I really dont know how to approach this problem since our professor did not touch graph theory with us.

I would really appreciate the help.

The graph looks like this:

Input example for Figure 1 (the last line indicates the matrix dimension n 11) 2 1 1 2 3 1 3 5 1 4 5 1 5 6 1 5 7 1 5 8 1 64 1 7 6 1 9 5 1 10 9 1 11 2 1 Output example (source 2) 1 3 4 5 6 7 8

Explanation / Answer

#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);
};
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)
{
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 << " ";
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(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
cout << "Following is Breadth First Traversal "
<< "(starting from vertex 2) ";
g.BFS(2);
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.