Génération de la forêt de graphes BFS

Question

Je souhaite générer une forêt BFS d'un graphe DACC (Direct Acyclic Graph). Cela signifie que ma classe Tree doit être un arbre général et non un arbre binaire (en d'autres termes, je ne peux pas connaître le nombre d'enfants qu'un noeud aura à l'avance quand je génère une forêt). La plupart du code est écrit et montré ci-dessous, mais il me manque une ligne qui, pour la vie de moi, m'échappe! Ma classe Tree stocke un paramètre de valeur, une référence parente et une liste d'enfants. Mon problème est de référencer le nœud de l'arbre suivant. Une fois que j'ai ajouté tous les voisins non visités en tant qu'enfants du nœud actuel, comment puis-je accéder au nœud suivant?

EDIT:

Il ressemblerait à quelque chose comme ça?

public void bfs(Tree parent) 
{ 
    Iterator<V> ni = neighbors((V) parent.value()); 
    if(ni.hasNext()) 
    { 
      while(ni.hasNext()) 
      { 
      V next = ni.next(); 
      GraphMatrixVertex<V> vert = dict.get(next); 
      if(!vert.isVisited()) 
       parent.addChild(new Tree(next)); 
     } 
    } 
} 

Où se passe l'appel récursif?

Answer 1

Si je comprends bien votre question, vous pouvez utiliser la récursivité pour cela. Fondamentalement, vous avez une fonction qui crée une couche de nœuds, puis elle s'appelle à nouveau pour chaque enfant que vous voulez créer/visiter.

Edit:

Ok, je modifié votre code un peu. Tout d'abord j'ai enlevé le if (hasNext) comme étant redondant avec la boucle while à l'intérieur de celui-ci. Pour chaque nœud enfant de votre liste de voisins, vous créez un nouveau nœud d'arbre puis exécutez sa méthode bfs(), en passant l'objet Tree actuel. La fonction retourne une liste, qui devrait être le meilleur chemin dans l'arbre. Je ne suis pas sûr de la façon dont vous obtenez les nœuds voisins, il semble étrange. Je n'ai pas testé le code, donc il y a probablement des fautes de frappe et des trucs dedans, mais j'espère que cela devrait vous donner une idée de la façon dont vous pouvez faire la recherche. Oh, et quand vous frappez un nœud de feuille (votre cible?), Il devra simplement définir son poids et retourner une nouvelle liste avec seulement elle-même.

int weight; // this should be you node traversal cost 

public LinkedList<Tree> bfs(Tree parent){ 

    Iterator<V> ni = neighbors((V) parent.value()); 

    LinkedList bestPath = null;  
    int bestScore = 0xFFFFFFFF; 

    while(ni.hasNext()){ 
     V next = ni.next(); 
     GraphMatrixVertex<V> vert = dict.get(next); 
     if(!vert.isVisited()){ 
      Tree newNode = new Tree(next); 
      parent.addChild(newNode); 
      LinkedList path = newNode.bfs(this); 
       if(newNode.weight < bestScore){ 
        bestScore = weight; 
        bestPath = path; 
       } 
     } 
    } 
    weight = bestScore + this.weight; 
    bestPath.addFirst(this); 
    return path; 
} 

Edit 2:

public void bfs(Tree parent){ 

    Iterator<V> ni = neighbors((V) parent.value()); 

    while(ni.hasNext()){ 
     V next = ni.next(); 
     GraphMatrixVertex<V> vert = dict.get(next); 
     if(!vert.isVisited()){ 
      Tree newNode = new Tree(next); 
      parent.addChild(newNode); 
      newNode.bfs(this); 
     } 
    } 
}