У меня есть график, реализованный в виде двусвязного списка с использованием java.util.LinkedList. По сути, каждый узел в связанном списке является вершиной графа, и каждая из этих вершин связана с другими связанными списками для представления ребер. Меня просят использовать следующий алгоритм для обнаружения цикла на графике.
DFS-Cycle (u)
Precondition: u is a vertex in a graph G
Postcondition: a cycle reachable from u is returned, of one exists
color[u] <- RED
push u onto stack
for each v in Adj[u] //explore edge (u,v)
if color[v] = RED//back edge
return list of elements on stack
else if color[v] = BLACK
DFS-Cycle(v)
colour[u] <- GRAY
pop u from stack
Я не понимаю, в какой части вы должны соединить граф связанного списка с массивом, называемым «цвет», и назначать цвета при прохождении списка. Мне не разрешено изменять структуру узлов связанных списков (в основном весь график). Мне разрешено только реализовать метод цикла, чтобы обнаружить цикл в графе и вернуть логическое значение. Метод принимает узел в качестве аргумента. Может кто-нибудь подсказать, пожалуйста, с чего начать?
Спасибо заранее.