nqs_1's blog

can anyone help me.
By nqs_1, history, 5 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

Comments Comments (5)
| Write comment?
»
5 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

→ Reply
»
5 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.

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

    Thx ,your post was really helpful.

    → Reply
»
5 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.

→ Reply