3. (4pt) Recall the DFS_print (graphT *g, int v); that traverses a graph in a de

Question

3. (4pt) Recall the DFS_print (graphT *g, int v); that traverses a graph in a depth- first-search manner. Suppose it is already implemented and ready to use. Now develop a function that can determine if a given undirected graph g is connected or not. int isConnected (graphT *g) typedef struct edgenode/* if g is connected, return 1; int y: int w; // weight; struct edgenode *next; otherwise, return0 typedef struct edgenodeT *edges [MAXV+1] int degree [MAXV+1]; int visited [MAXV+1]; int nvertices; int nedges; int directed; graphT;

Explanation / Answer

Note : Algorithm to find the whether a graph is strongly connected or Not using DfS............Given two sample graph vertices and checked wheter the graph is strongly connected are not....
///////////////////////////////////////////////////////////cpp code////////////////////////////////////////////////////////////
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph
{
int V;
list<int> *adj;
void DFSUtil(int v, bool visited[]);
public:
Graph(int V) { this->V = V; adj = new list<int>[V];}
~Graph() { delete [] adj; }
void addEdge(int v, int w);
bool isConnected();
Graph getTranspose();
};
void Graph::DFSUtil(int v, bool visited[])
{
visited[v] = true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
Graph Graph::getTranspose()
{
Graph g(V);
for (int v = 0; v < V; v++)
{
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
g.adj[*i].push_back(v);
}
}
return g;
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
bool Graph::isConnected()
{
bool visited[V];
for (int i = 0; i < V; i++)
visited[i] = false;
DFSUtil(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
Graph gr = getTranspose();
for(int i = 0; i < V; i++)
visited[i] = false;
gr.DFSUtil(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
return true;
}
int main()
{
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);
// g1.isConnected()? cout << "Yes " : cout << "No ";
if(!g1.isConnected()){
cout << "0" << endl;
cout << "Graph is Not Connected" << endl;
}
else{
cout << "1" << endl;
cout << "Graph is Connected" << endl;
}
Graph g2(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
// g2.isConnected()? cout << "Yes " : cout << "No ";
if(!g2.isConnected()){
cout << "0" << endl;
cout << "Graph is Not Connected" << endl;
}
else{
cout << "1" << endl;
cout << "Graph is Connected" << endl;
}

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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