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;
}

• wayfare: Is this code for learning/assignment purpose or for working software/app ?
• fscore: @Xiang m trying to learn graphs on my own and various search algorithms to become efficient in trees & graphs
• Sanjay Kumar: I find it useful - opendatastructures.org/ods-java/12_3_Graph_Traversal.html . Explains everything clearly with pseudo code.

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"));
 }
}

• fscore: What would be better to use: Graph.vertices vs. Node.child?
• 200_success: Neither! Store Graph.edges instead.
• fscore: Whats with the tradeoff of Iterators? just to avoid 2 lines of code, using iterator would be good enough?
• 200_success: The main benefit of implementing an Iterator is that everyone can immediately tell how to use it. The Iterator provides a very convenient interface for the caller, at the expense of complicating your depth-first traversal code.
• Mona Jalal: hey @200_success why do you suggest edges to be of the type private Map<String, List<String>> edges = new HashMap<String, List<String>>(); ??

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);

• fscore: why would you use lists instead of arrays? whats the tradeoff?
• wayfare: Arrays are continuous allocated memory and in list there is no guarantee. So accessing objects in array is much faster. *Arrays are not dynamic in size but list are.
• ceco: For me Lists are easier to handle. They dont throw nasty overflow errors. You dont need a counter, because the list already contains those informations.
• ceco: No, the getters have to be public. The member fields should be private.
• David Harkness: @Xiang ArrayList uses a contiguous array under the hood while LinkedList uses a non-contiguous chain of nodes.

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.

• fscore: so you are saying I should use private in those methods and import class in main program to use the methods? what could be another way of doing it
• wayfare: No, the way this should be done is make the class properties as private and then provide public setters/getters. This way you will have control on how the data is changed.
• fscore: Can you edit my code and show me few examples of what you are saying?
• wayfare: Code edited. Should be easy to understand now.
• 200_success: In general, it's a good idea to provide getters and setters to prevent others from meddling with your object's internal state. However, these particular getters and setters add complexity but don't provide much protection over public Node[] child.