{"id":25988,"date":"2017-10-26T09:25:55","date_gmt":"2017-10-26T03:55:55","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25988"},"modified":"2018-10-30T15:38:29","modified_gmt":"2018-10-30T10:08:29","slug":"python-algorithm-detect-cycle-undirected-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-algorithm-detect-cycle-undirected-graph\/","title":{"rendered":"Detect cycle in an undirected graph"},"content":{"rendered":"

Python Algorithm: detect cycle in an undirected graph:<\/strong><\/span><\/h3>\n

Given an undirected graph<\/a>, how to check if there is a cycle in the graph? For example, the following graph has a cycle 1-0-2-1.<\/p>\n

We have discussed cycle detection for directed graph. We have also discussed a union-find algorithm for cycle detection in undirected graphs<\/a>. The time complexity of the union-find algorithm is O(ELogV)<\/strong>. Like directed graphs, we can use DFS to detect cycle in an undirected graph in O(V+E)<\/strong> time. We do a DFS traversal<\/a> of the given graph. For every visited vertex \u2018v<\/strong>\u2019, if there is an adjacent \u2018u<\/strong>\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

Python Programming to detect cycle in an undirected graph:<\/strong><\/span><\/h3>\n
<\/div> 
# Python Program to detect cycle in an undirected graph from collections import defaultdict  #This class represents a undirected graph using adjacency list representationclass Graph:      def __init__(self,vertices):        self.V= vertices #No. of vertices        self.graph = defaultdict(list) # default dictionary to store graph       # function to add an edge to graph    def addEdge(self,v,w):        self.graph[v].append(w) #Add w to v_s list        self.graph[w].append(v) #Add v to w_s list      # A recursive function that uses visited[] and parent to detect    # cycle in subgraph reachable from vertex v.    def isCyclicUtil(self,v,visited,parent):         #Mark the current node as visited         visited[v]= True         #Recur for all the vertices adjacent to this vertex        for i in self.graph[v]:            # If the node is not visited then recurse on it            if  visited[i]==False :                 if(self.isCyclicUtil(i,visited,v)):                    return True            # If an adjacent vertex is visited and not parent of current vertex,            # then there is a cycle            elif  parent!=i:                return True                 return False               #Returns true if the graph contains a cycle, else false.    def isCyclic(self):        # Mark all the vertices as not visited        visited =[False]*(self.V)        # Call the recursive helper function to detect cycle in different        #DFS trees        for i in range(self.V):            if visited[i] ==False: #Don't recur for u if it is already visited                if(self.isCyclicUtil(i,visited,-1))== True:                    return True                 return False # Create a graph given in the above diagramg = Graph(5)g.addEdge(1, 0)g.addEdge(0, 2)g.addEdge(2, 0)g.addEdge(0, 3)g.addEdge(3, 4) if g.isCyclic():    print "Graph contains cycle"else :    print "Graph does not contain cycle "g1 = Graph(3)g1.addEdge(0,1)g1.addEdge(1,2)  if g1.isCyclic():    print "Graph contains cycle"else :    print "Graph does not contain cycle "  #This code is contributed by Neelam Yadav<\/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 and graph<\/a> is represented using adjacency list. So the time complexity is O(V+E)<\/strong><\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Python 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,4148],"tags":[76523,76185,76184,76187,76525,76190,76522,76524],"class_list":["post-25988","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-coding","category-dfs-and-bfs","category-graph-algorithms","category-python","tag-cycle-in-directed-graph","tag-detect-cycle-in-directed-graph-in-c","tag-detect-cycle-in-directed-graph-java","tag-detect-cycle-in-undirected-graph-in-c","tag-detect-cycle-in-undirected-graph-java","tag-find-all-cycles-in-a-directed-graph","tag-find-all-cycles-in-an-undirected-graph","tag-find-cycle-in-undirected-graph"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25988","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=25988"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25988\/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=25988"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25988"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25988"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}