Question

6) Explain how a cycle is found using Depth First Search in the followidg graph. Must the vertex v and Parent parameters are passed and used in the recursive calls. (16) show graphicaly how eat w 6

Answer 1

#include<iostream>
#include <list>
#include <limits.h>
using namespace std;

// Defines class Graph for undirected graph
class Graph
{
// To store number of vertices
int VER;
// Declares a pointer for an array to store adjacency lists
list<int> *adjacent;
bool DFSSearch(int v, bool visited[], int parent);
public:
// Prototype of member functions
Graph(int);
void addingEdges(int, int);
bool DFS();
};// End of class

// Parameterized constructor definition
Graph::Graph(int V)
{
// Assigns number of vertices
VER = V;
// Dynamically creates a list of size V
adjacent = new list<int>[VER];
}// End of parameterized constructor

// Function to add edge
void Graph::addingEdges(int ver, int wait)
{
// Add wait to ver’s list
adjacent[ver].push_back(wait);
// Add ver to waits’s list.
adjacent[wait].push_back(ver);
}// End of function

// Recursive function that uses visited[] and parent to detect cycle in subgraph reachable from vertex ver.
bool Graph::DFSSearch(int ver, bool visited[], int parent)
{
// Mark the current node as visited
visited[ver] = true;

// Creates an iterator for the list
list<int>::iterator it;
for (it = adjacent[ver].begin(); it != adjacent[ver].end(); ++it)
{
// Checks if an adjacent is not visited, then recur for that adjacent
if (!visited[*it])
{
// Recur for all the vertices adjacent to this vertex
// Checks if the return value of the function is true then return true
if (DFSSearch(*it, visited, ver))
return true;
}// End of if condition

// Otherwise checks if an adjacent is visited and not parent of current vertex, then there is a cycle.
else if (*it != parent)
return true;
}// End of for loop
// Otherwise returns false
return false;
}// End of function

// Function to return true if the graph contains a cycle, otherwise returns false
bool Graph::DFS()
{
// Mark all the vertices as not visited and not part of recursion stack
bool *visited = new bool[VER];

// Initializes the visited array to false initially
// Loops till number of vertices
for (int c = 0; c < VER; c++)
// Assigns false to c index position of array visited
visited[c] = false;

// Call the recursive helper function to detect cycle in different DFS trees
for (int t = 0; t < VER; t++)
// Checks if not visited
// Don't recur for t if it is already visited
if (!visited[t])
// Recursively calls the function
// If return value of the function is true then return true
if (DFSSearch(t, visited, -1))
return true;
// Otherwise returns false
return false;
}// End of function

// main function definition
int main()
{
// Creates a graph with 6 vertices
Graph graph(6);

// Calls the function to add edges
graph.addingEdges(0, 1);
graph.addingEdges(0, 2);
graph.addingEdges(0, 3);
graph.addingEdges(1, 4);
graph.addingEdges(1, 2);
graph.addingEdges(1, 0);
graph.addingEdges(2, 0);
graph.addingEdges(2, 1);
graph.addingEdges(2, 3);
graph.addingEdges(2, 5);
graph.addingEdges(3, 2);
graph.addingEdges(4, 1);
graph.addingEdges(4, 5);
graph.addingEdges(4, 4);
graph.addingEdges(4, 2);

// Calls the function to check cycle is present or not
graph.DFS()? cout << "Graph contains cycle\n" : cout << "Graph does not contain cycle\n";
return 0;
}// End of main function

Sample Output:

Graph contains cycle