图表:DFS访问和Java实现

Question

我正在尝试在Java语言中实现递归深度优先搜索图形。

假设

• 该图用邻接列表表示。

• GraphSearchImpl是一种存储访问结果的数据结构。

• GraphSearchImpl包含存储每个顶点的开始/结束时间，访问状态(未发现，发现，已关闭(，路径权重等的数组。

• 所有顶点都有一个在 HashMap 中映射的唯一索引，其中字符串是每个顶点的唯一标签。我正在使用此索引读取/写入指定顶点的数组单元格。

法典

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 开始/结束的时间间隔必须包含在 A 的时间间隔中，因为 B 是此图中 A 的儿子。

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

请指教。

Answer 1

问题是time是一个局部变量，所以当你在递归中增加它时，A的time不受影响。您应该将其转换为全局/静态变量，或者创建一个整数包装器类并将其传递到可变对象。