java - 任何人都可以帮助解决这个 Stack/List 问题吗？

Question

我一直在阅读一本关于 Java 的书，并且必须表示有向图、节点之间的距离等。

这是我所拥有的(来自以前的出版物)

import java.io.*;
import java.util.*;

public class BFSAlgorithm {

    private Graph graph;

    /**
     * Constructor.
     */
    public BFSAlgorithm(Graph g) {
        graph = g;
    }

    /**
     * 1 - Create a stack to store all the vertices of our path on.
     * 2 - First push the 'end' vertex on our stack.
     * 3 - Now loop from the highest level back to the first level and
     *     a. loop through each level and
     *     b. check each vertex in that level if it's connected to the
     *        vertex on the top of our stack, if we find a match, push that
     *        match on the stack and break out of the loop.
     * 4 - Now we only need to reverse the collection (stack) before returning 
     *     the path in the "correct" order (from start to finish).
     * 
     * Here's an example ASCII drawing of backtracking from the end vertex "n" 
     * to the starting vertex "g". The arrows, <-, denote the path that was 
     * found.
     * 
     * level:  0      1      2      3       4      5      6    7     8
     *        ---------------------------------------------------------
     *         g <-+  IV     e      I       a   +- III <- o <- VI <- n 
     *             +- V <-+  f   +- II <-+  b   |         p
     *                    +- c <-+       |  d   |
     *                       j           +- h <-+
     *                                      q
     *                                      r
     */
    private List<String> backTrack(List<List<String>> container, String end) {
        Stack<String> path = new Stack<String>();                     // 1
        path.push(end);                                               // 2
        for(int i = container.size()-1; i >= 0; i--) {                // 3
            List<String> level = container.get(i);
            String last = path.peek();
            for(String s : level) {                                   // a
                if(graph.isConnectedTo(last, s)) {                    // b
                    path.push(s);
                    break;
                }
            }
        }
        Collections.reverse(path);                                    // 4
        return path;
    }

    /**
     * 1 - Get the level from the 'container' which was added last.
     * 2 - Create a new level to store (possible) unexplored verices in.
     * 3 - Loop through each of the vertices from the last added level, and
     *     a. get the neighboring vertices connected to each vertex,
     *     b. loop through each connecting vertex and if the connecting vertex
     *        has not yet been visited,
     *     c. only then add it to the newly created level-list and mark it as 
     *        visited in our set.
     * 4 - We don't need to search any further if we stumble upon the 'end' 
     *     vertex. In that case, just "return" from this method.
     * 5 - Only make the recursive call if we have found vertices which have 
     *     not been explored yet.
     */
    private void bfs(List<List<String>> container, 
            String end, Set<String> visited) {

        List<String> lastLevel = container.get(container.size()-1);   // 1
        List<String> newLevel = new ArrayList<String>();              // 2

        for(String vertex : lastLevel) {                              // 3
            List<String> edges = graph.getEdges(vertex);              // a
            for(String edge : edges) {                                // b
                if(!visited.contains(edge)) {                         // c
                    visited.add(edge);
                    newLevel.add(edge);
                }
                if(edge.equals(end)) return;                          // 4
            }
        }  
        if(newLevel.size() > 0) {                                     // 5
            container.add(newLevel);
            bfs(container, end, visited);
        }
    }

    /**
     * 1 - Create an empty 'container' to store all the levels from the 
     *     'start'-vertex in. A level is also a list with one or more vertices.
     * 2 - The first level only holds the 'start' vertex, which is added first,
     *     this is the 'init' list.
     * 3 - The 'start' vertex is also stored in a Set which keeps track of all 
     *     the vertices we have encountered so that we don't traverse vertices
     *     twice (or more).
     * 4 - Once we initialized the steps 1-3, we can call the actual BFS-
     *     algorithm.
     * 5 - Once the BFS-algorithm is done, we call the backTrack(...) method 
     *     to find the shortest path between 'end' and 'start' between the 
     *     explored levels of the graph. 
     */
    public List<String> getShortestPath(String start, String end) {
        List<List<String>> container = new ArrayList<List<String>>(); // 1
        List<String> init = new ArrayList<String>();                  // 2
        init.add(start);
        container.add(init);
        Set<String> visited = new HashSet<String>();                  // 3
        visited.add(start);
        bfs(container, end, visited);                                 // 4
        return backTrack(container, end);                             // 5
    }

    /**
     * Main method:
     *  1 - Create a Graph.
     *  2 - Get a shortest path between two vertices.
     *  3 - Print the shortest path.
     */
    public static void main(String[] args) throws FileNotFoundException {
        Graph graph = new Graph("data.txt");                          // 1
        BFSAlgorithm bfsAlgorithm = new BFSAlgorithm(graph);
        List<String> shortestPath = 
            bfsAlgorithm.getShortestPath("g", "n");                   // 2
        for(int i = 0; i < shortestPath.size(); i++) {
            System.out.print(shortestPath.get(i));                    // 3
            System.out.print(i < shortestPath.size()-1 ? "\n -> " : "\n");
        }
    }
}

但是我得到以下错误:

reverse(java.util.List<?>) in
java.util.Collections cannot be
applied to (Stack<java.lang.String>)

incompatible types found   :
Stack<java.lang.String> required:
java.util.List<java.lang.String>

与此相关(第一个错误第一行，第二个错误第二行):

Collections.reverse(path);                                    // 4
        return path;

有什么想法吗？非常感谢!

Answer 1

根据该错误消息判断，Stack 没有引用 java.util.Stack(它实现了 java.util.List，并且是大概是你想要的。)相反，它指的是默认包中名为 Stack 的类(它不包含在你的示例中。)如果这是有意的，那么请从你的 Stack 添加代码 类的问题。