patternjavaMajor

Depth First Search & Breadth First Search implementation

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

depthsearchbreadthfirstimplementation

Problem

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 queue = new LinkedList();

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].addCh

Solution

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 , 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> edges = new HashMap>();

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

    public Iterable getNeighbors(String vertex) {
        List 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.

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 {
    private Set visited = new HashSet();
    private Queue queue = new LinkedList();
    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 {
private Set visited = new HashSet();
private Deque> stack = new LinkedList>();
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 th

Code Snippets

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

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

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

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

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

Context

StackExchange Code Review Q#48518, answer score: 42

Revisions (0)

No revisions yet.