{"id":25992,"date":"2017-10-26T09:27:36","date_gmt":"2017-10-26T03:57:36","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25992"},"modified":"2018-10-27T17:32:59","modified_gmt":"2018-10-27T12:02:59","slug":"java-algorithm-detect-cycle-undirected-graph-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-algorithm-detect-cycle-undirected-graph-2\/","title":{"rendered":"Detect cycle in an undirected graph"},"content":{"rendered":"

Given an undirected graph, how to check if there is a cycle in the graph?<\/h4>\n

Java Algorithm – Detect cycle in an undirected graph<\/span><\/h3>\n

For example<\/strong>, the following graph<\/a> has a cycle 1-0-2-1.<\/p>\n

The time complexity of the union-find algorithm is O(ELogV)<\/strong>. Like directed graphs<\/a>, we can use DFS<\/strong> to detect cycle in an undirected graph in O(V+E)<\/strong> time. We do a DFS traversal of the given graph. For every visited vertex \u2018v\u2019, if there is an adjacent \u2018u\u2019 such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don\u2019t find such an adjacent for any vertex, we say that there is no cycle. The assumption of this approach is that there are no parallel edges between any two vertices.<\/p>\n

\"detect-undirected-graph-cycle\"<\/p>\n

The program is given in Java program<\/a>, as follows<\/p>\n

Java Programming:<\/strong><\/span><\/h4>\n
<\/div> 
\/\/ A Java Program to detect cycle in an undirected graphimport java.io.*;import java.util.*; \/\/ This class represents a directed graph using adjacency list\/\/ representationclass Graph{    private int V;   \/\/ No. of vertices    private LinkedList<Integer> adj[]; \/\/ Adjacency List Represntation     \/\/ Constructor    Graph(int v) {        V = v;        adj = new LinkedList[v];        for(int i=0; i<v; ++i)            adj[i] = new LinkedList();    }     \/\/ Function to add an edge into the graph    void addEdge(int v,int w) {        adj[v].add(w);        adj[w].add(v);    }     \/\/ A recursive function that uses visited[] and parent to detect    \/\/ cycle in subgraph reachable from vertex v.    Boolean isCyclicUtil(int v, Boolean visited[], int parent)    {        \/\/ Mark the current node as visited        visited[v] = true;        Integer i;         \/\/ Recur for all the vertices adjacent to this vertex        Iterator<Integer> it = adj[v].iterator();        while (it.hasNext())        {            i = it.next();             \/\/ If an adjacent is not visited, then recur for that            \/\/ adjacent            if (!visited[i])            {                if (isCyclicUtil(i, visited, v))                    return true;            }             \/\/ If an adjacent is visited and not parent of current            \/\/ vertex, then there is a cycle.            else if (i != parent)                return true;        }        return false;    }     \/\/ Returns true if the graph contains a cycle, else false.    Boolean isCyclic()    {        \/\/ Mark all the vertices as not visited and not part of        \/\/ recursion stack        Boolean visited[] = new Boolean[V];        for (int i = 0; i < V; i++)            visited[i] = false;         \/\/ Call the recursive helper function to detect cycle in        \/\/ different DFS trees        for (int u = 0; u < V; u++)            if (!visited[u]) \/\/ Don't recur for u if already visited                if (isCyclicUtil(u, visited, -1))                    return true;         return false;    }      \/\/ Driver method to test above methods    public static void main(String args[])    {        \/\/ Create a graph given in the above diagram        Graph g1 = new Graph(5);        g1.addEdge(1, 0);        g1.addEdge(0, 2);        g1.addEdge(2, 0);        g1.addEdge(0, 3);        g1.addEdge(3, 4);        if (g1.isCyclic())            System.out.println("Graph contains cycle");        else            System.out.println("Graph doesn't contains cycle");         Graph g2 = new Graph(3);        g2.addEdge(0, 1);        g2.addEdge(1, 2);        if (g2.isCyclic())            System.out.println("Graph contains cycle");        else            System.out.println("Graph doesn't contains cycle");    }}\/\/ This code is contributed by Aakash Hasija<\/code><\/pre> <\/div>\n
Output:<\/strong><\/span><\/h3>\n
Graph contains cycle\r\nGraph doesn't contain cycle<\/pre>\n
Time Complexity:<\/strong> <\/span>The program does a simple DFS Traversal of graph<\/strong> and graph is represented using adjacency list. So the time complexity is O(V+E)<\/strong><\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Java Algorithm – Detect cycle in an undirected graph – Graph Algorithms – Given an undirected graph, how to check if there is a cycle in the graph<\/p>\n","protected":false},"author":1,"featured_media":31290,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,74168,73906,2139],"tags":[76186,76526,76185,76184,76189,76183,76187,76525],"class_list":["post-25992","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-coding","category-dfs-and-bfs","category-graph-algorithms","category-java","tag-detect-cycle-in-directed-graph-c","tag-detect-cycle-in-directed-graph-dfs","tag-detect-cycle-in-directed-graph-in-c","tag-detect-cycle-in-directed-graph-java","tag-detect-cycle-in-graph-using-bfs","tag-detect-cycle-in-undirected-graph","tag-detect-cycle-in-undirected-graph-in-c","tag-detect-cycle-in-undirected-graph-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25992","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25992"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25992\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31290"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25992"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25992"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25992"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}