java - 实现接口中所有方法的深度优先遍历算法

Question

这是我实现深度优先遍历算法的类，但是在测试时它没有通过测试。

公共类 DepthFirstTraversal 扩展 AdjacencyGraph 实现 Traversal {

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

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


@Override
public List<T> traverse() throws GraphError {
    if (getNoOfNodes() == 0 || getNoOfEdges() == 0){
        throw new GraphError();
    }
    Set<T> nodes = getNodes();
    Iterator<T> nodeIterator = nodes.iterator();

    for (T t : nodes ){
        visited.put(t, false);
    }
    while (nodeIterator.hasNext()){
        T node = nodeIterator.next();

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

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

    visited.remove(node, true);

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

    while (nextNode.hasNext()){
        if (visited(nextNode.next())){
            visit(nextNode.next(), traversalList);
        }
    }
    return list;
}

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

下面是我的实现中必须包含的所有方法的邻接图类。

公共类 AdjacencyGraph 实现 Graph {

// The adjacency list for this graph.

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

// The current number of nodes in the graph.
 
private int noOfNodes = 0;

// The current number of edges in the graph.

private int noOfEdges = 0;

// Check if the graph contains a given node.
// @param node the node to be checked.
// @return (<tt>node</tt> is a node in the graph).

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


// Check if the graph contains a given edge between two nodes.
// @param start the start node of the edge to be checked.
// @param end the end node of the edge to be checked.
// @return (there is an edge from <tt>start</tt> to <tt>end</tt> in the graph).
 
public boolean contains(T start,T end) {
    // check that both nodes are in the graph, and then check that "end" is in
    // "start"'s entry in the adjacency list
    return contains(start) && contains(end) && adjacencyList.get(start).contains(end);
}


// Add a node to the graph.
// @param node the node to be added.
// @throws GraphError if the node is already in the graph.


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 {
        // Add a new entry to the adjacency list.  This is a new node, so it will not yet 
           have any
        // neighbours, so its entry in the adjacency list will be a new, empty, set
        adjacencyList.put(node,new HashSet<T>());
        // increase number of nodes
        noOfNodes++;
    }
}


// Remove a node, and all edges leading to and from it, from the graph.
// @param node the node to be removed - all edges leaving the node, and all edges entering 
// the node will also be deleted.
// @throws GraphError if the node does not exist.
 
public void remove(T node) throws GraphError {
    if (!contains(node)) {
        throw new GraphError("Cannot remove " + node + " from the graph.  No such node.");
    } else {
        // remove the node and all edges leaving it by removing its entry in the adjacency 
        // list
        // before doing so reduce the number of edges about to be removed
        noOfEdges -= getNeighbours(node).size();
        adjacencyList.remove(node);
        // reduce number of nodes
        noOfNodes--;
        // remove any links to the node by removing the node, if present, from all of the 
        // remaining
        // entries in the adjacencyList
        for (T start: adjacencyList.keySet()) {
            if (contains(start,node)) {
                // reduce number of edges
                noOfEdges--;
                // remove edge
                remove(start,node);
            }
        }
    }
}

/**
 * Add an edge to the graph.
 *
 * @param start the start node of the edge to be added.
 * @param end the end node of the edge to be added.
 * @throws GraphError if the edge already exists, or if either <tt>start</tt> or 
   <tt>end</tt> is not a node in the graph
 */
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++;
    }
}

/**
 * Remove an edge from the graph.
 *
 * @param start the start node of the edge to be removed.
 * @param end the end node of the edge to be removed.
 * @throws GraphError if there is no such edge in this graph
 */
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--;
    }
}

/**
 * Get the neighbours of a given node.
 *
 * @param node the node for which the neighbours should be found.
 * @return a set of the immediate successors of the node.
 * @throws GraphError if the node is not a node in the graph
 */
public Set<T> getNeighbours(T node) throws GraphError {
    // The neighbours can be accessed through this node's entry in the adjacency list.
    // Note: Create a copy of the entry to avoid users being able to change the adjacency 
       list.
    Set<T> copy = new HashSet<T>();
    for (T member: adjacencyList.get(node)) {
        copy.add(member);
    }
    return copy;
}

/**
 * Get the number of nodes in the graph.
 *
 * @return the number of nodes currently in this graph
 */
public int getNoOfNodes() {
    return noOfNodes;
}

/**
 * Get all the nodes in the graph.
 *
 * @return a set containing all the nodes in this graph
 */
public Set<T> getNodes() {
    // Note: The nodes can be accessed through the adjacency list's key set.
    // Note: Create a copy of the key set to avoid users being able to change the adjacency           
    list
    HashSet<T> copy = new HashSet<T>();
    for (T member: adjacencyList.keySet()) {
        copy.add(member);
    }
    return copy;
}

/**
 * Get the number of edges in the graph.
 *
 * @return the number of edges currently in this graph
 */
public int getNoOfEdges() {
    return noOfEdges;
}

}

问题 - 使用 AdjacenyGraph 类中的方法实现遍历方法。到目前为止的实现不会通过下面的测试。

标签： javadft