Write a program that for a given graph outputs a vertices of

Write a program that, for a given graph, outputs:

a. vertices of each connected component

b. its cycle or a message that the graph is acyclic

Solution

The below code is written in C++ prgogramming Language:

class my_graph
{
int num_vert; // No. of vertices
list<int> *adj; // An array of adjacency lists

void fillOrder(int v, bool visited[], stack<int> &g_stack); // to fill the vertices into stack

void DFSUtil(int v, bool visited[]); // function to output DFS begining from v
bool is_cyclicUtil(int v, bool visited[], bool *rs); // function to check cyclic or not, used by is_cyclic

public:
my_graph(int v);
void addEdge(int v, int w);

void get_connects(); // function to find and get the connected components of directed graph
my_graph get_trans(); // Function that returns transpose of my_graph
bool is_cyclic(); // main function to check for cyclic or acyclic
};

my_graph::my_graph(int v)
{
num_vert = v;
adj = new list<int>[v];
}

void my_graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}

void my_graph::fillOrder(int v, bool visited[], stack<int> &g_stack)
{
// Mark the current node as visited and print it
visited[v] = true;

// Recur for all the vertices adjacent to given vertex
list<int>::iterator itr;
for(itr = adj[v].begin(); itr != adj[v].end(); ++itr)
if(!visited[*itr])
fillOrder(*itr, visited, g_stack);
g_stack.push(v);
}

// This function finds and prints all strongly connected components
void my_graph::get_connects()
{
stack<int> g_stack;

// Mark all the vertices as not visited (For first DFS)
bool *visited = new bool[num_vert];
for(int itr = 0; itr < num_vert; itr++)
visited[itr] = false;

// Fill vertices in stack according to their finishing times
for(int itr = 0; itr < num_vert; itr++)
if(visited[itr] == false)
fillOrder(itr, visited, g_stack);

// Create a reversed graph
my_graph graph = get_trans();

// Mark all the vertices as not visited (For second DFS)
for(int itr = 0; itr < num_vert; itr++)
visited[itr] = false;

// Now process all vertices in order defined by g_stack
while (g_stack.empty() == false)
{
// Pop a vertex from stack
int v = g_stack.top();
g_stack.pop();

// Print Strongly connected component of the popped vertex
if (visited[v] == false)
{
graph.DFSUtil(v, visited);
cout << endl;
}
}
}

// A recursive function to print DFS starting from v
void my_graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
cout << v << \" \";

// Recur for all the vertices adjacent to this vertex
list<int>::iterator itr;
for (itr = adj[v].begin(); itr != adj[v].end(); ++itr)
if (!visited[*itr])
DFSUtil(*itr, visited);
}

my_graph my_graph::get_trans()
{
my_graph g(num_vert);
for (int j = 0; j < num_vert; j++)
{
// Recur for all the vertices adjacent to this vertex
list<int>::iterator itr;
for(itr = adj[j].begin(); itr != adj[v].end(); ++itr)
{
g.adj[*itr].push_back(j);
}
}
return g;
}

// Utility function which is used by is_cyclic.
bool my_graph::is_cyclicUtil(int v, bool visited[], bool *recg_stack)
{
if(visited[v] == false)
{
// Mark the current node as visited and part of recursion stack
visited[v] = true;
recg_stack[v] = true;

// Recur for all the vertices adjacent to this vertex
list<int>::iterator itr;
for(itr = adj[v].begin(); itr != adj[v].end(); ++itr)
{
if ( !visited[*itr] && is_cyclicUtil(*itr, visited, recg_stack) )
return true;
else if (recg_stack[*itr])
return true;
}
}
recg_stack[v] = false;
  
return false;
}

// This function checks for cyclic or not. if cyclic return true, else false

bool my_graph::is_cyclic()
{
// First, mark all the vertices as not visited and not part of recursion stack
bool *visited = new bool[num_vert];
bool *recg_stack = new bool[num_vert];
for(int j = 0; j < num_vert; j++)
{
visited[j] = false;
recg_stack[j] = false;
}

for(int j = 0; j < num_vert; j++)
if (is_cyclicUtil(j, visited, recg_stack))
return true;

return false;
}

----------------------------------

Note: Test function is not written for this.