Я пытаюсь реализовать рекурсивный поиск в глубину для графика на языке 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 на этом графике.
Я знаю, что проблема в том, что я не правильно использую счетчик времени.
Пожалуйста, предложите.