Detect Cycle in a Directed Graph | GeeksforGeeks

Поделиться
HTML-код
  • Опубликовано: 24 дек 2024

Комментарии • 68

  • @clumsycoco
    @clumsycoco 6 лет назад +94

    Set speed to 1.5. You're welcome!

  • @rakeshswarankar
    @rakeshswarankar 6 лет назад +2

    I believe we can use BFS (use queue) or DFS(use stack), all we care about visited nodes. In BFS we marked a node as visited once we put down all the adjacent nodes in queue. Correct me if I am wrong :)

  • @treyquattro
    @treyquattro 4 года назад +8

    why do so many GeeksForGeeks C++ solutions leak memory? Lazily converted from Java I suspect.

    • @hil449
      @hil449 2 года назад

      Yea that new is ridiculous. Also why do they insist on using c style array instead of vectors?

  • @priyagupta1936
    @priyagupta1936 4 года назад +2

    Why do we need to check visited array ? can't we just check what's in the recstack to decide the cycle ?

  • @mahesh23343
    @mahesh23343 4 года назад +1

    Tushar Roy told it better. The stack is a DS that should not be even mentioned here.

  • @imochurad
    @imochurad 3 года назад +3

    Please add an explanation why rec stack is required on top of the visited array. It is not obvious at all.

    • @JanardhanaRaoAnala
      @JanardhanaRaoAnala 2 года назад +1

      Assume you have three nodes, 1, 2, and 3, as well as the edges 1->2, 1->3, and 2->3. In this graph, there is no cycle. If you don't utilize a recursive stack and only use a visited array, your visited array would look like this: You'd go to 1 (2 & 3 are adjacent to 1, you would call dfs on both as well). Let's say you visit node 2 first from node 1. Because of DFS, you will also visit node 3 from node 2. Your visited list so far will be [1,2,3]. After that, you'd visit node 3 because it hasn't been visited yet from 1. Now, You would think there's a cycle because your visited list already has node 3, but there isn't one. So, the stack is required for directed graphs.

    • @ashar8152
      @ashar8152 2 года назад

      @@JanardhanaRaoAnala no need of recursion stack if we just make visited array as vector type and pass it by value in parameter. they have used pass by reference therefore they have to explicitly use recursion stack otherwise recursion function take care of this if pass by value.

  • @adhaarsharma753
    @adhaarsharma753 3 года назад +2

    How can a node be visited yet not be present in the recursion stack?

    • @44vinith
      @44vinith 3 года назад

      Think of a multi component case, then it'll be different

  • @phule9000
    @phule9000 3 года назад

    that's exactly what i was looking for, many thanks!

  • @usamaalioffical
    @usamaalioffical 7 лет назад +6

    Nice Explanation Lots of Love From Pakistan

  • @lets_see_777
    @lets_see_777 5 лет назад +1

    "Visited and in Stack right now"-----just visualize this yourself on a few graphs and you will get it

    • @priyagupta1936
      @priyagupta1936 4 года назад

      Why do we need to check visited array ? can't we just check what's in the recstack to decide the cycle ?

    • @kewtomrao
      @kewtomrao 3 года назад

      @@priyagupta1936 No because we need to detect the backedge ie relation with ancestor.Hence we need to check for both the recr stack and visited array

  • @praveenab9291
    @praveenab9291 5 лет назад +1

    Can't we go with the approach which we use for linked list?

  • @yuqiu8247
    @yuqiu8247 6 лет назад +2

    Could anybody explain why we need a rec-stack besides the visited list?

    • @nazninmalek4440
      @nazninmalek4440 6 лет назад +9

      I think rec-stack array is different from visited array, it will contain all the vertices while traversing any path from one vertex to its adjacent vertices and so on, once we reach to a vertex which does not have any adjacent vertices, we remove that vertex from rec-stack array and then traverse another path.While traversing one particular path, if we encounter a vertex which is already in that rec-stack then cycle exists. If we don't use rec-stack array then it may give correct output in directed cyclic graph , but for directed acyclic graph, it will give wrong output.

    • @goelshubham46
      @goelshubham46 4 года назад +1

      for acyclic graphs

  • @GautamSingh-yn9cb
    @GautamSingh-yn9cb 7 лет назад

    @4:08 what if 1 does not have any other connected node except 0 , then how do you get 2 ? as you have not pushed it to stack

    • @brainchallenge9273
      @brainchallenge9273 7 лет назад +4

      you delete 1 from stack, going back a step, and then explore other paths from 0, which is 2, pushing it back on the stack

  • @abhishekraj-kf3zc
    @abhishekraj-kf3zc 7 лет назад +4

    how to check the longest cycle in given graph.?

    • @koiralabros7219
      @koiralabros7219 3 года назад

      Give each node a level each time you go to the next one. When you find a cycle, check the difference between the levels of both the nodes. Keep track of this difference value for every cycle you identify in the graph. And return the maximum value.

  • @atextful
    @atextful 7 лет назад +3

    But, in reality the stack isn't a stack. It's a list, right? It's only saving the visited nodes, but it isn't popping them.

    • @GeeksforGeeksVideos
      @GeeksforGeeksVideos  7 лет назад

      For backedge detection, we need to keep track of nodes that are in our recursion stack which are not the same as visited nodes.
      We are using a list as it facilitate O(1) check to the presence of nodes in recursion stack.
      recStack[v] = true; // makes a node part of the stack
      recStack[v] = false;// removes the vertex from stack
      However the order is not of any importance for that matter.
      The code given stops on finding a single backedge.

  • @ovuncuzun
    @ovuncuzun 3 года назад +1

    Thank you very much

  • @RobertPodosek
    @RobertPodosek Год назад

    Where does 'adj' come from?

  • @amankhunt3620
    @amankhunt3620 7 лет назад +1

    Is there a need of stack. we can even keep an array of nodes(visited[]) in whichwe will mark 1 if visited else 0.Now if we find an adjacent node 'u' while exploring node 'v' allready visited in array there is cycle else not.

    • @brainchallenge9273
      @brainchallenge9273 7 лет назад +4

      The stack in this example is your array of visited nodes that you propose. It's saving the current path from the node you chose to start with. That's working too, but imagine we don't have any cycles in the graph, then you'll go through the same paths over and over again, because you forget you've already tried them. That's why you need a separate visited array that keeps track of all the visited nodes.

    • @batusun717
      @batusun717 6 лет назад +1

      infinite loop without visited array

    • @giteshkhanna2633
      @giteshkhanna2633 6 лет назад

      If you maintain a single visited array in this case. That means you are going to implement a block of code for when something is already visited. But that is going to create an infinite loop since you have no way to stop the code.

  • @vipulkrishna19
    @vipulkrishna19 5 лет назад +5

    volume is so low.try to keep it high

  • @aradhyajain9575
    @aradhyajain9575 7 лет назад

    what is the modification you have made for undirected than directed graph

    • @prabhatism
      @prabhatism 5 лет назад

      The modification is in the input.
      if a and b are linked. In undirected, both will be adjacent to each other but in directed(assume a to b) only the adjacency will be from a to b and not b to a, which will be in the case of undirected.

  • @amit2197kumar
    @amit2197kumar 8 лет назад +1

    very nice explanation .

  • @surajitroy_roll-5023
    @surajitroy_roll-5023 4 года назад

    Good I liked the explanation

  • @sulabhprasad2922
    @sulabhprasad2922 5 лет назад

    Can anyone tell if the edge from 0 to 2 can also be considered as back edge instead of 2 to 0?

  • @ManishSharma-xq9be
    @ManishSharma-xq9be 7 лет назад

    How many cycles are in there in graph?
    2 or 3

  • @manishranjan9373
    @manishranjan9373 4 года назад +1

    A better example could have been given.

  • @alaayahia5356
    @alaayahia5356 2 года назад

    Thank you!

  • @isaacdouglas1119
    @isaacdouglas1119 3 года назад

    This video would be very helpful if I could hear it :)

  • @Foba_Bett
    @Foba_Bett 7 лет назад

    Thanks a lot mister :)!

  • @alexeystaroverov4804
    @alexeystaroverov4804 6 лет назад

    Is it possible to use queue , list or array instead of stack? what is the reason you selected stack?

  • @shaikhnabeel6443
    @shaikhnabeel6443 3 года назад +2

    why are speaking like someone is sleeping next to you and you can't speak loudly and have to make video too.😐

  • @sayanroy9161
    @sayanroy9161 3 года назад

    You just reading the code.

  • @Ankitjha0502
    @Ankitjha0502 5 лет назад +2

    this is wrong....
    check for matrix
    0 1 0 0
    0 0 1 0
    0 0 0 0
    1 0 0 0
    There is no cycle but this approach says yes there is

  • @tianyuez
    @tianyuez 6 лет назад +8

    Hello friends! (Indian accent)

  • @demidrek-heyward
    @demidrek-heyward 6 лет назад

    thanks!

  • @hil449
    @hil449 2 года назад

    Every single time there's c++ code in geeksforgeeks it throws best practices out of the window. Why tf are you using a c style array instead of a vector? And why that new? Your code is leaking memory lmao

  • @alekseevaleksandr
    @alekseevaleksandr 6 лет назад

    I do not hear anything!

  • @kuladeepmazumdar346
    @kuladeepmazumdar346 5 лет назад

    Remove the subtitles man. I am seeing nothing

  • @shivambhardwaj7605
    @shivambhardwaj7605 8 лет назад

    "This video is contributed by Illuminati."
    Who is Illuminati ?

  • @prajwalrao1004
    @prajwalrao1004 4 года назад

    Why don't we have a speed faster than 2x😂🤦

  • @shreyaspadhye7337
    @shreyaspadhye7337 4 года назад

    The guy's voice is so irritating