Анимация BFS Traversal с использованием JPanel

Question

Я пытаюсь анимировать обход BFS с помощью JPanel.

Консольный вывод показывает алгоритм работает ...

BFS: 
A B C D E F 

Для данного графа:

BFS фрагмент кода:

public void bfs() { 

    Queue q = new LinkedList(); 
    q.add(rootNode); 
    rootNode.visited(true); 
    rootNode.setColor(Color.cyan); 
    printNode(rootNode); 
    while (!q.isEmpty()) { 

     Nodes n = (Nodes)q.remove(); 
     Nodes child = null; 
     //put all unvisited children in the queue 
     while ((child = getUnvisitedChildNode(n)) != null) 
     { 
      // 
      child.visited(true); 
      //visited color = cyan 
      child.setColor(Color.cyan); 
      printNode(child); 
      q.add(child); 

     } 
    } 
} 

Итак, я выдумали лучший способ для анимата e это на JPanel, добавив таймер, который вызывает bfs() каждые 1 секунду ... И измените петли while на if операторов ... поэтому, когда он называется, он будет перебирать один раз на узел и отмечать его как посещенный.

public void bfs() { 

    Queue q = new LinkedList(); 
    q.add(rootNode); 
    rootNode.visited(true); 
    rootNode.setColor(Color.cyan); 
    printNode(rootNode); 
    if (!q.isEmpty()) { 

     Nodes n = (Nodes)q.remove(); 
     Nodes child = null; 
     //put all unvisited children in the queue 
     if ((child = getUnvisitedChildNode(n)) != null) 
     { 
      // 
      child.visited(true); 
      //visited color = cyan 
      child.setColor(Color.cyan); 
      printNode(child); 
      q.add(child); 

     } 
    } 
    if (q.isEmpty()) { 
     cancelTimer = true; 
    } 
} 

Это становится через узлы A, B, C, D, но теперь не будет посещать ребенок B: E и F ...

Я использую paintComponent с repaint() для изменения цвета узлов при посещении ...

public void paintComponent(Graphics g) { 
    g.setColor(Color.BLACK); 
    g.fillRect(0, 0, width, height); 

    g.setColor(rootNode.getColor()); 
    g.fillRect(rootNode.getX(), rootNode.getY(), rootNode.getWidth(), rootNode.getHeight()); 

    g.setColor(Color.WHITE); 
    g.drawString(rootNode.getValue(), rootNode.getX()+9, rootNode.getY()+16); 
    paintComponent(g, rootNode);  
} 

public void paintComponent(Graphics g, Nodes parentNode) { 
    //keep generating new nodePrintList to load with new Children 
    ArrayList<Nodes> nodePrintList = new ArrayList<Nodes>();  

    //base case: end of nodeList 
    if (nodeList.indexOf(parentNode)==nodeList.size()-1) { 
     System.out.println("\nend"); 
    } 
    else { 
    //traverse nodeList recursively 
     nodePrintList = getChildren(parentNode);  
     //loop through and print all children of node n 
     //System.out.println(); 
     int x = parentNode.getX()-50; 

     for (Nodes child : nodePrintList) {    
      g.setColor(child.getColor()); 
      child.setX(x); 
      child.setY(parentNode.getY()+50); 
      g.fillRect(child.getX(), child.getY(), child.getWidth(), child.getHeight());   
      g.setColor(Color.WHITE); 
      g.drawString(child.getValue(), child.getX()+9, child.getY()+16); 
      x+=50; 
      //System.out.print("PARENT: " + parentNode.getValue() + " | x,y: " + parentNode.getX() + ", " + parentNode.getY() + "...\n CHILD: " + child.getValue() + " | x,y: " + child.getX() + ", " + child.getY()); 
      paintComponent(g, child); 
      g.drawLine(parentNode.getX()+10, parentNode.getY()+23, child.getX()+10, child.getY()); 
     }   
    }repaint(); 

} 

Любая идея?

Answer 1

Вам необходимо пересмотреть свой алгоритм. Каждый раз, когда вы вызываете bfs(), вы начинаете поиск в корневом узле «A».

Алгоритм итеративно отмечает «B», «C», а затем «D», как посещенные дети «A», а затем ... вот и все. «А» не имеет детей, которых нет, поэтому bfs() больше ничего не делает; Существует не while петля, из которой могут быть изучены дети 'B'.

Вам необходимо настроить некоторую форму постоянного состояния, чтобы метод bfs() фактически прошел через все узлы, 1 на 1 Iterative Deepening может быть хорошим местом для начала, поскольку DFS можно сделать итерационным с помощью простого стека.