1
$\begingroup$

The approach described in this question is wrong. It'll find false positives for disconnected components with multiple vertices. See D.W.'s answer for a reliable alternative.

This might be a simple question, but I can't seem to find a clear cut algorithm for this. I'm given a set of vertices from a graph and I need to determine whether they form a connected subtree in this original graph. I also have the neighbors of each of the vertices and an edge list to work with.

My approach would be to loop over the vertices and check if each one has at least one of the other given vertices as a direct neighbor. If one of them hasn't, it must be disconnected from the rest of the vertices, so the set can't form a connected subtree and we can return false early. So like this:

foreach (vertex in input)
{
   connectedToAny = false;

   foreach(other in input)
   {
          if (vertex.neighbors.contains(other))
          {
                 connectedToAny = true;
                 break;                     
          }
   }

   if (!connectedToAny)
   {
          return false;
   }
}

return true;

I'm aware this doesn't preclude the existence of cycles, but I'm happy to ignore this for now.

My main question is if this approach is in fact correct, or whether I'm missing cases where this could lead to false positives or negatives.

I'd also be happy to hear if there's a more efficient approach. I have also considered using a more conventional depth first search from any of the input vertices to see if they're connected, but I think I'd have to compute $neighbors \cap input$ at each recursion to specialize from simply connected (possibly via other vertices) to directly connected subtree, right?

$\endgroup$
1
$\begingroup$

You can do this in linear time. You can tell if they're connected by keeping only those vertices and edges between them, and testing if the resulting graph is connected using standard algorithms (e.g., DFS). You can tell if they're a tree by testing if the resulting graph has any cycles (e.g., using DFS).

$\endgroup$
  • $\begingroup$ Right, I see what you mean, thanks for pointing this out. $\endgroup$ – Fasermaler Jan 10 '16 at 20:03

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.