Depth First Search & Breadth First Search implementation

Question

I've implemented DFS and BFS implementations. I want to check if the code is readable, contains any issues, and can be improved.

GraphImplementation

package graphs;


import java.util.*;
import graphs.State;
public class GraphImplementation 
{
    public void dfs(Node root)
    {       
        //Avoid infinite loops
        if(root == null) return;

        System.out.print(root.getVertex() + "\t");
        root.state = State.Visited;

        //for every child
        for(Node n: root.getChild())
        {
            //if childs state is not visited then recurse
            if(n.state == State.Unvisited)
            {
                dfs(n);
            }
        }
    }

    public void bfs(Node root)
    {
        //Since queue is a interface
        Queue<Node> queue = new LinkedList<Node>();

        if(root == null) return;

        root.state = State.Visited;
         //Adds to end of queue
        queue.add(root);

        while(!queue.isEmpty())
        {
            //removes from front of queue
            Node r = queue.remove(); 
            System.out.print(r.getVertex() + "\t");

            //Visit child first before grandchild
            for(Node n: r.getChild())
            {
                if(n.state == State.Unvisited)
                {
                    queue.add(n);
                    n.state = State.Visited;
                }
            }
        }


    }

    public static Graph createNewGraph()
    {
        Graph g = new Graph();        
        Node[] temp = new Node[8];

        temp[0] = new Node("A", 3);
        temp[1] = new Node("B", 3);
        temp[2] = new Node("C", 1);
        temp[3] = new Node("D", 1);
        temp[4] = new Node("E", 1);
        temp[5] = new Node("F", 1);

        temp[0].addChildNode(temp[1]);
        temp[0].addChildNode(temp[2]);
        temp[0].addChildNode(temp[3]);

        temp[1].addChildNode(temp[0]);
        temp[1].addChildNode(temp[4]);
        temp[1].addChildNode(temp[5]);

        temp[2].addChildNode(temp[0]);
        temp[3].addChildNode(temp[0]);
        temp[4].addChildNode(temp[1]);
        temp[5].addChildNode(temp[1]);

        for (int i = 0; i < 7; i++) 
        {
            g.addNode(temp[i]);
        }
        return g;
    }

    public static void main(String[] args) {

        Graph gDfs = createNewGraph();
        GraphImplementation s = new GraphImplementation();

        System.out.println("--------------DFS---------------");
        s.dfs(gDfs.getNode()[0]);
        System.out.println();
        System.out.println();
        Graph gBfs = createNewGraph();
        System.out.println("---------------BFS---------------");
        s.bfs(gBfs.getNode()[0]);

    }

}

Graph.java:

package graphs;

public class Graph {

    public int count; // num of vertices
    private Node vertices[];

    public Graph()
    {
        vertices = new Node[8];
        count = 0;
    }

    public void addNode(Node n)
    {
        if(count < 10)
        {
            vertices[count] = n;
            count++;
        }
        else
        {
            System.out.println("graph full");
        }
    }

    public Node[] getNode()
    {
        return vertices;
    }
}

Node.java:

package graphs;
import graphs.State;
public class Node {

    public Node[] child;
    public int childCount;
    private String vertex;
    public State state;

    public Node(String vertex)
    {
        this.vertex = vertex;
    }

    public Node(String vertex, int childlen)
    {
        this.vertex = vertex;
        childCount = 0;
        child = new Node[childlen];
    }

    public void addChildNode(Node adj)
    {
        adj.state = State.Unvisited;
        if(childCount < 30)
        {
            this.child[childCount] = adj;
            childCount++;
        }
    }

    public Node[] getChild()
    {
        return child;
    }

    public String getVertex()
    {
        return vertex;
    }

}

State.java:

package graphs;

public enum State {

    Unvisited,Visiting,Visited;

}

Answer 1

Data Structure

Your terminology is a bit off. Trees have roots and children. Arbitrary graphs, on the other hand… I think "origin" and "neighbors" would be more appropriate.

• Visited flag: Storing the visited/unvisited flag in the Node hurts flexibility. Once you perform a dfs() or bfs(), that graph is "ruined". You won't be able to reset all nodes to the unvisited state. (Well, you could do it manually, since Node.state is a public field, after all. But that's nasty too.) Instead, I suggest that dfs() and bfs() keep a HashSet of visited nodes. Once the traversal is done, just discard the set.

• State.Visiting: That value is never used.

• Node.getNode(): The name suggests that it would return a single node, but it doesn't. Also, by returning the entire array, and the original of the array rather than a copy, you would be letting the caller alter the graph's connections in unapproved ways. Better to offer ways to iterate through all neighbours and to fetch a specific neighbour.

• Child vertex array: The Node constructor says: vertices = new Node[8]; However, addNode() checks if (count < 10). You should test against vertices.length instead.

  If the capacity is exceeded, you should't print to System.out as a side-effect. Throw an exception instead, so that the caller can decide how to handle it.

  Better yet, use an expandable data structure so that you don't have to deal with capacity limits. A simple substitution would be to use an ArrayList<Node>, but read on…

• Graph.vertices vs. Node.child: Those arrays seem to serve the same purpose, redundantly.

• Graph.createNewGraph(): It's cumbersome. Wouldn't it be nice to be able to write

  Graph g = new Graph();
  g.addEdge("A", "B");
  g.addEdge("B", "C");
  …
  return g;
  

My suggestion:

public class Graph {
    // Alternatively, use a Multimap:
    // http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html
    private Map<String, List<String>> edges = new HashMap<String, List<String>>();

    public void addEdge(String src, String dest) {
        List<String> srcNeighbors = this.edges.get(src);
        if (srcNeighbors == null) {
            this.edges.put(src,
                srcNeighbors = new ArrayList<String>()
            );
        }
        srcNeighbors.add(dest);
    }

    public Iterable<String> getNeighbors(String vertex) {
        List<String> neighbors = this.edges.get(vertex);
        if (neighbors == null) {
            return Collections.emptyList();
        } else {
            return Collections.unmodifiableList(neighbors);
        }
    }
}

Traversal

Your dfs() and bfs() methods can only ever print the node names. You can't reuse the code for anything else, since the System.out.print() calls are mingled with the graph traversal code. It would be better to implement an Iterator so that the caller can decide what to do with each node.

Also, DFS and BFS are two different strategies for accomplishing a similar task. Therefore, they should be implemented in two classes with a shared interface. I suggest an Iterator<String>.

The breadth-first iterator is a pretty straightforward translation of your original code, with the main difference being that the iterator is now responsible for keeping track of which vertices have been visited.

public class BreadthFirstIterator implements Iterator<String> {
    private Set<String> visited = new HashSet<String>();
    private Queue<String> queue = new LinkedList<String>();
    private Graph graph;

    public BreadthFirstIterator(Graph g, String startingVertex) {
        this.graph = g;
        this.queue.add(startingVertex);
        this.visited.add(startingVertex);
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean hasNext() {
        return !this.queue.isEmpty();
    }

    @Override
    public String next() {
        //removes from front of queue
        String next = queue.remove(); 
        for (String neighbor : this.graph.getNeighbors(next)) {
            if (!this.visited.contains(neighbor)) {
                this.queue.add(neighbor);
                this.visited.add(neighbor);
            }
        }
        return next;
    }
}

Unfortunately, you'll find that you can no longer use recursion for depth-first traversal. Instead, you'll have to rewrite it as an iterative solution using an explicit stack, which makes the code more complicated. (Alternatively, if you abandon the idea of making an Iterator and use the visitor pattern instead, then you could keep the same recursive code structure).

public class PreOrderDFSIterator implements Iterator<String> {
    private Set<String> visited = new HashSet<String>();
    private Deque<Iterator<String>> stack = new LinkedList<Iterator<String>>();
    private Graph graph;
    private String next;

    public PreOrderDFSIterator(Graph g, String startingVertex) {
        this.stack.push(g.getNeighbors(startingVertex).iterator());
        this.graph = g;
        this.next = startingVertex;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean hasNext() {
        return this.next != null;
    }

    @Override
    public String next() {
        if (this.next == null) {
            throw new NoSuchElementException();
        }
        try {
            this.visited.add(this.next);
            return this.next;
        } finally {
            this.advance();
        }
    }

    private void advance() {
        Iterator<String> neighbors = this.stack.peek();
        do {
            while (!neighbors.hasNext()) {  // No more nodes -> back out a level
                this.stack.pop();
                if (this.stack.isEmpty()) { // All done!
                    this.next = null;
                    return;
                }
                neighbors = this.stack.peek();
            }

            this.next = neighbors.next();
        } while (this.visited.contains(this.next));
        this.stack.push(this.graph.getNeighbors(this.next).iterator());
    }
}

Tests

This problem deserves better testing. With the original code, which always printed its output to System.out, there was no good way to write unit tests. Now, you can do anything you want with the results, so it is possible to write proper unit tests.

import static org.junit.Assert.*;

import org.junit.BeforeClass;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

import java.util.*;

// javac -cp .:junit.jar GraphTest.java
// java -cp .:junit.jar:hamcrest-core.jar org.junit.runner.JUnitCore GraphTest

@RunWith(JUnit4.class)
public class GraphTest {

    public static Graph graph1;

    @BeforeClass
    public static void makeGraphs() {
        Graph g = graph1 = new Graph();
        g.addEdge("A", "B");
        g.addEdge("B", "C");
        g.addEdge("B", "D");
        g.addEdge("B", "A");
        g.addEdge("B", "E");
        g.addEdge("B", "F");
        g.addEdge("C", "A");
        g.addEdge("D", "C");
        g.addEdge("E", "B");
        g.addEdge("F", "B");
    }

    private void expectIteration(String answer, Iterator<String> it) {
        StringBuilder sb = new StringBuilder();
        while (it.hasNext()) {
            sb.append(' ').append(it.next());
        }
        assertEquals(answer, sb.substring(1));
    }

    @Test
    public void preOrderIterationOfIsolatedVertex() {
        expectIteration("Z", new PreOrderDFSIterator(graph1, "Z"));
    }

    @Test
    public void preOrderIterationFromA() {
        expectIteration("A B C D E F", new PreOrderDFSIterator(graph1, "A"));
    }

    @Test
    public void preOrderIterationFromB() {
        expectIteration("B C A D E F", new PreOrderDFSIterator(graph1, "B"));
    }

    @Test
    public void BreadthFirstIterationOfIsolatedVertex() {
        expectIteration("Z", new BreadthFirstIterator(graph1, "Z"));
    }

    @Test
    public void BreadthFirstIterationFromA() {
        expectIteration("A B C D E F", new BreadthFirstIterator(graph1, "A"));
    }

    @Test
    public void BreadthFirstIterationFromB() {
        expectIteration("B C D A E F", new BreadthFirstIterator(graph1, "B"));
    }
}

Answer 2

As I mentioned in my other answer, hard-coding System.out.println() as the action for each node hurts code reusability. To let the caller specify the action to be performed on each node, without unrolling the recursion in the depth-first iterator, you can use the visitor pattern.

import java.util.*;

public class Graph<T> {

    public static interface Visitor<T> {
        void visit(T vertex);
    }

    // Alternatively, use a Multimap:
    // http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html
    private Map<T, List<T>> edges = new HashMap<T, List<T>>();

    public void addEdge(T src, T dest) {
        List<T> srcNeighbors = this.edges.get(src);
        if (srcNeighbors == null) {
            this.edges.put(src,
                srcNeighbors = new ArrayList<T>()
            );
        }
        srcNeighbors.add(dest);
    }

    public Iterable<T> getNeighbors(T vertex) {
        List<T> neighbors = this.edges.get(vertex);
        if (neighbors == null) {
            return Collections.emptyList();
        } else {
            return Collections.unmodifiableList(neighbors);
        }
    }

    public void preOrderTraversal(T vertex, Visitor<T> visitor) {
        preOrderTraversal(vertex, visitor, new HashSet<T>());
    }

    private void preOrderTraversal(T vertex, Visitor<T> visitor, Set<T> visited) {
        visitor.visit(vertex);
        visited.add(vertex);

        for (T neighbor : this.getNeighbors(vertex)) {
            // if neighbor has not been visited then recurse
            if (!visited.contains(neighbor)) {
                preOrderTraversal(neighbor, visitor, visited);
            }
        }
    }

    public void breadthFirstTraversal(T vertex, Visitor<T> visitor) {
        Set<T> visited = new HashSet<T>();
        Queue<T> queue = new LinkedList<T>();

        queue.add(vertex);              //Adds to end of queue
        visited.add(vertex);

        while (!queue.isEmpty()) {
            //removes from front of queue
            vertex = queue.remove(); 
            visitor.visit(vertex);

            //Visit child first before grandchild
            for (T neighbor : this.getNeighbors(vertex)) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

}

I've made the node type generic, just because it's possible.

Here are tests to demonstrate its usage.

import static org.junit.Assert.*;

import org.junit.BeforeClass;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

import java.util.*;

// javac -cp .:junit.jar Graph.java GraphTest.java
// java -cp .:junit.jar:hamcrest-core.jar org.junit.runner.JUnitCore GraphTest

@RunWith(JUnit4.class)
public class GraphTest {
    private static class CrumbtrailVisitor implements Graph.Visitor<String> {
        private StringBuilder sb = new StringBuilder();

        public void visit(String vertex) {
            sb.append(' ').append(vertex);
        }

        public String toString() {
            return sb.substring(1);
        }
    };

    public static Graph<String> graph1;

    @BeforeClass
    public static void makeGraphs() {
        Graph<String> g = graph1 = new Graph<String>();
        g.addEdge("A", "B");
        g.addEdge("B", "C");
        g.addEdge("B", "D");
        g.addEdge("B", "A");
        g.addEdge("B", "E");
        g.addEdge("B", "F");
        g.addEdge("C", "A");
        g.addEdge("D", "C");
        g.addEdge("E", "B");
        g.addEdge("F", "B");
    }

    @Test
    public void preOrderVisitorFromA() {
        Graph.Visitor<String> crumbtrailVisitor = new CrumbtrailVisitor();
        graph1.preOrderTraversal("A", crumbtrailVisitor);
        assertEquals("A B C D E F", crumbtrailVisitor.toString());
    }

    @Test
    public void breadthFirstVisitorFromB() {
        Graph.Visitor<String> crumbtrailVisitor = new CrumbtrailVisitor();
        graph1.breadthFirstTraversal("B", crumbtrailVisitor);
        assertEquals("B C D A E F", crumbtrailVisitor.toString());
    }
}

As you can see, the inversion of control makes things more awkward for the caller. But you still gain the ability to specify an arbitrary action. Also, with Java 8 method references, the simple case is easy — you can just write graph1.preOrderTraversal("A", System.out::println).

Answer 3

I'd use lists instead of a arrays and public counter. eg.:

public class Graph
{
   private List<Node> vertices = new LinkedList<Node>();    

   public void addNode(Node n)
   {        
       if(vertices.length >= 10){
           System.out.println("graph full");
           return;
       }            
       vertices.add(n);      
   }

   public Node[] getNode()
   {
        return vertices.toArray;
   }
}

There is also a bug in your Graph-class, since your array is limited to 8 entries, but you are filling it until your is counter >= 10.

Your Node-class contains public members with getters? I'd make them private ;)

I'd also remove redundant comments. e.g.: "for every child" at a for loop. Since everybody knows what an for loop does.

Let your code be the description:

for(Node child: root.getChild())
 if(child.state == State.Unvisited)
  dfs(n);

Answer 4

Overall a good design. However there are few points which you should pay attention to.

Access Modifiers: You code has some properties as public and also public getter. This makes no sense. You should choose the access modifiers carefully. Anybody can access the child (NodeArray) and set to null if this code is used as an API by some user.

public Node[] child;

public Node[] getChild()
{
    return child;
}

This should be

private Node[] child;

public Node[] getChild()
{
    return child;
}

public void setChild(Node node){
 // set Node to first empty location in Node array
  if(node != null)
    child[nonEmptyLocation] = node;
}

// if you want to set whole array
public void setChildren(Node[] nodes){
  if(nodes!= null && nodes.length > 0)// check that the data is valid
    this.nodes = nodes;
}

---

public class Graph {

   public int count; // num of vertices

Static Functions: Your DFS and BFS functions are not static. I can think of no reason to do that when you have create function as static. Better make it consistent.