深度优先搜索(DFS)算法Vertex u声明错误及无输出问题求助

你的代码存在3处核心错误，按影响优先级排序如下：

• while循环末尾多余分号导致死循环
  你写的while(S.size()>0); {中的分号会让while循环变为空循环，只要栈内元素不为空就会一直卡死，这是运行无输出的核心原因，直接删除该分号即可。
• 条件判断、循环未加花括号导致逻辑错乱
  Java中if、for等语句不加花括号时，仅会执行紧随其后的第一行代码。你当前的代码中，未被访问的节点才标记访问的逻辑，实际变成了无论节点是否访问过都会加入已访问列表、遍历邻接节点、强制更新前驱，完全不符合DFS逻辑，所有多语句执行的代码块都需要补充花括号。
• 构造DFS树时未做空指针判断
  DFS的起始节点没有前驱节点，此时你声明的u为null，直接调用addDirectedEdge方法传入null会触发空指针异常，仅当u不为空时才需要添加边。

修正后的完整DFS代码如下：

public GraphAdjacencyList depthFirstSearch(Vertex start) {
    Stack<Vertex> S = new Stack<Vertex>();
    ArrayList<Vertex> visited = new ArrayList<Vertex>();
    HashMap<Vertex,Vertex> predecessor = new HashMap<Vertex,Vertex>();
    // 初始化所有节点为未访问状态
    for(int i = 0;i<listOfVertices.size();i++) {
        listOfVertices.get(i).setVisited(false);
    }
    S.push(start);
    // 删除原代码中while后的多余分号
    while(S.size()>0) {
        Vertex u = S.pop();
        if(!u.getVisited()) {
            u.setVisited(true);
            visited.add(u);
            for(Vertex w: getAdjacentVertices(u)) {
                if(!w.getVisited()) {
                    S.push(w);
                    predecessor.put(w,u);
                }
            }
        }
    }
    GraphAdjacencyList T = new GraphAdjacencyList(listOfVertices);
    for(Vertex v:visited) {
        Vertex u = null;
        if(predecessor.containsKey(v)) {
            u = predecessor.get(v);
            // 仅前驱不为空时添加边，避免空指针异常
            T.addDirectedEdge(u,v,1);
        }
    }
    return T;
}

内容的提问来源于stack exchange，提问作者Mr. Zalgo