-0.69's blog

Breaking Cyclic Graph into Trees?
By -0.69, history, 8 months ago, In English

Image Example?Hey I was wondering If I have a graph that contains cycles. How can I break it into all possible Trees?? (Assuming the no. of vertices are very less?)

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

the simplest way is probably to just try all $$$n!$$$ paths, since in the worst case, there will be about $$$n!$$$ subtrees anyways.

However, if you want it to be fast, this is what i found: http://www.hariharan-ramesh.com/papers/spantree1.pdf and https://cs.ou.edu/~thulasi/Algorithm/Complexity%20of%20Computation%20of%20a%20Spanning%20Tree%20Enumeration%20Algorithm.pdf

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

    Thankyou I tried the n! factorial way it worked

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

to convert it to the tree you need to cancel cycles: to cancel a cycle you should at least delete one edge so you should make it independently for every cycle and then combine it, I think it needs very small constraints or a small number of cycles I see an idea like this Here

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Maintain a visited array and add the edges as they're given in the input. If both nodes in a given edge are visited, discard the edge.

→ Reply