Блог пользователя aman_naughty

Автор aman_naughty, история, 5 лет назад, По-английски

I want help please don't down-vote.

I want to print the cycle in an undirected graph. I know how to detect cycle in an undirected graph but can't determine how to find the vertices involved in the cycle. Here is the code to find cycle.

code

Can someone please tell me how to modify this so that I can get the vertices in the cycle as well.

I have seen geeksforgeeks article on printing all cycles but I can't understand it. Is there some simpler approach ?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello! To do that you can use stack. In DFS you can push visited vertex to stack, and if there is a cycle then all elements from the top of stack (until you reach the last vertex) belong to the cycle

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

When you do dfs, you can consider vertices of 3 types; unvisited, visited but in the stack, or visited and finished (we called dfs on all their neighbors and returned already).

If your dfs detects a cycle, then all the cycle vertices are the type that's in the stack (they must have been visited, but they cannot be finished because you will find a cycle before finishing any vertex on it). So, one easy way to find the cycle is to maintain the stack along with a dfs (vector or stack, either global or passed by reference). When you find a visited neighbor, iterate from the back of the stack until you reach that visited node, and put all the vertices you iterated on in some vector, representing the cycle.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks Noam! For future reference: the iteration process in the stack after you find a visited neighbour is a parallel process to the main DFS.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Sorry. My answer is wrong as I got the wrong definition of a cycle.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In an undirected graph, all nodes in the same connected component are in a cycle.

    I'm not sure that's right. Consider an undirected graph that is a chain/linked list. They are all part of the same connected component, but how is there a cycle?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

any one go idea how to do it usign bfs in undirected graph?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Using BFS it is more writing work than a simple DFS but still you can do that. Just run the BFS over the nodes and when you find a backedge (an edge to already visited node) , you have found a cycle .

    For printing the cycle just find the LCA (lowest common ancestor) of the nodes connected by that backedge and travel parent to parent from both the nodes to the LCA. now just connect the parts in order to find the given cycle , still i would say it is a lot easier using DFS. (For making a bit simple , don't use Binary lifting for finding the LCA)

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

you can try this:

Spoiler