algorithm to use to return a specific range of nodes in a directed graph

Question

I have a class Graph with two lists types namely nodes and edges

I have a function

List<int> GetNodesInRange(Graph graph, int Range)

when I get these parameters I need an algorithm that will go through the graph and return the list of nodes only as deep (the level) as the range. The algorithm should be able to accommodate large number of nodes and large ranges.

Atop this, should I use a similar function

List<int> GetNodesInRange(Graph graph, int Range, int selected)

I want to be able to search outwards from it, to the number of nodes outwards (range) specified.

alt text http://www.freeimagehosting.net/uploads/b110ccba58.png

So in the first function, should I pass the nodes and require a range of say 2, I expect the results to return the nodes shown in the blue box.

The other function, if I pass the nodes as in the graph with a range of 1 and it starts at node 5, I want it to return the list of nodes that satisfy this criteria (placed in the orange box)

Answer 1

What you need seems to be simply a depth-limited breadth-first search or depth-first search, with an option of ignoring edge directionality.

---

Here's a recursive definition that may help you:

• I'm the only one of range 1 from myself.
• I know who my immediate neighbors are.
• If N > 1, then those of range N from myself are
  • The union of all that is of range N-1 from my neighbors