Graph – Detect Cycle in an Undirected Graph using DFS

Posted on | Edited on | Views:

REF.1
REF.2 geeksforgeeks DFS

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
import java.util.*;

class UndirectedGraphCycle {

    static class Graph {
        int vertices;
        LinkedList<Integer>[] adjList;

        public Graph(int vertices) {
            this.vertices = vertices;
            adjList = new LinkedList[vertices];
            for (int i = 0; i < vertices; i++) {
                adjList[i] = new LinkedList<>();
            }
        }

        public void addEdge(int source, int destination) {
            // add forward edge
            adjList[source].addFirst(destination);
            // add reverse edge
            adjList[destination].addFirst(source);
        }

        public boolean isCycle() {
            // visited array
            boolean[] visited = new boolean[vertices];
            // do DFS, from each vertex
            for (int i = 0; i < vertices; i++) {
                if (!visited[i]) {
                    if (isCycleUtil(i, visited, -1)) {
                        return true;
                    }
                }
            }
            return false;
        }

        boolean isCycleUtil(int currVertex, boolean[] visited, int parent) {
            // add this vertex to visited vertex
            visited[currVertex] = true;

            for (int i = 0; i < adjList[currVertex].size(); i++) {
                int vertex = adjList[currVertex].get(i);
                // If an adjacent is not visited, then recur for that
                // adjacent
                if (!visited[vertex]) {
                    if (isCycleUtil(vertex, visited, currVertex)) {
                        return true;
                    }
                }
                // If an adjacent is visited and not parent of current
                // vertex, then there is a cycle.
                else if (vertex != parent) {
                    return true;
                }
            }
            return false;
        }
    }
}

public class MyClass {

    public static void main(String[] args) {
        int vertices = 6;
        UndirectedGraphCycle.Graph graph = new UndirectedGraphCycle.Graph(vertices);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        graph.addEdge(4, 5);
        graph.addEdge(5, 2);
        boolean result = graph.isCycle();
        System.out.println("is Cycle present: " + result);
    }
}
0%