Cheap and Secure Web Hosting Provider : See Now

[Solved]: Check if given vertices form a connected subtree in a graph

, , No Comments
Problem Detail: 

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?

Asked By : Fasermaler

Answered By : D.W.

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51575

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback