用于在有向图中返回特定范围的节点的算法

Question

我有一个类Graph,有两个列表类型,即节点和边

我有一个功能

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

当我得到这些参数时,我需要一个算法,它将通过图形并返回节点列表,只作为范围的深度(级别).该算法应该能够容纳大量节点和大范围.

在此之上,我应该使用类似的功能

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

我希望能够从它向外搜索到指定的向外(范围)节点数.

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

所以在第一个函数中,如果我传递节点并且需要一个2的范围,我希望结果返回蓝色框中显示的节点.

另一个函数,如果我在图中传递范围为1的节点并从节点5开始,我希望它返回满足此条件的节点列表(放在橙色框中)

Answer 1

它应该是一个递归函数，查找所选邻居的邻居，然后查找每个邻居的邻居，直到范围为 0。DFS 搜索如下所示：

List<int> GetNodesInRange(Graph graph, int Range, int selected){
  var result = new List<int>();
  result.Add( selected );
  if (Range > 0){
    foreach ( int neighbour in GetNeighbours( graph, selected ) ){
      result.AddRange( GetNodesInRange(graph, Range-1, neighbour) );
    }
  }
  return result;
}

如果可能的话，您还应该检查循环。此代码用于树结构。