I have a graph with Edge `E` and Vertex `V`, I can find the spanning tree using [Kruskal algorithm](http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/Kruskal.shtml), now I want to find all the cycle bases that are created by utilitizing that spanning tree and the edges that are not on the tree, any algorithm that allows me to do that, besides brute force search?


I can, of course, starts from one vertex of the non-spanning tree edge, gets all the edges, explore all of them, retracts if I find dead end, until I come back to the other vertex of the edge. But this is a bit, err... brutal. Any other ideas?



Given a Spanning Tree and an Edge Not on the Spanning Tree, How to Form a Cycle Base?
I think you're likely to get better answers if you post this question on Stack Overflow rather than here.


But anyways, if your graph doesn't have weights on edges, you don't need Kruskal's algorithm to find a spanning tree; you can just use DFS. As you compute the tree, store for each vertex its parent and the distance to the root. Then when you encounter a non-tree edge, you can find the nearest common ancestor of its two endpoints efficiently.


