java - 使用 BFS 遍历 java 跟踪倒数第二项

Question

我可以通过将 q.poll 保存在 int 中来跟踪最后一项，但是如何使用此遍历跟踪倒数第二项？

    public Integer breadthFirstTraversal(Integer v) {
            Queue<Integer> q = new LinkedList<Integer>();
            VertexIDList adjList;

            q.add(v);
            getVertex(v).setMarked();

            while (!q.isEmpty()) {
                v = q.poll();
                adjList = getVertex(v).getAdjs();


                Iterator<Integer> vIt = adjList.iterator();
                while (vIt.hasNext()) {
                    Integer u = vIt.next();

                    if (!getVertex(u).isMarked()) {

                        q.add(u);
                        getVertex(u).setMarked();

                    }

                }

            }
// return second last item here

        }

标签： javagraphqueuebreadth-first-search

Answer 1

修改方法签名并添加一个列表来存储路径。（size()-2：last but 1）

public Integer breadthFirstTraversal(Integer v, List emptyList) {
    //with intermediary vars
    int last = 0;
    int last1 = 0;
    Queue<Integer> q = new LinkedList<Integer>();
    VertexIDList adjList;

    q.add(v);

    getVertex(v).setMarked();


    while (!q.isEmpty()) {
        v = q.poll();

        //store
        emptyList.add(getVertex(v));
        last1 = last;
        last = getVertex(v);
        //System.out.println(getVertex(v));

        adjList = getVertex(v).getAdjs();

        Iterator<Integer> vIt = adjList.iterator();
        while (vIt.hasNext()) {
            Integer u = vIt.next();
            if (!getVertex(u).isMarked()) {

                q.add(u);
                getVertex(u).setMarked();  
            }
        }
    }
 // return second last item here
 return last1;
}