Subgraph of a graph given a start vertex

I want to get a subgraph of a graph given the vertex to start at. All vertices connected to the starting vertex are considered part of the subgraph that should be returned.

I've already solved this requirement but am curious if there is a more efficient solution. The solution I came up with was to do a DFS o开发者_开发知识库f the graph and record every vertex that was encountered in a set, S. Then, I simply took all of the edges from the original graph that were connected to a vertex in S and I built a subgraph from it. The edges in the original graph are stored in a C# Dictionary which I believe is basically a hash.

DFS and BFS do not work because if you have two vertices that both have the same child, BFS or DFS will not traverse one of those edges. Hence the subgraph in that case would contain all of the correct vertices, but be missed some edge pairs.

Is there a better solution than the one I've come up with?

I think a BFS traversal is the most efficient algorithm for this.

If you do a BFS and enqueue all neighbors for each node (i.e. traverse all the edges attached to the current node) and only abort traversal when the current node has already been visited, you avoid the problem you described with "same child" / "missed edges".

a "fast" algorithm that enumerates all induced subgraphs of given size can be found here:

http://theinf1.informatik.uni-jena.de/~wernicke/motifs-wabi2005.pdf

does this help?