I need to implement a DFS on a undirected graph. My data structure is simple. I have a Node class and a Dictionary It contains the neighbours (Node) of each node in the graph. So the keys are nodes and the values are their directly connected nodes. How can I implement the DFS for counting the cycles in the graph?
This is my current code:
foreach (Node n in nodeList)
{
while (loopFounded == false)
{
visitNode(n);
if (loopFounded == true)
{
loops.Add(loopIndex, new ArrayList(visiting));
visiting.Clear();
loopIndex = loopIndex + 1;
}
}
loopFounded = false;
}
The visitNode function is:
void visitNode(Node n)
{
if (visiting.Capacity != 0 && visiting.Contains(n))
{
Console.WriteLine("loop!");
loopFounded = true;
return;
}
visiting.Add(n);
if (neighbours.ContainsKey(n))
{
foreach (Node node in neighbours[n])
{
if (!visited.Contains(node) && !visiting.Contains(node))
{
visitNode(node);
}
}
visited.Add(n);
}
return;
}
It is returning only loops composed by couples of nodes... Can someone help me? Thanks