0
$\begingroup$

I have a graph with Edge E and Vertex V, I can find the spanning tree using Kruskal algorithm, 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?

Improve this question
$\endgroup$
2
  • $\begingroup$ You don't need Kruskal, Ngu! You can find a spanning tree trivially -- it doesn't have to be minimum. Newcomers, see mathoverflow.net/questions/1443/… for Ngu's initial question. $\endgroup$
    – TonyK
    Commented Oct 22, 2009 at 18:15
  • $\begingroup$ Sure, I can find spanning tree-- with or without Kruskal. But my question is how to form the cycle base without resorting to something what I call 'brute force'. $\endgroup$
    – Graviton
    Commented Oct 23, 2009 at 1:34

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Even with weights, you can use DFS to find a spanning tree. It might not have any nice properties, though. $\endgroup$
    – Michael Lugo
    Commented Oct 22, 2009 at 18:03
  • $\begingroup$ >if your graph doesn't have weights on edges I agree, but But my question is how to form the cycle base without resorting to something what I call 'brute force'. $\endgroup$
    – Graviton
    Commented Oct 23, 2009 at 1:34
1
$\begingroup$

Although this thread is long-dead, there is a very simple way to do this with linear algebra, so I will post an answer.

You are interested in a basis of the cycle space of $G$. Orient $G$ in any way. Let $\partial(G)$ be the edge-vertex incidence matrix of $G$. A basis of the cycle space is given by a basis for $\ker \partial(G)$. To get the answer to your question note that if you take any spanning tree $T$ and you consider the edges of $E-T$, there will be a unique element of the cycle space that is $1$ on a given edge of $E-T$ and $0$ on the others. Finding such an element for each edge of $E-T$ will yield a new basis for $\ker \partial(G)$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .