0

我正在尝试使用 JPanel 为 BFS 遍历设置动画。

控制台输出显示算法正在运行...

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

        }
    }
}

因此,我认为在 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:EF...

在此处输入图像描述

我正在使用paintComponentrepaint()来更改访问时的节点颜色...

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();

}

任何想法?

4

1 回答 1

0

你需要修改你的算法。每次调用 时bfs(),都会从根节点“A”开始搜索。

该算法迭代地将“B”、“C”和“D”标记为“A”的已访问子项,然后……就是这样。'A' 没有未探视的孩子,因此bfs()不再做任何事情;没有while可以探索“B”的孩子的循环

您需要设置某种形式的持久状态,以便 bfs() 方法实际上将逐个遍历所有节点。 迭代深化可能是一个不错的起点,因为可以通过简单的方法使 DFS 迭代堆。

于 2013-06-19T21:45:46.953 回答