title: How to detect a cycle in a graph implemented as a linked list?
body: <p>I have a graph implemented as a doubly linked list using java.util.LinkedList.  Basically, each node on the linked list is a vertex of the graph, and each of those vertices are connected to other linked lists to represent the edges.  I'm asked to use the following algorithm to detect a cycle in the graph.  </p>
  
  <pre><code>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] &lt;- 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] &lt;- GRAY
      pop u from stack
  </code></pre>
  
  <p>I do not understand the part where you have to connect the linked list graph to an array called "color" and assign colors as you traverse the list.  I'm not permitted to change the node structure of the linked lists (Basically the whole graph).  I'm only allowed to implement the cycle method to detect a cycle in the graph and return a boolean.  The method takes a Node as an argument.  Can someone please guide me on how to begin with?  </p>
  
  <p>Thanks in advanced.</p>