如何递归地实现图的通用深度优先遍历？

Question

正如问题的标题所说，我正在尝试对图形进行深入的首次遍历搜索。

为了解决此练习，我应该扩展Graph<T>类并实现Traversal接口。

我正在测试方法的图形如下：

   0 → 1 ↔ 2 → 4
   ↓       ↓
   3       5

或更清楚地说：

0 {1,3}，1 {2}，2 {1,4,5}，3 {empty}，4 {5} 5 {4}

我期望DFT为0，1，2，4，5，4，2，1，1，0，3，0但是我却得到0，1，2，4，3，4

public class DepthFirstTraversal<T> extends Graph<T> implements Traversal <T> {

private AdjacencyGraph<T> graph;

private HashMap<T, Boolean> visited = new HashMap<>();

private List<T> traversalList = new ArrayList<>();

@Override
public List<T> traverse() throws GraphError {

    if (getNoOfNodes() == 0){
        throw new GraphError();
    }

    Set<T> nodes = getNodes();
    Iterator<T> nodeIterator = nodes.iterator();

    for (T t : nodes){
        System.out.println(t + " " + getNeighbours(t));
        visited.put(t, false);
    }

    while (nodeIterator.hasNext()) {
        T node = nodeIterator.next();
        System.out.println("The current node is: " + node + "\n" + "Has next ? " + nodeIterator.hasNext() + "\n" + "Nxt is " + nodeIterator.next());

        if(nodeIterator.hasNext()){
            visit(node, traversalList);
        }
    }
    return traversalList;
}


public List<T> visit(T node, List<T> list) throws GraphError {

    System.out.println("Initial node " + node);
    System.out.println("visit" + traversalList.toString());
    list.add(node);

    System.out.println(list.toString());
    visited.replace(node, true);

    Set<T> neighbours = getNeighbours(node);
    Iterator<T> nextNode = neighbours.iterator();

    System.out.println(nextNode.hasNext() + " next node");
    while (nextNode.hasNext()){
        if(visited(nextNode.next())) {
            visit(nextNode.next(),traversalList);
            System.out.println(traversalList.toString() + " in the while loop");
        }
    }
    return list;
}

public boolean visited(T node) {
    if(visited.get(node)){
        return true;
    }
    else
        return false;

}

图形类包括：（我无法修改的类）

public class Graph<T> implements Graph<T>{

    private Hashtable<T,Set<T>> adjacencyList = new Hashtable<T,Set<T>>();

    private int noOfEdges = 0;


    public boolean contains(T node) {
        return getNodes().contains(node);
    }

    public boolean contains(T start,T end) {

        return contains(start) && contains(end) && adjacencyList.get(start).contains(end);
    }


    public void add(T node) throws GraphError {
        if (contains(node)) {
            throw new GraphError("Cannot add " + node + " to the graph.  This node is already in the graph.");
        } else {

            noOfNodes++;
        }
    }

    public void remove(T node) throws GraphError {
        if (!contains(node)) {
            throw new GraphError("Cannot remove " + node + " from the graph.  No such node.");
        } else {
            noOfEdges -= getNeighbours(node).size();
            adjacencyList.remove(node);

            noOfNodes--;

            for (T start: adjacencyList.keySet()) {
                if (contains(start,node)) {
                    // reduce number of edges
                    noOfEdges--;
                    // remove edge
                    remove(start,node);
                }
            }
        }
    }


    public void add(T start, T end) throws GraphError {
        if (contains(start,end)) {
            throw new GraphError("Cannot add " + start + "==>" + end + " to the graph.  This edge is already in the graph.");
        } else if (!contains(start) || !contains(end)) {
            throw new GraphError("Cannot add " + start + "==>" + end + " to the graph.  One or both of the nodes on this edge is not in the graph.");
        } else {
            // add the edge by adding "end" to "start"'s entry in the adjacency list
            adjacencyList.get(start).add(end);
            // increase number of edges
            noOfEdges++;
        }
    }

    public void remove(T start, T end) throws GraphError {
        if (!contains(start,end)) {
            throw new GraphError("Cannot remove " + start + "==>" + end + " from the graph.  There is no such edge in the graph.");
        } else {
            // delete "end" from "start"'s entry in the adjacency list
            adjacencyList.get(start).remove(end);
            // decrease the number of edges
            noOfEdges--;
        }
    }

    public Set<T> getNeighbours(T node) throws GraphError {
list.
        Set<T> copy = new HashSet<T>();
        for (T member: adjacencyList.get(node)) {
            copy.add(member);
        }
        return copy;
    }


    public int getNoOfNodes() {
        return noOfNodes;
    }


    public Set<T> getNodes() {
list
        HashSet<T> copy = new HashSet<T>();
        for (T member: adjacencyList.keySet()) {
            copy.add(member);
        }
        return copy;
    }

    public int getNoOfEdges() {
        return noOfEdges;
    }
}

Answer 1

这里似乎有一个错误：

    if(visited(nextNode.next())) {
        visit(nextNode.next(),traversalList);

您打过两次电话next。也许您想要：

    T nextT = nextNode.next();
    if(visited(nextT)) {
        visit(nextT, traversalList);

但是如果条件被消除，!visited(nextT)显然更有意义。