Homework SourseI need help finishing this project Please write these last t
I need help finishing this project. Please write these last two functions into my code.
Function 1. 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. 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
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph
{
int V; // No. of vertices
list<int> *adj; // An array of adjacency lists
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 isSC();
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::isSC()
{
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()
{
// 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;
}
