{"id":2020,"date":"2020-07-01T09:50:55","date_gmt":"2020-07-01T09:50:55","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2020"},"modified":"2022-03-31T12:15:18","modified_gmt":"2022-03-31T12:15:18","slug":"shortest-cycleminor-image-correction-ex-2","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/shortest-cycleminor-image-correction-ex-2\/","title":{"rendered":"Shortest cycle"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Breadth First Search<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given a graph we have to find the length of the shortest cycle in the given graph. If no cycle exists print \u22121<\/code>.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

Idea is to check the length of the cycle from every vertex and print the minimum length, if no cycle is present print -1<\/code>.<\/p>\n

We can use BFS to store the cycle length for every vertex. <\/p>\n<\/blockquote>\n

Description :<\/h4>\n

We will iterate for all vertices and store distance and parent of every vertex v<\/code> using distance[ ] and parent[ ] array. Now for every v<\/code> iterate for all its adjacent vertices a<\/code>, if a<\/code> is not visited update its distance (distance[a] = distance[v]+1) and parent (parent[a] = v). If a<\/code> is already visited check if parent[a] is v<\/code> or not, if not then there is a cycle. Now update the minimum cycle length if the current cycle length is shorter.<\/p>\n

\"\"<\/p>\n

Algorithms :<\/h4>\n

shortest_cycle()<\/strong> :<\/p>\n

    \n
  1. \n

    create a queue and push the current vertex now perform following operations untill the queue is not empty:<\/p>\n<\/li>\n

  2. \n

    each time we pop a vertex v<\/code> from queue, ( v<\/code> = queue.front() ), we will mark the vertex v<\/code> as visited (visited[v]= true<\/code>).<\/p>\n<\/li>\n

  3. \n

    Iterate for all the adjacent vertices of v<\/code> and for every adjacent vertex a<\/code>, do following :<\/p>\n

      \n
    • update the parent and distance as, parent[a] = v<\/code> and distance[a]= distance[v]+1<\/code>.<\/li>\n
    • push a<\/code> into the queue.<\/li>\n
    • if a<\/code> is not visited,
      \nand if parent[v] != a<\/code>. <\/li>\n
    • update the ans ( ans = min(ans,current cycle length) ).<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n

      Complexity Analysis:<\/h3>\n
      \n

      The time complexity<\/strong> of the above method is represented in the form of O(V+E)<\/code>, where V<\/code> is the number of verices and E<\/code> is the number of edges.<\/p>\n<\/blockquote>\n

      Solutions:<\/h3>\n

      \t\t\t\t\t\t