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
//Adjacency list
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
// 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 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
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started