图：DFS 访问和 Java 实施

Question

我正在尝试使用 Java 语言对图实施递归深度优先搜索。

假设

图用邻接表表示。
GraphSearchImpl是一个存储访问结果的数据结构。
GraphSearchImpl 包含存储每个顶点 start/end 次、访问状态（UNDISCOVERED、DISCOVERED、CLOSED）、路径权重等的数组。
所有的顶点都有一个映射在HashMap中的唯一索引，其中String是每个顶点的唯一标签。我是 reading/writing 数组单元格，对于指定的顶点，使用此索引。

代码

    public void visitDFSRecursive(GraphSearchImpl search,VertexImpl u,Integer time) {
    int index = search.getIndexOf(u);
    search.status[index]=VertexImpl.DISCOVERED;
    time++;
    search.startTimes[index]=time;
    for (VertexImpl v: u.getAdjList()) {
        int adjIndex = search.getIndexOf(v);
        if (search.status[adjIndex]==VertexImpl.UNDISCOVERED) {
            search.status[adjIndex]=VertexImpl.DISCOVERED;
            search.parents[adjIndex]=u;
            visitDFSRecursive(search,v,time);
        }
    }
    search.status[index]=VertexImpl.CLOSED;
    time++;
    search.endTimes[index]=time;
    }

我正在这样调用此方法，在只有两个节点 (A -> B) 的图上：

g.visitDFSRecursive(search,sourceVertex,new Integer(0));

输出如下：

-A从1开始到2结束

-B 开始于 2 结束于 3

显然是错误的，因为B的start/end时间间隔必须包含在A的时间间隔中，因为B在这个图中是A的儿子。

我知道问题是我没有正确使用时间计数器。

求推荐。

Answer 1

问题在于 time 是一个局部变量，因此当您在递归中递增它时，A 的 time 不受影响。您应该将其转换为 global/static 变量，或者制作一个整数包装器 class 并通过可变对象传递它。

图：DFS 访问和 Java 实施

Graphs: DFS visit and Java implementation

java

recursion

graph

depth-first-search