Given a graph $G$, how to find all disjoint edges?
By Sophia Bowman
I have an undirected graph $G$, with edges $E$ and vertex $V$, how to group the edges into different sets, in which
- One edge can only belong in one set
- Every edge must be covered in one of the sets
- 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?
$\endgroup$ 41 Answer
$\begingroup$It sounds like you are just looking for connected components, which can easily be found with a simple breadth- or depth-first search.
$\endgroup$
