要使用的算法返回节点的特定范围中一个有向图 [英] algorithm to use to return a specific range of nodes in a directed graph

问题描述

我有一类图形与两个列表类型，即节点和边

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

我有一个函数

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.

所以在第一个功能，我应该通过节点，需要一系列的说2，我所期望的结果返回在蓝色框中显示的节点。

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.

另一个函数，如果我通过节点作为图形与一系列1和它开始于节点5，我希望它返回满足该标准（置于橙色框）的节点列表

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)

推荐答案

这应该是一个递归函数，即找到的选择邻居，然后找出每个邻居的邻居，直到范围为0 DFS搜索类似的东西：

It should be a recursive function, that finds neighbours of the selected, then finds neighbours of each neighbour until range is 0. DFS search something like that:

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;
}

您也应该检查周期，如果他们是可能的。这code是树形结构。

You should also check for cycles, if they are possible. This code is for tree structure.

这篇关于要使用的算法返回节点的特定范围中一个有向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！