Is a Graph Cyclic? | Graph Data Structure | Cycles in Graphs in JAVA

Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we explain about cyclic algorithms in a graphs and state the problem where:
1. You are given a graph.
2. You are required to find and print if the graph is cyclic.
For a better experience and more exercises, VISIT: www.pepcoding....
#graphs #datastructures #algorithms
Have a look at our result: www.pepcoding....
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Join us on Telegram: t.me/joinchat/...

[@sudhanshusharma9123]

"Umeed karta hun aapko maza aaya hoga", Han sir explanation me toh aaya hi aaya saath me last ke dance steps me bhi!

[@Pepcoding]

Thank you so much and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@shashankpal6699]

Ganesh Gaitonde of DSA.
आपको शत्-शत् नमन

[@e431215]

Will this cover case 0 -> 1 -> 2 -> 0 ?
Cyclic is (0 to 1 to 2 to 0), as a cyclic path. This solution is (0 to 1 to 2) and (0 to 2).

[@shang_chi4651]

Sir gaana mast tha 😂mazaa aata hai jab shandaar padhane waala koi teacher badhiya gaana bhi gaaye to😁

[@Pepcoding]

Thank you beta and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@cautioni]

sir what about directed graphs?

[@ShivamMishra-qt9yy]

sir! this is not working in Directed Cyclic graph i.e. (0->1->2->0)

[@adarshdubey1784]

Sir, Will this technique work for both directed and undirected graph?

[@___vandanagupta___]

Same question

[@adarshdubey1784]

@@___vandanagupta___ No it will not

[@ayushmansharma5321]

@@___vandanagupta___ for Directed Cyclic Graph,we need to take help of topological sort
As topological Sort is only possible for DAG(Directed Acyclic Graph),So apply that strategy for finding whether the graph contains a a cycle or not.

[@___vandanagupta___]

@@ayushmansharma5321 thnks

[@user-pr6lv7nd6l]

How this is different from using parent array

[@shreshthsingh7744]

Nice Dance Sir😍😍😍

[@Pepcoding]

Thanks 😊

[@lakshyadalal1698]

Jaat tutor😘 bhai greatt 👍

[@Pepcoding]

Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@lakshyadalal1698]

@@Pepcoding bilkul sir aapne jo doubt clear kia why stack worked but not preorder was the real doubt i had while solving problem sir one suggestion code smjhate smay c++ ka bhi btadia kro kuch difficult ya unusual syntax k lie

[@lakshyadalal1698]

@@Pepcoding stack or preorder vali dusri video thi topological sort ki*

[@sumitshokeen4065]

@@lakshyadalal1698 Ram Ram Lakhay bhai

[@ayushmansharma5321]

We can also use DFS Strategy for finding cycle in the graph or not(without forming Pair Class)
//Here is the code :
//(Note: I have considered that my Graph contain multiple components,so it can work in any situation)
//Also to make code simple any easy to read ,I have not created any Edge class ,because there is no use of weight and (parent while storing in graph).
import java.util.*;
import java.io.*;
public class Main{
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int vtces = Integer.parseInt(br.readLine());
int edges = Integer.parseInt(br.readLine());
ArrayList[] graph = new ArrayList[vtces];
for(int i=0;i

[@ShivamKhantwal94]

can we use DFS here ?

[@aakash1763]

Will this work for directed graph?

[@ueeabhishekkrsahu]

sir where is level 2 of graph

[@RahulGupta-xc4fg]

If a graph have components then simply it doesn't means that it is a cyclic graph ,
instead of iterating it for all vertices
i considered it and all test cases runs successfully.
am i missing any insight...

[@Pepcoding]

It may have a cycle in one of its components

[@Pepcoding]

You are confusing cyclic with connected

[@RahulGupta-xc4fg]

@@Pepcoding okay sir thank you so much :)

[@harshtekriwal131]

Sir ise Union Find wale tarike se bi krwadena , Kafi question deke hai uspe

[@Pepcoding]

hanji. level2 mei wo sabse important topic hai.

[@prashantsingh1621]

@@Pepcoding level 2 ke liye buy karna hoga kya?

[@kumarpriyansh4238]

Sir is it possible for you to make a video on how to handle non integer vertex graphs (ex String or character) or graph with random vertex numbers.

[@rohansinghjr1195]

use character array as visited, rest index will do.

[@ManishTiwari-ge1wc]

Good Explanation

[@Pepcoding]

Thankyou beta,
I am glad you liked the video. I also hope that you are watching till end.
Will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms)

[@illegalcall]

Sir, when will level 2 graph start?

[@Pepcoding]

Beta, shuru kr he diya h content, uska bhi jaldi kr he denge shuru.

[@gauravnarang955]

what about cycle in directed graph?

[@Pepcoding]

That will be covered in a separate video

[@adarshdubey1784]

sir , i think this approach won't work for self loop nodes? ..is it so ?

[@namanjain9922]

I also think so not working for self loop.

[@ishikajain6115]

Sir graphs kb tk hoga khtm?

[@Pepcoding]

Aj khatam

[@mehulshrimali1951]

Sir, so how can we do this question usinf DFS?

[@swapnilpadaya163]

private static boolean isCylic(ArrayListgraph[], Set visited,int prevSrc, int src){
visited.add(src);
for(Edge edge : graph[src]){
if(edge.nbr != prevSrc && visited.contains(edge.nbr) == true){
return true;
}
if(visited.contains(edge.nbr) == false){
boolean ans = isCylic(graph,visited,src,edge.nbr);
if(ans){
return true;
}
}
}
return false;
}
I am basically keeping track of previously visited vertex. and rest is explained by sir. same concept of bfs over here

[@vikasjoshi7236]

@@swapnilpadaya163 thnx

[@loserfruit9663]

@@swapnilpadaya163 nice

[@_s_h_l_o_k_]

If you went to search for the song- Na mili hai na 😂😂😂😂

[@gouravsingla5622]

I think it is wrong. It will again visit the parent.

[@harshitkaushik4144]

Sabki maut ka badla lega ye faizal (Sumeet sir saying this to all those students who are not able to get placement but he is assuring us that he will surely help us to reach there).

[@Pepcoding]

Hahaha😅🙊😈