-
Notifications
You must be signed in to change notification settings - Fork 0
/
CycleDetection_Undirected.java
80 lines (62 loc) · 2.08 KB
/
CycleDetection_Undirected.java
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
80
package Graphs;
import java.util.ArrayList;
public class CycleDetection_Undirected {
public static class Edge{
int w;
int src;
int dest;
public Edge(int w, int s, int d){
this.w = w;
this.src = s;
this.dest = d;
}
}
public static void createGraph(ArrayList<Edge> graph[]){
for (int i=0; i<graph.length; i++){
graph[i] = new ArrayList<>(); //assigning a new array list at each index of graph array
}
graph[0].add(new Edge(1, 0, 1));
graph[0].add(new Edge(1, 0, 2));
graph[0].add(new Edge(1, 0, 3));
graph[1].add(new Edge(1, 1,0));
graph[1].add(new Edge(1, 1,2));
graph[2].add(new Edge(1, 2, 0));
graph[2].add(new Edge(1, 2, 1));
graph[3].add(new Edge(1, 3, 0));
graph[3].add(new Edge(1, 3, 4));
graph[4].add(new Edge(1, 4, 3));
}
public static boolean cycleDetect(ArrayList<Edge>[] graph){
boolean[] vis = new boolean[graph.length];
for (int i=0; i<graph.length; i++){
if (!vis[i]){
if (detectUtil(graph, vis, i, -1)) return true;
}
}
return false;
}
public static boolean detectUtil(ArrayList<Edge>[] graph, boolean[] vis, int curr, int par){
vis[curr] = true;
for (int i=0; i<graph[curr].size(); i++){
Edge e = graph[curr].get(i);
// case 1 : unvisited
if (!vis[e.dest]){
if (detectUtil(graph, vis, e.dest, curr))
return true;
}
// case 2 : visited and not parent
if (vis[e.dest] && e.dest != par){
return true;
}
}
return false;
}
public static void main(String[] args) {
int V = 5;
ArrayList<Edge>[] graph = new ArrayList[V];
createGraph(graph);
System.out.println(
"Cycle Exists : " + cycleDetect(graph)
);
}
}