I have an undirected graph $G$, with edges $E$ and vertex $V$, how to group the edges into different sets, in which

  1. One edge can only belong in one set
  2. Every edge must be covered in one of the sets
  3. If I can "walk" from one edge to another, these two edges must be contained in a single set.

Take this for an example, I have the following edges $(A,B), (C,B), (D,B),(B,G), (E,F)$, then there are two sets, namely, $(A,B), (C,B), (D,B),(B,G)$ and $(E,F)$.

Edit: My hunch tells me that there is a standard algorithm (with a name) for this, what is it?

  • $\begingroup$ I haven't studied graph theory but 1 and 2 don't make sense. It seems like they're two ways of saying the same thing, "each edge can only belong in one set", i.e. a partition on E. I just point this out because somebody that can help you might be confused too. If it's standard terminology please just excuse me. Condition 3 just defines an equivalence relation assuming that you allow a walk from an edge to itself of zero steps. $\endgroup$ – knucklebumpler Apr 6 '11 at 10:33
  • $\begingroup$ @knucklebumpler, I've edited the question. sorry for the poor wording. $\endgroup$ – Graviton Apr 6 '11 at 10:35
  • $\begingroup$ @Zach, from what I know, connected component works for directed graph, not undirected graph, don't you think so? $\endgroup$ – Graviton Apr 6 '11 at 11:22
  • $\begingroup$ (I posted my comment as an answer now.) Connected components exist in both directed and undirected graphs. Directed graphs, however, distinguish between "weakly" connected components and "strongly" connected components. $\endgroup$ – Zach Langley Apr 6 '11 at 11:25

It sounds like you are just looking for connected components, which can easily be found with a simple breadth- or depth-first search.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.