Homework SourseHelp write and incorporate these two functions into existing
Help write and incorporate these two functions into existing C++ code!
Task 1. Write a function that determines whether the graph is strongly connected or not. A graph is strongly connected if and only if every node can reach any other nodes.
Function 2. Write a function that determines whether the graph contains a cycle. You should notice that the graphs we consider here are directed graphs. The idea of DFS can be helpful in this task.
After finished, write some test cases for your code.
Here is what I have so far:
// include the required header files
#include <iostream>
#include <cstdlib>
using namespace std;
#define MAX 20
//GraphAM
class GraphAM
{
//Access specifier
private:
int n;
int **adj;
bool *visited;
//Access specifier
public:
//Constructor
GraphAM(int n)
{
this->n = n;
visited = new bool[n];
adj = new int*[n];
for (int i = 1; i <= n; i++)
{
adj[i] = new int[n];
for (int j = 1; j <= n; j++)
{
adj[i][j] = 0;
}
}
}
//Add edge to graph
void add_edge(int o, int d)
{
if (o > n || d > n || o < 0 || d < 0)
{
cout << \"Invalid edge!\ \";
}
else
{
adj[o][d] = 1;
}
}
//initialize the visited
void initializeVisited()
{
for (int i = 1; i <= n; i++)
visited[i] = false;
}
//\"DFS\" traversal
void depthFirstSrch(int vt)
{
//Set visited to true
visited[vt] = true;
//print visited vt
printf(\"%d \", vt);
//for all nodes in the graph
for (int kk = 1; kk <= n; kk++)
//check adjecent vertex is not visited
if (adj[vt][kk] == 1 && visited[kk] == false)
//call depthFirstSrch
depthFirstSrch(kk);
}
//\"BFS\" traversal
void breadthFirstSrch(int vt)
{
//Declare the required variables
int kk, frt, rar;
int q[20];
frt = rar = -1;
//print vt
printf(\"%d \", vt);
visited[vt] = true;
rar++;
frt++;
q[rar] = vt;
//until vertex in the graph
while (frt <= rar)
{
//delete from queue
vt = q[frt];
frt++;
//for all vertex in graph
for (kk = 1; kk <= n; kk++)
{
//checking adjecent unvisited nodes
if (adj[vt][kk] == 1 && visited[kk] == false)
{
//print visited kk
printf(\"%d \", kk);
visited[kk] = true;
rar++;
q[rar] = kk;
}
}
}
}
void display()
{
int i, j;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
cout << adj[i][j] << \" \";
cout << endl;
}
}
};
int main()
{
int nodes, max_edges, o, d;
cout << \"Enter number of nodes: \";
cin >> nodes;
GraphAM adjmatrix(nodes);
int vt;
max_edges = nodes * (nodes - 1);
for (int i = 0; i < max_edges; i++)
{
cout << \"Enter edge (-1 -1 to exit): \";
cin >> o >> d;
if ((o == -1) && (d == -1))
break;
adjmatrix.add_edge(o, d);
}
cout << \"Adjacent matrix is: \ \";
adjmatrix.display();
cout << \"Enter start vertex:\";
cin >> vt;
//DFS traversal
cout << \"DFS Traversal:\" << endl;
adjmatrix.initializeVisited();
adjmatrix.depthFirstSrch(vt);
//BFS traversal
cout << \"\ BFS Traversal:\" << endl;
adjmatrix.initializeVisited();
adjmatrix.breadthFirstSrch(vt);
cin.get();
cin.get();
return 0;
}
Solution
To check that if a graph is strongly connected or not:
I have used some user defined functions in this code. these udfs will also be defined further if you need one.
bool Graph::isSC()
{
// St1p 1: Mark all the vertices as not visited (For first DFS)
bool visited[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Step 2: Do DFS traversal starting from first vertex.
DFSUtil(0, visited);
// If DFS traversal doesn’t visit all vertices, then return false.
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
// Step 3: Create a reversed graph
Graph gr = getTranspose();
// Step 4: Mark all the vertices as not visited (For second DFS)
for(int i = 0; i < V; i++)
visited[i] = false;
// Step 5: Do DFS for reversed graph starting from first vertex.
// Staring Vertex must be same starting point of first DFS
gr.DFSUtil(0, visited);
// If all vertices are not visited in second DFS, then
// return false
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
return true;
}
//Definition of functions used in the above code:
// The main function that returns true if the graph is strongly connected, otherwise false
bool isSC();
// A recursive function to print DFS starting from v
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
// Function that returns reverse (or transpose) of this graph
Graph Graph::getTranspose()
{
Graph g(V);
for (int v = 0; v < V; v++)
{
// Recur for all the vertices adjacent to this vertex
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); // Add w to v’s list.
}
// Driver program to test above functions
int main()
{
// Create graphs given in the above diagrams
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.isSC()? cout << \"Yes\ \" : cout << \"No\ \";
Graph g2(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
g2.isSC()? cout << \"Yes\ \" : cout << \"No\ \";
return 0;
}
output:
yes
no
2) Write a function that determines whether the graph contains a cycle.
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
if(visited[v] == false)
{
// Mark the current node as visited and part of recursion stack
visited[v] = true;
recStack[v] = true;
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
return true;
else if (recStack[*i])
return true;
}
}
recStack[v] = false; // remove the vertex from recursion stack
return false;
}
// Returns true if the graph contains a cycle, else false.
bool Graph::isCyclic()
{
// Mark all the vertices as not visited and not part of recursion
// stack
bool *visited = new bool[V];
bool *recStack = new bool[V];
for(int i = 0; i < V; i++)
{
visited[i] = false;
recStack[i] = false;
}
// Call the recursive helper function to detect cycle in different
// DFS trees
for(int i = 0; i < V; i++)
if (isCyclicUtil(i, visited, recStack))
return true;
return false;
}
//definition of the functions used in the code written above
bool isCyclic(); // returns true if there is a cycle in this graph
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
//test case to check if the graph contains a cyclic or not
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
if(g.isCyclic())
cout << \"Graph contains cycle\";
else
cout << \"Graph doesn\'t contain cycle\";
return 0;
}
output:
