How efficient is the below BFS implementation?

Question

I am trying to learn BFS and trying to analyse BFS time complexity on my own. But I could not wrap my head around it. Below is my implementation of Graph data structure and BFS algorithm. Is the time complexity here really O(Vertex + Edges) in my implementation. If not, what am I missing here in terms of efficiency time complexity.

public class Graph {

    private final Map<Vertex, List<Vertex>> nodes;

    public Graph() {
        this.nodes = new HashMap<>();
    }

    public void addEdge(Vertex source, Vertex target) {
        List<Vertex> neighbours = getEdges(source);
        if(!neighbours.contains(target))
            neighbours.add(target);
        this.nodes.put(source, neighbours);
    }

    public List<Vertex> getEdges(Vertex source) {
        return this.nodes.getOrDefault(source, new LinkedList<>());
    }
}

public class BreadthFirstSearch {

    private final Graph graph;
    private final Queue<Vertex> queue;
    private final Set<Vertex> visited;

    public BreadthFirstSearch(Graph graph) {
        this.graph = graph;
        this.queue = new LinkedList<>();
        this.visited = new HashSet<>();
    }

    public void doBFS() {
        this.graph.getNodes().forEach((key, value) -> {
            this.queue.add(key);
            this.queue.addAll(value);
            while(!this.queue.isEmpty()) {
                Vertex vertex = this.queue.poll();
                if(this.visited.contains(vertex)) {
                    continue;
                }
                System.out.print(vertex + " -> ");
                visited.add(vertex);
            }
        });
    }
}

Answer 1

You have not implemented a BFS search as you do not iteratively add vertices to the queue as they are reached - you only ever add the vertices and their immediately adjacent neighbours with each pass of the outer loop and that is not a BFS.

---

In Java:

• HashMap.foreach has a time complexity of O(buckets + n) - for a fixed number of hash buckets, this is effectively O(n).
• Collection.add has a time complexity of O(1).
• Collection.addAll has a time complexity of O(n).
• LinkedList.poll has a time complexity of O(1).
• Collection.isEmpty has a time complexity of O(1).
• HashSet.contains has a worst-case time complexity of O(log(n)) (or O(n) if you are using Java 7 or below). Assuming that your objects hash with an even distribution and the number of items is not orders of magnitude greater than the number of buckets used by the HashSet then the average time-complexity can be considered to be O(1).

So each line of your code has the time complexity:

this.graph.getNodes().forEach((key, value) -> {    // O(|V|)
  this.queue.add(key);                             //   O(1)
  this.queue.addAll(value);                        //   O(|vertex.adjacent|)
  while(!this.queue.isEmpty()) {                   //   O(1)
    Vertex vertex = this.queue.poll();             //     O(1)
    if(this.visited.contains(vertex)) {            //     O(log(|V|)) worst-case
      continue;                                    //       O(1)
    }                                              //
    System.out.print(vertex + " -> ");             //     O(1)
    visited.add(vertex);                           //     O(1)
  }                                                //
});                                                //

In this case, using addAll is not actually a problem because, for each vertex, you are adding each adjacent vertex, which is equivalent of iterating over the edges in a single direction. So aggregated over the entirety of the outer loop you are going to add each edge's adjacent vertex in each direction so this is O(2E), or simply O(E).

Where you do have an issue is that checking if a vertex is visited is O(log(n)) worst-case time complexity and that is done for each vertex each time you want to add it to the queue. Since you check for each adjacent vertex of each edge then over the entire process this is O(E.log(V)) worst-case time-complexity (and O(E) average time-complexity, assuming the previously mentioned preconditions hold).

Your entire algorithm is O(V + E.log(V)) worst-case time-complexity (or O(V + E.V) worst-case time complexity if you are using Java 7 or earlier) and O(V + E) best-case/average time-complexity (again, assuming the previous preconditions are met).

---

To fix the worst-case time complexity issues:

• You could add a visited flag to the Vertex object and set the flag on the object or, if your vertices each have a unique sequential numerical index (i.e. they are numbered 0 .. |V|-1), you could have an array of boolean flags on the BreadthFirstSearch object corresponding to each vertex and update the flag in the array. Either way you could update the flags in O(1) time.
• You can stop using a HashMap to store the adjacency lists and, instead, store the lists as an attribute on each vertex.

Something like:

public class BreadthFirstSearch {

    private final Graph graph;
    private final Queue<Vertex> queue;
    private final boolean[] visited;

    public BreadthFirstSearch(Graph graph) {
        this.graph = graph;
        this.queue = new LinkedList<>();
        this.visited = new boolean[graph.nodes.size()];
    }

    private void enqueue(final Vertex vertex)
    {
        int index = vertex.index;
        if (!this.visited[index])
        {
            this.queue.add(vertex);
        }
    }

    public void doBFS() {
        this.graph.getNodes().forEach((key, value) -> {
            this.enqueue(key);
            while(!this.queue.isEmpty()) {
                final Vertex vertex = this.queue.poll();
                System.out.print(vertex + " -> ");
                LinkedList<Vertex> neighbours = vertex.getAdjacent();
                for (final Vertex adjacent: neighbours)
                {
                    this.enqueue(adjacent);
                }
            }
        });
    }
}

This assumes that you can write a vertex.getAdjacent method that has an O(1) worst-case time complexity. With your current implementation using a HashMap to store relationships this is unlikely as HashMap.get has O(log(n) worst-case time complexity. Instead, you may need to look a storing the adjacent edges as an attribute on each Vertex instance rather than in a HashMap on the graph.

Answer 2

The time complexity of BFS is O(V + E). However, I have a few parts that I don't understand about your code. In your BreadthFirstSearch#doBFS, you add the node and all the nodes that node can reach for all nodes. You shouldn't be looping over each node in BFS; you just need to add the first node to the queue and while the queue isn't empty, process the node.

public void doBFS(Vertex start) {
    queue.add(start);
    while (!queue.isEmpty()) {
        Vertex current = queue.poll();
        System.out.println("vertex " + current + " visited");
        for (Vertex target : graph.getNodes().getOrDefault(current, List.of())) {
            if (!this.visited.contains(target)) {
                queue.add(target);
            }
        }
    }
}