Given a Spanning Tree and an Edge Not on the Spanning Tree, How to Form a Cycle Base?

Question

I have a graph with Edge E and Vertex V, I can find the spanning tree using Kruskal algorithm (or any other traverse-backtrack-traverse-again kind of algorithms), 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?

Answer 1

A simple algorithm we use for finding cycles in graphs:

Create a depth-first spanning tree where each node has a parent. In traversing the tree create a record of used nodes. When an edge points to a previously used node, store it as a cyclic edge. When the spanning tree is complete, the count of the cyclic edges gives the count of cycles. For each cyclic edge recurse through the ancestors of the two nodes until a common ancestor is found. That will give exactly the cycles.

It may be useful to have an index (hashtable) of all the ancestors of a cyclic edge node so that is quick to find the common ancestor.

I doubt this is the best algorithm but it is fairly quick.

EDIT in repsonse to comment Each node in the spanning tree has a parent. When a node in a cyclic edge is reached it calculates its list of ancestors (List<Node>This list could be indexed for speed (i.e. contains() is < O(n)). When a cyclic edge with two nodes (n1, n2) is found then iterate through the ancestors of n1, n1.ancestorList (rapidly since the list has already been created) and test whether the ancestor is in n2.ancestorList. If it (commonAncestor) is, then exactly those ancestors traversed correspond to cycles. Then iterate through n2 until you reach commonAncestor (rapid). The time should depend on the number of cyclic edges, combined with the lookup in lists (probably O(logN) but cheap). There is no need to re-explore the graph and there is no backtracking.

Answer 2

After constructing spanning tree, iterate on every edge(A,B) which is not in tree and find Lowest Common Ancestor(LCA) for nodes of this edge, your cycle would be path from A -> LCA -> B -> A

you can use this link: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor for efficient Lowest Common Ancestor algorithm implementation.