如何使用 java 中的邻接表为有向图实现深度优先搜索算法？

Question

我需要帮助编写一个方法，该方法 returns 根据在 DFS 遍历中遇到的顺序遍历图中所有节点的迭代器。该方法需要使用堆栈而不是递归。

Iterator<T> dfsNodeListing(T start){
    //Where start is the node that the dfs traversal will begin from.
}

我以哈希表的形式设置了后继者和前任者，以跟踪进出每个节点的边。我还有一个 ArrayList，如果搜索访问了节点，它就会被添加到该节点。

private Hashtable <T, Set<T>> pred = new Hashtable<>();
private Hashtable <T, Set<T>> succ = new Hashtable<>();
private ArrayList<T> mark = new ArrayList <>();

如何将所有这些元素结合在一起？

编辑：这是我目前正在使用的。我在中间的某个地方被卡住了，方法永远不会完成。

public Iterator<T> dfsNodeListing(T start) {
    Stack<T> stk = new Stack<>();
    stk.push(start);
    if(!mark.contains(start)){
        mark.add(start);
        stk.push(start);
        while(!stk.isEmpty()){
            stk.pop();
            for(T n : succ.get(start)){
                if(!mark.contains(n)){
                    stk.push(n);
                }
            }
        }
    }
    return mark.iterator();
}

Answer 1

我认为您的 foreach 循环有问题，因为您只能获得 start 节点的后继节点，而不是从堆栈中弹出的节点。您可以像这样修改您的代码：

while(!stk.isEmpty()){
        for(T n : succ.get(stk.pop())){
        if(!mark.contains(n)){
            stk.push(n);
            mark.add(n);
        }
    }
}

如何使用 java 中的邻接表为有向图实现深度优先搜索算法？

How do I implement a depth first search algorithm for a directed graph using an adjacency list in java?

java

algorithm

iterator

graph

depth-first-search