In the previous post I offered the following problem to solve:
The input data is the graph representation, for example the instance of LinkedList class. The output is Boolean value which is true if the graph has the cycle and false otherwise. The constraints are no additional memory should be used.
Let me publish the solution and the comments.
The solution.
To show the solution, I would like to use C# language. I realized that LinkedList<T> class which I referred in the puzzle definition can't represent the graph that has cycles because the methods of this class don't allow to set the next and previous node to the node which already belongs the list. So, the following class is used to show the solution.
internal class GraphNode<T>
{
private T _value;
private GraphNode<T> _next;
public GraphNode(T value)
{
_value = value;
}
public GraphNode<T> Next
{
get{ return _next;}
set{ _next = value;}
}
public override string ToString()
{
return _value.ToString();
}
}
static bool HasCycle<T>(List<GraphNode<T>> list)
{
if (list == null)
throw new ArgumentNullException("list");
if (list.Count == 0)
throw new ArgumentException("empty list", "list");
GraphNode<T> current1 = list[0];
GraphNode<T> current2 = list[0];
do
{
if (current1.Next == null || current2.Next == null || current2.Next.Next == null)
{
return false;
}
current1 = current1.Next;
current2 = current2.Next.Next;
if (ReferenceEquals(current1, current2))
{
return true;
}
} while (current1 != null && current2 != null);
return false;
}
The Analysis.
The idea behind the scene is very simple. The solution is using two pointers to the graph nodes, the first pointer goes through the graph with step 1(current1=current.Next) and the second pointer goes through the graph with step 2(current2=current.Next.Next). If the graph has the cycle, these two pointers will refer to the same node at some point which is obvious.However, I seen a lot of situations when people were not able to solve this puzzle quickly or didn't solve it at all.When I was asked to solve this puzzle several years ago I didn't solve it as well. And the reason of that is the conceptual blocks.
When I studied at the university, we learned the common algorithms and implemented them quite intensively. A lot of the algorithms dealt with the graphs - visiting the graph nodes, finding the shortest way between two graph nodes, etc. I used to use single pointer to the graph nodes for these algorithms. After more than 5 years this habit still persisted. This is some sort of the stereotype which is definitely the conceptual block. The second block is the same as I shown in the previous post - the tendency to delimit the problem area poorly. Sometimes people restrict themselves to using the single pointer. If one would know about the conceptual blocks and control the process of the problem solving, the "finding the cycle in the graph" become the pretty trivial task.
.gif){kind=link}