如何递归实现循环图的一般深度优先遍历?

问题描述 投票:0回答:1

正如问题的标题所说,我正在尝试对有向循环图进行深度优先遍历搜索。

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

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

   0 → 1 ↔ 2 → 4
   ↓       ↓ ⤢
   3       5

(注:将原始边4 4 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;
    }
}
java graph hash graph-traversal
1个回答
0
投票

这里似乎有一个错误:

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

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

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

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

© www.soinside.com 2019 - 2024. All rights reserved.