3
$\begingroup$

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?

  • 0
    (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.2011-04-06

1 Answers 1

3

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