nqs_1's blog

By nqs_1, history, 4 years ago, In English

how to mark all the nodes that are in a cycle in a graph?

  • Vote: I like it
  • +7
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You can use degree of nodes like doing BFS. The detail is in this post

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I assume that you are dealing with directed graphs. How about finding strongly connected components? Clearly, any cycle must be in some SCC and the nodes in a SCC (with more than 1 node) are in a cycle by definition of a strongly connected component. So, you can just dump those SCCs with one node only. And mark the nodes in the rest of the SCCS.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thx ,your post was really helpful.

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Find all bridges in the graph, a vertex is in a cycle iff atleast one of the adjacent edge is not a bridge.