-
Notifications
You must be signed in to change notification settings - Fork 2
/
CycleInUndirectedGraph.java
62 lines (51 loc) · 1.83 KB
/
CycleInUndirectedGraph.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
package Graph;
import java.util.ArrayList;
import java.util.List;
/**
* @author kalpak
*
* Detect cycle in an Undirected Graph.
*
*/
public class CycleInUndirectedGraph {
public static List<List<Integer>> createGraph(int numNodes) {
List<List<Integer>> graphAdjList = new ArrayList<>(numNodes);
for (int i = 0; i < numNodes; i++)
graphAdjList.add(new ArrayList<>());
return graphAdjList;
}
public static void addUndirectedEdge(List<List<Integer>> graph, int from, int to) {
graph.get(from).add(to);
graph.get(to).add(from);
}
public static boolean hasCycleDFS(List<List<Integer>> graph, int startNode, boolean[] visited, int parent) {
// mark the current node as discovered
visited[startNode] = true;
// do for every edge `startNode —> childNode`
List<Integer> adjacencyList = graph.get(startNode);
for (int node: adjacencyList) {
// if `node` is not discovered
if (!visited[node]) {
if (hasCycleDFS(graph, node, visited, startNode)) {
return true;
}
} else if (node != parent) {
// if `node` is discovered, and `node` is not the parent of startNode
// we found a back-edge (cycle)
return true;
}
}
// No back-edges were found in the graph
return false;
}
public static void main(String[] args) {
List<List<Integer>> graph = createGraph(6);
addUndirectedEdge(graph, 0, 1);
addUndirectedEdge(graph, 1, 2);
addUndirectedEdge(graph, 0, 3);
addUndirectedEdge(graph, 3, 4);
addUndirectedEdge(graph, 4, 5);
addUndirectedEdge(graph, 5, 1);
System.out.println(hasCycleDFS(graph, 0, new boolean[6], -1));
}
}