In this program you will work with BFS. The input to the program is a file conta

Question

In this program you will work with BFS. The input to the program is a file containing an undirected graph in adjacency list format. You will redirect input from this file as you have done in previous programming assignments this semester.

If the graph is connected, the program must output “the graph is connected” and then list the edges of a BFS spanning tree from vertex 1. If the graph is disconnected, the program must output “the graph is disconnected”.

See the input example below, but your program must be capable of working with graphs of up to 1,000 vertices. You may choose any reasonable output format, but you need to specify the format in comments at the top of your main program file.

Input examples:

1 3 4

2 4

3 1 4

4 2 1 3

1 2 4

2 1 3

3 2 4

4 1 3

1 2

2 1

3 4

4 3

Needs to be in C++ and has to read in a file using file redirection containing text such as above.

Explanation / Answer

#include <iostream>
#include <list>
#include <queue>
using namespace std;

class Graph
{
private:
int V;
list<int> *adj;
public:
Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void addEdge(int v, int p);
void BFS(int k, bool visited[]);
Graph getTranspose();
bool isConnected();
};


void Graph::addEdge(int v, int p)
{
adj[v].push_back(p);
adj[p].push_back(v);
}


void Graph::BFS(int k, bool visited[])
{
list<int> q;
list<int>::iterator j;
visited[k] = true;
q.push_back(k);
while (!q.empty())
{
k = q.front();
q.pop_front();
for(i = adj[k].begin(); j != adj[k].end(); ++j)
{
if(!visited[*j])
{
visited[*j] = true;
q.push_back(*j);
}
}
}
}
  
Graph Graph::getTranspose()
{
Graph g(V);
for (int v = 0; v < V; v++)
{
list<int>::iterator j;
for(j = adj[v].begin(); j != adj[v].end(); ++j)
{
g.adj[*j].push_back(v);
}
}
return g;
}

bool Graph::isConnected()
{
bool visited[V];
for (int j = 0; j < V; j++)
visited[j] = false;
BFS(0, visited);
for (int j = 0; j < V; j++)
if (visited[j] == false)
return false;
Graph gr = getTranspose();
for(int j = 0; j < V; j++)
visited[j] = false;
gr.BFS(0, visited);
for (int j = 0; j < V; j++)
if (visited[j] == false)
return false;
return true;
}

int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 3);
if (g.isConnected())
cout<<"The Graph is Connected"<<endl;
else
cout<<"The Graph is not Connected"<<endl;

Graph g1(5);
g1.addEdge(0, 1);
g1.addEdge(1, 2);
g1.addEdge(2, 3);
g1.addEdge(3, 0);
g1.addEdge(2, 4);
g1.addEdge(4, 2);
if (g1.isConnected())
cout<<"The Graph is Connected"<<endl;
else
cout<<"The Graph is not Connected"<<endl;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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