Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Shortest cycle

Last Updated on March 31, 2022 by Ria Pathak

Hard

### Problem Statement :

Given a graph we have to find the length of the shortest cycle in the given graph. If no cycle exists print `−1`.

See original problem statement here

### Solution Approach :

#### Introduction :

Idea is to check the length of the cycle from every vertex and print the minimum length, if no cycle is present print `-1`.

We can use BFS to store the cycle length for every vertex.

#### Description :

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

#### Algorithms :

shortest_cycle() :

1. create a queue and push the current vertex now perform following operations untill the queue is not empty:

2. each time we pop a vertex `v` from queue, ( `v` = queue.front() ), we will mark the vertex `v` as visited (`visited[v]= true`).

3. Iterate for all the adjacent vertices of `v` and for every adjacent vertex `a`, do following :

• update the parent and distance as, `parent[a] = v` and `distance[a]= distance[v]+1`.
• push `a` into the queue.
• if `a` is not visited,
and if `parent[v] != a`.
• update the ans ( ans = min(ans,current cycle length) ).

### Complexity Analysis:

The time complexity of the above method is represented in the form of `O(V+E)`, where `V` is the number of verices and `E` is the number of edges.

### Solutions:

```
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define INT_MAX 99999
#define INT_MIN -99999

struct node {
int vertex;
struct node* next;
};
struct node* createNode(int);

struct Graph {
int numVertices;
};

// Create a node
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}

// Create a graph
struct Graph* createAGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;

graph->adjLists = malloc(vertices * sizeof(struct node*));

int i;
for (i = 0; i < vertices; i++)

return graph;
}

void addEdge(struct Graph* graph, int s, int d) {
// Add edge from s to d
struct node* newNode = createNode(d);

// Add edge from d to s
newNode = createNode(s);
}

// Print the graph
void printGraph(struct Graph* graph) {
int v;
for (v = 0; v < graph->numVertices; v++)
{
//printf("\n Vertex %d\n: ", v);
while (temp) {
printf("%d ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}

//QUEUE
struct Queue
{
int front, rear, size;
unsigned capacity;
int* array;
};

// function to create a queue of given capacity.
// It initializes size of queue as 0
struct Queue* createQueue(unsigned capacity)
{
struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1;  // This is important, see the enqueue
queue->array = (int*) malloc(queue->capacity * sizeof(int));
return queue;
}

// Queue is full when size becomes equal to the capacity
int isFull(struct Queue* queue)
{  return (queue->size == queue->capacity);  }

// Queue is empty when size is 0
int isEmpty(struct Queue* queue)
{  return (queue->size == 0); }

// Function to add an item to the queue.
// It changes rear and size
void enqueue(struct Queue* queue, int item)
{
if (isFull(queue))
return;
queue->rear = (queue->rear + 1)%queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
}

// Function to remove an item from queue.
// It changes front and size
int dequeue(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1)%queue->capacity;
queue->size = queue->size - 1;
return item;
}

// Function to get front of queue
int front(struct Queue* queue)
{
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}

int min(int a,int b)
{
return (a<b)?a:b;
}

int shortest_cycle(struct Graph* graph,int n)
{
// To store length of the shortest cycle
int ans = INT_MAX;

// For all vertices
for (int i = 0; i < n; i++) {

// Make distance maximum
int dist[n];
for(int i=0;i<n;i++)
dist[i]=INT_MAX;

// Take a imaginary parent
int par[n] ;
for(int i=0;i<n;i++)
par[i]= -1;

// Distance of source to source is 0
dist[i] = 0;
struct Queue* q = createQueue(1000);

// Push the source element
enqueue(q,i);

// Continue until queue is not empty
while (!isEmpty(q)) {

// Take the first element
int x = front(q);
dequeue(q);

// Traverse for all it's childs
while(temp) {

// If it is not visited yet
if (dist[temp->vertex] == INT_MAX) {

// Increase distance by 1
dist[temp->vertex] = 1 + dist[x];

// Change parent
par[temp->vertex] = x;

// Push into the queue
enqueue(q,temp->vertex);
}

// If it is already visited
else if (par[x] != temp->vertex)
ans = min(ans, dist[x] + dist[temp->vertex] + 1);

temp = temp->next;
}
}
}

// If graph contains no cycle
if (ans == INT_MAX)
return -1;

// If graph contains cycle
else
return ans;
}

int main()
{
int t;
scanf("%d",&t);
while(t--)
{

int n ,e;
scanf("%d %d",&n,&e);
struct Graph* graph = createAGraph(n);

while(e--)
{

int u,v;
scanf("%d %d",&u,&v);
}
printf("%d\n",shortest_cycle(graph,n));

}

return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;
#define N 10000

vector<int> gr[N];

{
gr[x].push_back(y);
gr[y].push_back(x);
}

// Function to find the length of
// the shortest cycle in the graph
int shortest_cycle(int n)
{
// To store length of the shortest cycle
int ans = INT_MAX;

// For all vertices
for (int i = 0; i < n; i++) {

// Make distance maximum
vector<int> dist(n, INT_MAX);

// Take a imaginary parent
vector<int> par(n, -1);

// Distance of source to source is 0
dist[i] = 0;
queue<int> q;

// Push the source element
q.push(i);

// Continue until queue is not empty
while (!q.empty()) {

// Take the first element
int x = q.front();
q.pop();

// Traverse for all it's childs
for (int child : gr[x]) {

// If it is not visited yet
if (dist[child] == INT_MAX) {

// Increase distance by 1
dist[child] = 1 + dist[x];

// Change parent
par[child] = x;

// Push into the queue
q.push(child);
}

// If it is already visited
else if (par[x] != child)
ans = min(ans, dist[x] + dist[child] + 1);
}
}
}

// If graph contains no cycle
if (ans == INT_MAX)
return -1;

// If graph contains cycle
else
return ans;
}

int main()
{
int t;
cin>>t;
while(t--)
{

int n ,e;
cin>>n>>e;
for(int i=0;i<e;i++)
gr[i].clear();

while(e--)
{

int u,v;
cin>>u>>v;
}
cout <<shortest_cycle(n)<<endl;

}

return 0;
}
```
```
import java.util.*;

class Main
{

static final int N = 100200;
@SuppressWarnings("unchecked")
static Vector<Integer>[] gr = new Vector[N];

static void Add_edge(int x, int y)
{
}

// Function to find the length of
// the shortest cycle in the graph
static int shortest_cycle(int n)
{

// To store length of the shortest cycle
int ans = Integer.MAX_VALUE;

// For all vertices
for (int i = 0; i < n; i++)
{

// Make distance maximum
int[] dist = new int[n];
Arrays.fill(dist, (int) 1e9);

// Take a imaginary parent
int[] par = new int[n];
Arrays.fill(par, -1);

// Distance of source to source is 0
dist[i] = 0;

// Push the source element

// Continue until queue is not empty
while (!q.isEmpty())
{

// Take the first element
int x = q.poll();

// Traverse for all it's childs
for (int child : gr[x])
{
// If it is not visited yet
if (dist[child] == (int) (1e9))
{

// Increase distance by 1
dist[child] = 1 + dist[x];

// Change parent
par[child] = x;

// Push into the queue
}
else if (par[x] != child && par[child] != x)
ans = Math.min(ans, dist[x] + dis[child] + 1);
}
}
}

// If graph contains no cycle
if (ans == Integer.MAX_VALUE)
return -1;

// If graph contains cycle
else
return ans;
}

// Driver Code
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0)
{
int n = sc.nextInt();
int e = sc.nextInt();
for (int i = 0; i < n; i++)
gr[i] = new Vector<>();

while(e-->0)
{
int u = sc.nextInt();
int v = sc.nextInt();
}

// Function call
System.out.println(shortest_cycle(n));
}
}
}
```

[forminator_quiz id="2125"]

This article tried to discuss Breadth First Search. Hope this blog helps you understand and solve the problem. To practice more problems on Breadth First Search you can check out MYCODE | Competitive Programming.