Cycles in an Undirected Graph

Question

Given an undirected graph G  V  E  with n vertices   V    n   how do you find if it contains a cycle in O n

User · Answer

I believe that the assumption that the graph is connected can be handful  thus  you can use the proof shown above  that the running time is O  V    if not  then  E   V   reminder  the running time of DFS is O  V   E

User · Answer

I started studying graphs recently  I wrote a piece of code in java that could determine if a graph has cycles  I used DFT to find cycles in the graph  Instead of recurssion I used a stack to traverse the graph   At a high level DFT using a stack is done in the following steps   Visit a Node If the node is not in the visited list add it to the list and push it to the top of the stack Mark the node at the top of the stack as the current node  Repeat the above for each adjacent node of the current node If all the nodes have been visited pop the current node off the stack   I performed a DFT from each node of the Graph and during the traversal if I encountered a vertex that I visited earlier  I checked if the vertex had a stack depth greater than one  I also checked if a node had an edge to itself and if there were multiple edges between nodes  The stack version that I originally wrote was not very elegant  I read the pseudo code of how it could be done using recursion and it was neat  Here is a java implementation  The LinkedList array represents a graph  with each node and it s adjacent vertices denoted by the index of the array and each item respectively  class GFG   Boolean isCyclic int V  LinkedList lt Integer gt    alist        List lt Integer gt  visited   new ArrayList lt Integer gt         for  int i   0  i  lt  V  i              if   visited contains i                 if  isCyclic i  alist  visited  -1                   return true                      return false     Boolean isCyclic int vertex  LinkedList lt Integer gt    alist  List lt Integer gt  visited  int parent        visited add vertex       for  Iterator lt Integer gt  iterator   alist vertex  iterator    iterator hasNext               int element   iterator next            if   visited contains element                 if  isCyclic element  alist  visited  vertex                   return true            else if  element    parent              return true            return false

User · Answer

An undirected graph is acyclic  i e   a forest  if a DFS yields no back edges  Since back edges are those edges  u  v  connecting a vertex u to an ancestor v in a depth-first tree  so no back edges means there are only tree edges  so there is no cycle  So we can simply run DFS  If find a back edge  there is a cycle  The complexity is O V  instead of O E   V   Since if there is a back edge  it must be found before seeing  V  distinct edges  This is because in a acyclic  undirected  forest   E     V    1

User · Answer

Actually  depth first  or indeed breadth first  search isn t quite enough  You need a sightly more complex algorithm   For instance  suppose there is  graph with nodes  a b c d  and edges   a b   b c   b d   d c   where an edge  x y  is an edge from x to y    looks something like this  with all edges directed downwards         a                     b              d                           c    Then doing depth first search may visit node  a   then  b   then  c   then backtrack to  b   then visit  d   and finally visit  c  again and conclude there is a cycle -- when there isn t  A similar thing happens with breadth first    What you need to do is keep track of which nodes your in the middle of visiting  In the example above  when the algorithm reaches  d  it has finished visiting  c  but not  a  or  b   So revisiting a finished node is fine  but visiting an unfinished node means you have a cycle  The usual way to do this is colour each node white not yet visited   grey visiting descendants   or black finished visiting    here is some pseudo code    define visit node n     if n colour    grey    if we re still visiting this node or its descendants     throw exception  Cycle found      n colour   grey   to indicate this node is being visited   for node child in n children        if child colour    white    if the child is unexplored       visit child     n colour   black   to show we re done visiting this node   return   then running visit root node  will throw an exception if and only if there is a cycle  initially all nodes should be white

User · Answer

An undirected graph without cycle has  E   lt   V -1   public boolean hasCycle Graph g        int totalEdges   0     for Vertex v   g getVertices           totalEdges    v getNeighbors   size            return totalEdges 2  gt  g getVertices   size - 1

User · Answer

I think that depth first search solves it  If an unexplored edge leads to a node visited before  then the graph contains a cycle  This condition also makes it O n   since you can explore maximum n edges without setting it to true or being left with no unexplored edges

User · Answer

A simple DFS does the work of checking if the given undirected graph has a cycle or not   Here s the C   code to the same   The idea used in the above code is      If a node which is already discovered visited is found again and is   not the parent node   then we have a cycle    This can also be explained as below mentioned by  Rafal Dowgird      If an unexplored edge leads to a node visited before  then the graph contains a cycle

User · Answer

The answer is  really  breadth first search  or depth first search  it doesn t really matter   The details lie in the analysis   Now  how fast is the algorithm   First  imagine the graph has no cycles  The number of edges is then O V   the graph is a forest  goal reached   Now  imagine the graph has cycles  and your searching algorithm will finish and report success in the first of them  The graph is undirected  and therefore  the when the algorithm inspects an edge  there are only two possibilities  Either it has visited the other end of the edge  or it has and then  this edge closes a circle  And once it sees the other vertex of the edge  that vertex is  inspected   so there are only O V  of these operations  The second case will be reached only once throughout the run of the algorithm

User · Answer

Here is a simple implementation in C   of algorithm that checks if a graph has cycle s  in O n  time  n is number of vertexes in the Graph   I do not show here the Graph data structure implementation  to keep answer short   The algorithms expects the class Graph to have public methods   vector lt int gt  getAdj int v  that returns vertexes adjacent to the v and int getV   that returns total number of vertexes  Additionally  the algorithms assumes the vertexes of the Graph are numbered from 0 to n - 1   class CheckCycleUndirectedGraph   private      bool cyclic      vector lt bool gt  visited       void depthFirstSearch const Graph amp  g  int v  int u            visited v    true          for  auto w   g getAdj v                 if   visited w                     depthFirstSearch g  w  v                             else if  w    u                    cyclic   true                  return                                 public      CheckCycleUndirectedGraph const Graph amp  g    cyclic false            visited   vector lt bool gt  g getV    false           for  int v   0  v  lt  g getV    v                  if   visited v                    depthFirstSearch g  v  v                   if cyclic                    break                                     bool containsCycle   const           return cyclic             Keep in mind that Graph may consist of several not connected components and there may be cycles inside of the components  The shown algorithms detects cycles in such graphs as well

User · Answer

I believe using DFS correctly also depends on how are you going to represent your graph in the code  For example suppose you are using adjacent lists to keep track of neighbor nodes and your graph has 2 vertices and only one edge  V  1 2  and E   1 2    In this case starting from vertex 1  DFS will mark it as VISITED and will put 2 in the queue  After that it will pop vertex 2 and since 1 is adjacent to 2  and 1 is VISITED  DFS will conclude that there is a cycle  which is wrong   In other words in Undirected graphs  1 2  and  2 1  are the same edge and you should code in a way for DFS not to consider them different edges  Keeping parent node for each visited node will help to handle this situation

User · Answer

Here is the code I ve written in C based on DFS to find out whether a given graph is connected cyclic or not  with some sample output at the end  Hope it ll be helpful      include lt stdio h gt   include lt stdlib h gt        Global Variables      int A 20  20  visited 20  v 0 count 0 n  int seq 20  s 0 connected 1 acyclic 1        DFS Function Declaration      void DFS          DFSearch Function Declaration      void DFSearch int cur         Main Function      int main                 int i j       printf   nEnter no of Vertices          scanf   d   amp n        printf   nEnter the Adjacency Matrix 1 0   n        for i 1 i lt  n i                for j 1 j lt  n j            scanf   d   amp A i  j         printf   nThe Depth First Search Traversal  n         DFS         for i 1 i lt  n i            printf   c  d t   a  seq i -1 i        if connected  amp  amp  acyclic     printf   n nIt is a Connected  Acyclic Graph         if  connected  amp  amp  acyclic    printf   n nIt is a Not-Connected  Acyclic Graph         if connected  amp  amp   acyclic    printf   n nGraph is a Connected  Cyclic Graph         if  connected  amp  amp   acyclic   printf   n nIt is a Not-Connected  Cyclic Graph          printf   n n        return 0             DFS Function Definition      void DFS              int i      for i 1 i lt  n i            if  visited i                       if i gt 1  connected 0          DFSearch i                                    DFSearch Function Definition      void DFSearch int cur             int i j      visited cur    count           seq count  cur           for i 1 i lt count-1 i                    if A cur  seq i                        acyclic 0       for i 1 i lt  n i            if A cur  i   amp  amp   visited i              DFSearch i                Sample Output   majid majid-K53SC   Desktop  gcc BFS c  majid majid-K53SC   Desktop    a out                                       Enter no of Vertices  10  Enter the Adjacency Matrix 1 0    0 0 1 1 1 0 0 0 0 0  0 0 0 0 1 0 0 0 0 0  0 0 0 1 0 1 0 0 0 0  0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0  0 1 0 0 1 0 0 0 0 0  0 0 0 0 0 0 0 1 0 0  0 0 0 0 0 0 0 0 1 0  0 0 0 0 0 0 0 0 0 1  0 0 0 0 0 0 1 0 0 0   The Depdth First Search Traversal  a 1 c 2 d 3 f 4 b 5 e 6 g 7 h 8 i 9 j 10      It is a Not-Connected  Cyclic Graph    majid majid-K53SC   Desktop    a out                                       Enter no of Vertices  4  Enter the Adjacency Matrix 1 0   0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 1  The Depth First Search Traversal  a 1 c 2 b 3 d 4   It is a Connected  Acyclic Graph    majid majid-K53SC   Desktop    a out                                       Enter no of Vertices  5  Enter the Adjacency Matrix 1 0   0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0  0 0 1 0 0  The Depth First Search Traversal  a 1 d 2 b 3 c 4 e 5   It is a Not-Connected  Acyclic Graph

User · Answer

By the way  if you happen to know that it is connected  then simply it is a tree  thus no cycles  if and only if  E   V -1  Of course that s not a small amount of information

User · Answer

As others have mentioned    A depth first search will solve it  In general depth first search takes O V   E  but in this case you know the graph has at most O V  edges  So you can simply run a DFS and once you see a new edge increase a counter  When the counter has reached V you don t have to continue because the graph has certainly a cycle  Obviously this takes O v

User · Answer

DFS APPROACH WITH A CONDITION parent    next node  Let s see the code and then understand what s going on    bool Graph  isCyclicUtil int v  bool visited    int parent             Mark the current node as visited      visited v    true           Recur for all the vertices adjacent to this vertex      list lt int gt   iterator i       for  i   adj v  begin    i    adj v  end      i                     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        The above code explains itself but I will try to explain one condition i e   i    parent Here if suppose graph is   1--2  Then when we are at 1 and goes to 2  the parent for 2 becomes 1 and when we go back to 1 as 1 is in adj matrix of 2 then since next vertex 1 is also the parent of 2 Therefore cycle will not be detected for the immediate parent in this DFS approach  Hence Code works fine

User · Answer

A connected  undirected graph G that has no cycles is a tree  Any tree has exactly n - 1 edges  so we can simply traverse the edge list of the graph and count the edges  If we count n - 1 edges then we return    yes    but if we reach the nth edge then we return    no     This takes O  n  time because we look at at most n edges   But if the graph is not connected then we would have to use DFS  We can traverse through the edges and if any unexplored edges lead to the visited vertex then it has cycle

User · Answer

You can use boost graph library and cyclic dependencies  It has the solution for finding cycles with back edge function

User · Answer

You can solve it using DFS  Time complexity  O n  The essence of the algorithm is that if a connected component graph does NOT contain a CYCLE  it will always be a TREE See here for proof Let us assume the graph has no cycle  i e  it is a tree  And if we look at a tree  each edge from a node  1 either reaches to its one and only parent  which is one level above it  2 or reaches to its children  which are one level below it  So if a node has any other edge which is not among the two described above  it will obviously connect the node to one of its ancestors other than its parent  This will form a CYCLE  Now that the facts are clear  all you have to do is run a DFS for the graph  considering your graph is connected  otherwise do it for all unvisited vertices   and IF you find a neighbor of the node which is VISITED and NOT its parent  then my friend there is a CYCLE in the graph  and you re DONE  You can keep track of parent by simply passing the parent as parameter when you do DFS for its neighbors  And Since you only need to examine n edges at the most  the time complexity will be O n   Hope the answer helped

[algorithm] Cycles in an Undirected Graph

Examples related to algorithm

Examples related to graph

Examples related to graph-theory