0

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

G5W
  • 36,531
  • 10
  • 47
  • 80
MarcoRaoul
  • 11
  • 3

0 Answers0