Modify the DFS method so that it can detect if a Graph is a Tree or not

Question

This DFS method has to be changed, so it can check a graph on having cycles in it. My problem is to code it, because of my little expeirience in coding. It looks like my post is almost code :D

public void DFS()
 {
  Stack<Integer> stack = new Stack<Integer>();
  boolean[] visited = new boolean[N];

  for (int i = 0; i < N; i++) {
  if (!visited[i]) { // find another unvisited vertex

stack.push(i); // and push it into the stack
visited[i] = true; // mark it as visited
System.out.print((i + 1) + " ");

while (!stack.isEmpty()) { // repeat until the stack is empty

 int v = stack.peek(); // get the top vertex in stack

 // trying to find next unvisited neighbor
 boolean hasNeighbor = false;

 for (int j = 0; j < N; j++) {
  if (!visited[j] && connected(v, j)) {
   stack.push(j);
   visited[j] = true;
   System.out.print((j + 1) + " ");

   // so it has an unvisited neighbor vertex
   hasNeighbor = true;

   // found one - don't need to search anymore
   break;
  }
 }

 // if a vertex has no more neighbors
 // we can remove it from the stack
 if (!hasNeighbor)
  stack.pop();
}
 }
  }

System.out.println();
 }

Answer 1

Adding an else statement to your condition:

if (!visited[i]) { 

will do the trick.

So... your method should end like this:

        } else {
          graph = true;
        }
    }
    System.out.println();
}

Edit: You might have to do some extra changes though, like add another boolean array which would distinguish between elements that you are just "visiting", i.e. you are in their left or right subtree and nodes that you have already fully visited. I would suggest you do this by replacing your existing boolean array with a byte array:

1. You visit a node, now you want to visit its left tree. No matter if it has one, before visiting it, you put VISITED[node] ++;

2. You try visiting its right subtree. Same procedure.

3. Add a check to see if VISITED[node] > 2. If yes, you certainly have a graph.