алгоритм для использования для возврата определенного диапазона узлов в ориентированном графе
У меня есть класс График с двумя типами списков а именно, узлы и края
У меня есть функция
List GetNodesInRange(Graph graph, int Range)
когда я получаю эти параметры, мне нужен алгоритм, который пройдет график и возвратит список узлов только настолько же глубоко (уровень) как диапазон. Алгоритм должен смочь разместить большое количество узлов и больших спектров.
На этом, должен я использовать подобную функцию
List GetNodesInRange(Graph graph, int Range, int selected)
Я хочу смочь искать за пределы его к количеству узлов за пределы указанный (диапазон).
сопроводительный текст http://www.freeimagehosting.net/uploads/b110ccba58.png
Таким образом в первой функции, должен я передавать узлы и требовать, чтобы диапазон сказал 2, я ожидаю, что результаты возвратят узлы, показанные в синем поле.
Другая функция, если я передаю узлы как в графике с диапазоном 1 и он запускается в узле 5, я хочу, чтобы он возвратил список узлов, которые удовлетворяют это критерии (помещенный в оранжевое поле)
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;
}
Вам также следует проверить наличие циклов, если они возможны. Этот код предназначен для древовидной структуры.
// 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 представляет собой набор посещенных узлов для преодоления циклов.
Примечание : не тестировался каким-либо образом.
То, что вам нужно, кажется просто ограниченным по глубине поиском в ширину или поиском в глубину с возможностью игнорирования направленности краев.
Вот рекурсивное определение, которое может вам помочь:
- Я единственный из диапазона 1 от меня.
- Я знаю, кто мои ближайшие соседи.
- Если
N> 1, то те, которые находятся в диапазонеNот меня, являются- Объединение всего, что входит в диапазон
N-1от моих соседей
- Объединение всего, что входит в диапазон