java - 如何检测以链表形式实现的图中的循环？

Question

我有一个使用 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

我不明白必须将链接列表图连接到名为“颜色”的数组并在遍历列表时分配颜色的部分。我不允许更改链表的节点结构(基本上是整个图)。我只允许实现循环方法来检测图中的循环并返回 boolean 值。该方法采用 Node 作为参数。有人可以指导我如何开始吗？

提前致谢。

Answer 1

color 将是一个用于标记节点的map - 如果发现节点 v 被标记为红色(if color[v] = RED) 则表示该节点已被访问过，并且已找到循环。