-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCycleDetectionInDirectedGraph.java
More file actions
79 lines (66 loc) · 2.03 KB
/
CycleDetectionInDirectedGraph.java
File metadata and controls
79 lines (66 loc) · 2.03 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package datastructure.graph;
import java.util.LinkedList;
/**
* The type Cycle detection in directed graph.
*/
public class CycleDetectionInDirectedGraph {
/**
* Detect cycle boolean.
*
* @param graph the graph
* @return the boolean
*/
public static boolean detectCycle(AdjacencyListGraph graph){
int vertices = graph.vertices;
boolean visited[] = new boolean[vertices];
boolean stackFlag[] = new boolean[vertices];
for (int i = 0; i < vertices; i++){
//Check cyclic on each node
if (cyclic(graph, i, visited, stackFlag)){
return true;
}
}
return false;
}
private static boolean cyclic(AdjacencyListGraph graph, int v, boolean[] visited, boolean[] stackFlag) {
//if node is currently in stack that means we have found a cycle
if(stackFlag[v])
return true;
//if it is already visited (and not in Stack) then there is no cycle
if (visited[v])
return false;
visited[v]=true;
stackFlag[v]=true;
LinkedList<Integer> temp = null;
if(graph.adjacencyList[v]!=null)
temp=graph.adjacencyList[v];
for(int i=0;i<temp.size();i++){
//run cyclic function recursively on each out go ing path
if(cyclic(graph,temp.get(i),visited,stackFlag)){
return true;
}
}
stackFlag[v] = false;
return false;
}
/**
* Main.
*
* @param args the args
*/
public static void main(String args[]) {
AdjacencyListGraph g1 = new AdjacencyListGraph(4);
g1.addEdge(0,1);
g1.addEdge(1,2);
g1.addEdge(1,3);
g1.addEdge(3,0);
g1.printGraph();
System.out.println(detectCycle(g1));
System.out.println();
AdjacencyListGraph g2 = new AdjacencyListGraph(3);
g2.addEdge(0,1);
g2.addEdge(1,2);
g2.printGraph();
System.out.println(detectCycle(g2));
}
}