BFS 无法正常工作

Question

我正在尝试实施 BFS 以查找在学习某门课程之前所需的所有先决条件。我的 public List<Node> computeAllPrereqs(String courseName) 方法是我的代码出错的地方。有人可以看看我的方法并帮我找到问题吗？我认为结束节点将是 none，因为我图表中的课程都指向 none。该图不是循环的。

这是我传递给构造函数的文本文件，第一列是课程，后面是课程的先决条件：

CS1 None
CS2 CS1
CS3 CS2
CS4 CS1
CS5 CS3 CS4
CS6 CS2 CS4

.

public class Graph {

    private Map<String, Node> graph;

    public Graph(String filename) throws FileNotFoundException {

        // open the file for scanning
        File file = new File(filename);
        Scanner in = new Scanner(file);

        // create the graph
        graph = new HashMap<String, Node>();

        // loop over and parse each line in the input file
        while (in.hasNextLine()) {
            // read and split the line into an array of strings
            // where each string is separated by a space.
            Node n1, n2;
            String line = in.nextLine();
            String[] fields = line.split(" ");
            for(String name: fields){
                if (!graph.containsKey(fields[0]))
                {
                    n1 = new Node(name);
                    graph.put(name, n1);
                }
                else{
                    n2 = new Node(name);
                    graph.get(fields[0]).addNeighbor(n2);
                }
            }
        }
        in.close();
    }    
    public List<Node> computeAllPrereqs(String courseName){
        // assumes input check occurs previously
        Node startNode;
        startNode = graph.get(courseName);


        // prime the dispenser (queue) with the starting node
        List<Node> dispenser = new LinkedList<Node>();
        dispenser.add(startNode);

        // construct the predecessors data structure
        Map<Node, Node> predecessors = new HashMap<Node,Node>();
        // put the starting node in, and just assign itself as predecessor
        predecessors.put(startNode, startNode);

        // loop until either the finish node is found, or the
        // dispenser is empty (no path)
        while (!dispenser.isEmpty()) {
            Node current = dispenser.remove(0);
            if (current == new Node(null)) {
                break;
            }
            // loop over all neighbors of current
            for (Node nbr : current.getNeighbors()) {
                // process unvisited neighbors
                if(!predecessors.containsKey(nbr)) {
                    predecessors.put(nbr, current);
                    dispenser.add(nbr);
                }
            }
        }

        return constructPath(predecessors, startNode, null);
    }
    private List<Node> constructPath(Map<Node,Node> predecessors,
                                     Node startNode, Node finishNode) {

        // use predecessors to work backwards from finish to start,
        // all the while dumping everything into a linked list
        List<Node> path = new LinkedList<Node>();

        if(predecessors.containsKey(finishNode)) {
            Node currNode = finishNode;
            while (currNode != startNode) {
                path.add(0, currNode);
                currNode = predecessors.get(currNode);
            }
            path.add(0, startNode);
        }

        return path;
    }

}

这是我用来制作图中节点和邻居的节点class：

public class Node {

    /*
     *  Name associated with this node.
     */
    private String name;

    /*
     * Neighbors of this node are stored as a list (adjacency list).
     */
    private List<Node> neighbors;


    public Node(String name) {
        this.name = name;
        this.neighbors = new LinkedList<Node>();
    }


    public String getName() {
        return name;
    }

    public void addNeighbor(Node n) {
        if(!neighbors.contains(n)) {
            neighbors.add(n);
        }
    }

    public List<Node> getNeighbors() {
        return new LinkedList<Node>(neighbors);
    }


    @Override
    public String toString() {
        String result;
        result = name + ":  ";

        for(Node nbr : neighbors) {
            result = result + nbr.getName() + ", ";
        }
        // remove last comma and space, or just spaces in the case of no neighbors
        return (result.substring(0, result.length()-2));
    }


    @Override
    public boolean equals(Object other) {
        boolean result = false;
        if (other instanceof Node) {
            Node n = (Node) other;
            result = this.name.equals(n.name);
        }
        return result;
    }

    @Override
    public int hashCode() {
        return this.name.hashCode();
    }
}

这是我的测试 class:

public class Prerequisite {

/**
 * Main method for the driver program.
 *
 * @param args the name of the file containing the course and
 * prerequisite information
 *
 * @throws FileNotFoundException if input file not found
 */
public static void main(String[] args) throws FileNotFoundException {

    // Check for correct number of arguments
    if(args.length != 1) {
        String us = "Usage: java Prerequisite <input file>";
        System.out.println(us);
        return;
    }

    // create a new graph and load the information
    // Graph constructor from lecture notes should
    // be modified to handle input specifications
    // for this lab.
    Graph graph = new Graph(args[0]);

    // print out the graph information
    System.out.println("Courses and Prerequisites");
    System.out.println("=========================");
    System.out.println(graph);


    // ASSUMPTION:  we assume there are no cycles in the graph

    // Part I:
    // compute how many (and which) courses must be taken before it is
    // possible to take any particular course

    System.out.println("How many courses must I take "
            + "before a given course?!?!?");
    for(String name : graph.getAllCourseNames()) {
        List<Node> allPrereqs = graph.computeAllPrereqs(name);
        System.out.print(String.valueOf(allPrereqs.size()));
        System.out.print(" courses must be taken before " + name + ": ");
        for(Node el : allPrereqs) {
            System.out.print(el.getName() + " ");
        }
        System.out.println();
    }


}

当我运行这个测试时我的输出是：

0 courses must be taken before CS1: 
0 courses must be taken before CS3: 
0 courses must be taken before CS2: 
0 courses must be taken before CS5: 
0 courses must be taken before CS4: 
0 courses must be taken before CS6:

应该是：

0 courses must be taken before CS1: 
2 courses must be taken before CS3: CS1 CS2 
1 courses must be taken before CS2: CS1 
4 courses must be taken before CS5: CS1 CS3 CS2 CS4 
1 courses must be taken before CS4: CS1 
3 courses must be taken before CS6: CS1 CS2 CS4

我知道我发布了很多代码，但如果需要帮助修复我的错误，我不想在以后编辑更多代码。

Answer 1

if (current == new Node(null)) {
        break;
    }

您应该使用 continue 而不是 break。即使你遇到了空节点，你也可以在队列中有更多的正常节点，这些节点到空节点的路径更长。

从CS5开始分析图就可以体会

Answer 2

请注意，使用深度优先搜索 (DFS) 可以更有效地确定先决条件，从而实现拓扑排序。

在图构建过程中，当 linking 邻居时，"lookalikes" 被 linked 而不是现有的图节点本身，因此生成的图实际上是未连接的。要解决该问题，link 图形的实际节点相互连接。

            if (!graph.containsKey(fields[0]))
            {
                n1 = new Node(name);
                graph.put(name, n1);
            }
            else{
                if(graph.containsKey(name)) {
                    n2 = graph.get(name);
                }
                else {
                    n2 = new Node(name);
                    graph.put(name, n2);
                }
                graph.get(fields[0]).addNeighbor(n2);
            }

上述代码片段的另一个好处是它将终端 "None" 节点添加到图表中。

无法构建单行路径，因为一门课程可能有多个先决条件。例如，CS6 依赖于 CS2 和 CS4。在 constructPath 方法中，终止条件将在仅遵循其中一条路径后触发。因此，鉴于程序的当前结构，您可以实现的最好结果是输出一组先决条件课程而不是单行路径。

private List<Node> constructPath(Map<Node,Node> predecessors,
                                 Node startNode, Node finishNode) {
/*
    // use predecessors to work backwards from finish to start,
    // all the while dumping everything into a linked list
    List<Node> path = new LinkedList<Node>();

    if(predecessors.containsKey(finishNode)) {
        Node currNode = finishNode;
        while (currNode != startNode) {
            path.add(0, currNode);
            currNode = predecessors.get(currNode);
        }
        path.add(0, startNode);
    }
*/
    Set<Node> prereqs = new HashSet<Node>(predecessors.keySet());
    prereqs.remove(graph.get("None"));
    return new ArrayList<Node>(prereqs);
}

采用这种方法，参数 startNode 和 finishNode 都不是必需的，而且前导映射的创建是多余的。

最后，课程本身不是先决条件，因此将自己指定为前置课程是不正确的。

    // put the starting node in, and just assign itself as predecessor
    // predecessors.put(startNode, startNode);

鉴于这些修改，这就是输出

0 courses must be taken before CS1: 
1 courses must be taken before CS2: CS1 
2 courses must be taken before CS3: CS2 CS1 
1 courses must be taken before CS4: CS1 
4 courses must be taken before CS5: CS4 CS2 CS3 CS1 
3 courses must be taken before CS6: CS4 CS2 CS1

为了改进代码，TreeSet (http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html) can be used instead of a HashSet to output the prerequisites in a uniform order. To use TreeSet however, the Node class will have to be augmented to implement Comparable (How to implement the Java comparable interface?)。

同样，如果输出的先决条件集不令人满意，请考虑使用 DFS 代替生成拓扑排序 (http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htm)。

BFS 无法正常工作

BFS is not working correctly

java

graph

hashmap

breadth-first-search