алгоритм, используемый для возврата определенного диапазона узлов в ориентированном графе

Question

У меня есть класс Graph с двумя типами списков, а именно узлы и ребра

У меня есть функция

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

когда я получу эти параметры, мне понадобится алгоритм, который будет проходить через график и возвращать список узлов только настолько глубоко (уровень), как диапазон. Алгоритм должен быть способен вместить большое количество узлов и большие диапазоны.

Поверх этого, я должен использовать аналогичную функцию

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

Я хочу, чтобы можно было выполнять поиск по нему, по указанному количеству узлов наружу (диапазону).

альтернативный текст http://www.freeimagehosting.net/uploads/b110ccba58.png

Итак, в первой функции, если я пропущу узлы и потребую диапазон, скажем, 2, я ожидаю, что результаты вернут узлы, показанные в синем поле.

Другая функция, если я пропускаю узлы, как на графике с диапазоном 1, и начинается с узла 5, я хочу, чтобы он возвращал список узлов, которые удовлетворяют этому критерию (помещен в оранжевое поле)

Answer 1

То, что вам нужно, кажется просто ограниченным по глубине поиском по ширине или поиском по глубине с возможностью игнорирования направленности края.

---

Вот рекурсивное определение, которое может вам помочь:

• Я единственный из диапазона 1 от себя.
• Я знаю, кто мои ближайшие соседи.
• Если N > 1, то те из диапазона N от меня
  • Союз всего, что находится на расстоянии N-1 от моих соседей

Answer 2

// get all the nodes that are within Range distance of the root node of graph
Set<int> GetNodesInRange(Graph graph, int Range)
{
    Set<int> out = new Set<int>();
    GetNodesInRange(graph.root, int Range, out);
    return out;
}

// get all the nodes that are within Range successor distance of node
// accepted nodes are placed in out
void GetNodesInRange(Node node, int Range, Set<int> out)
{
    boolean alreadyVisited = out.add(node.value);
    if (alreadyVisited) return;
    if (Range == 0) return;
    // for each successor node
    {
        GetNodesInRange(successor, Range-1, out);
    }
}


// get all the nodes that are within Range distance of selected node in graph
Set<int> GetNodesInRange(Graph graph, int Range, int selected)
{
    Set<int> out = new Set<int>();
    GetNodesInRange(graph, Range, selected, out);
    return out;
}

// get all the nodes that are successors of node and within Range distance
//     of selected node
// accepted nodes are placed in out
// returns distance to selected node
int GetNodesInRange(Node node, int Range, int selected, Set<int> out)
{
    if (node.value == selected)
    {
        GetNodesInRange(node, Range-1, out);
        return 1;
    }
    else
    {
        int shortestDistance = Range + 1;
        // for each successor node
        {
            int distance = GetNodesInRange(successor, Range, selected, out);
            if (distance < shortestDistance) shortestDistance = distance;
        }
        if (shortestDistance <= Range)
        {
            out.add(node.value);
        }
        return shortestDistance + 1;
    }
}

Я несколько изменил ваши требования, чтобы получить Set вместо List.

Метод GetNodesInRange(Graph, int, int) не будет обрабатывать графики, содержащие циклы. Этого можно избежать, поддерживая набор узлов, которые уже были посещены. В методе GetNodesInRange(Graph, int) используется тот факт, что набор out представляет собой набор посещенных узлов для преодоления циклов.

Примечание : не проверено каким-либо образом.

Answer 3

Это должна быть рекурсивная функция, которая находит соседей выбранного, затем находит соседей каждого соседа, пока диапазон не станет равен 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;
}

Вам также следует проверить циклы, если они возможны. Этот код предназначен для древовидной структуры.