algorytm używany do zwrócenia konkretnej szereg węzłów skierowanego wykresie

Question

mam klasy wykres dwa rodzaje wymienia czyli węzłów i krawędzi

mam funkcji

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

kiedy się te parametry Potrzebuję algorytmu, który przejdzie przez wykres i zwróci listę węzłów tylko tak głęboko (poziom), jak zakres. Algorytm powinien być w stanie pomieścić dużą liczbę węzłów i dużych zakresów.

szczycie tego należy użyć podobnej funkcji

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

Chcę mieć możliwość wyszukiwania na zewnątrz od niego, do liczby węzłów zewnątrz (zakres) określony.

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

Więc w pierwszej funkcji, należy przekazać węzły i wymaga szeregu powiedzieć 2, oczekuję wyników powrót węzły pokazane na niebieskim polu.

Druga funkcja, jeśli przekażę węzły jak na wykresie z zakresem 1 i rozpocznie się w węźle 5, chcę, aby zwróciła listę węzłów spełniających te kryteria (umieszczonych w pomarańczowym polu)

Answer 1

To powinno być funkcji rekurencyjnej, że znajdzie sąsiadów wybranego, a następnie znajdują sąsiadów każdego sąsiada, aż zakres wynosi 0. Wyszukiwanie DFS coś takiego:

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

Powinieneś również sprawdzić cykle, jeśli są one możliwe. Ten kod dotyczy struktury drzewa.

Answer 2

To, czego potrzebujesz, wydaje się być po prostu ograniczoną głębokością breadth-first search lub depth-first search, z opcją ignorowania kierunkowości krawędzi.

---

Oto definicja rekurencyjna, które mogą pomóc:

• jestem jedynym z zakresu 1 od siebie.
• Wiem, kim są moi najbliżsi sąsiedzi.
• Jeśli N > 1, potem te z zakresu N od siebie są
  • Unii wszystkich, że jest zakresem N-1 z moich sąsiadów

Answer 3

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

zmodyfikowałem nieco swoje wymagania, aby powrócić do Set zamiast List.

Metoda GetNodesInRange(Graph, int, int) nie obsługuje wykresów zawierających cykle. Można to pokonać, utrzymując kolekcję węzłów, które już zostały odwiedzone. Metoda GetNodesInRange(Graph, int) korzysta z tego, że zestaw out jest zbiorem odwiedzanych węzłów, aby pokonać cykle.

Uwaga: To ma nie zostało przetestowane w jakikolwiek sposób.