Question: How to combine the code for detecting the cycle in a directedgraph with this class wich forrepresenting adjacency list so, I want in this class

How to combine the code for detecting the cycle in a directedgraph with this class wich forrepresenting adjacency list

so, I want in this class detect the cycle depending withits variables

public class DirectedGraph {
//Set of vertices
Set V = newHashSet();
//Adjacency list
HashMap>addacencyList = new HashMap>();

//Add an edge to the adjacency list
public void addEdge(Course src, Course dest){
//if the list for src is notpresent in addacencyList, create it first
if(addacencyList.get(src.getCourseID())==null){
addacencyList.put(src.getCourseID(), newLinkedList());
}
addacencyList.get(src.getCourseID()).addFirst(dest);
}

//If a vertex does not present in V, add it
public void addVertex(Course c){
if(!V.contains(c)){
V.add(c);
}
}

}

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

******************************************************

The code ehich for detecting the cycle:

import java.io.*;

import java.util.*;

// This class Graph1 represents a directed graphusing adjacency list representation

public class Graph1

{

private int V1; // Number ofvertices

private LinkedList adj[]; //Adjacency List Represntation

// Constructor

Graph1(int v) {

V1 = v;

adj = new LinkedList[v];

for(int j=0; j

adj[j] = new LinkedList();

}

// addEdge1 function to add an edge into thegraph

void addEdge1(int v,int w) {

adj[v].add(w);

adj[w].add(v);

}

// A recursive function that uses visited[] andparent to detect cycle in subgraph reachable from vertexv.

Boolean isCycleUtil(int v, Boolean visited[], int parent)

{

// Mark the current node asvisited

visited[v] = true;

Integer i;

// Recursive for all the vertices adjacent to thisvertex

Iterator it = adj[v].iterator();

while (it.hasNext())

{

i = it.next();

// If an adjacent is not visited, then recursive forthat adjacent

if (!visited[i])

{

if (isCycleUtil(i, visited, v))

return true;

}

// If an adjacent is visited and not parent ofcurrent vertex, then there is a cycle.

else if (i != parent)

return true;

}

return false;

}

// Returns true if the graph1 is containing a cycle,else false.

Boolean isCycle()

{

// Mark all the vertices as not visited and not partof recursion stack

Boolean visited[] = new Boolean[V1];

for (int j = 0; j < V1; j++)

visited[j] = false;

// Call the recursive function to detect cyclein different DFS trees

for (int p = 0; p < V1; p++)

if (!visited[p]) // Don't recur for u ifalready visited

if (isCycleUtil(p, visited, -1))

return true;

return false;

}

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!