Implementing a BFS-search method for a graph

Question

I'm implementing my own graph class. My undirected graph is represented by a map which maps every node to a list storing the edges it has.

    private Map>> graphRep = new HashMap<>();

    private static class Edge {
        int cost;
        T node;
        public Edge(T n, int w) {
            node = n;
            cost = w;
        }

I have already created a recursive depth-first traversal method for my graph which utilizes a map to store the path between the start node to the search node. It does by mapping every node the next node on the path between the start node to end node.

    @Override
    public List depthFirstSearch(T start, T end) {
        Set visited = new HashSet();
        Map path = new HashMap<>();
        recursiveDFS(start, end, visited,path);
        List myList = new ArrayList();
        T current = end;
        myList.add(current);
        while (current != start) {
            myList.add(path.get(current));
            current = path.get(current);
        }
        System.out.println(path);
        System.out.println(myList);
        Collections.reverse(myList);
        return myList;
    }

    private void recursiveDFS (T node, T end, Set visited, Map path) {
        // uppdatera path och visited
        visited.add(node);
        for (Edge e : graphRep.get(node)) {
            if (e.node == end) {
                path.put(e.node, node);
                return;
            }
            if (!visited.contains(e.node)){
                path.put(e.node, node);
                recursiveDFS(e.node, end, visited, path);
            }
        }
    }

I believe I can utilize essentially the same code for the breadth-first search as with the depth-first search, only that the instead of traversing the nodes by depth I traverse them by breadth, and that's where I'm stuck. I'm completely lost on how to do that.


    @Override
    public List breadthFirstSearch(T start, T end) {

        Set visited = new HashSet();
        Map path = new HashMap<>();
        recursiveBFS(start, end, visited,path);
        List myList = new ArrayList();
        T current = end;
        myList.add(current);
        while (current != start) {
            myList.add(path.get(current));
            current = path.get(current);
        }
        System.out.println(path);
        System.out.println(myList);
        Collections.reverse(myList);
        return myList;
    }

    public void recursiveBFS (T node, T end, Set visited, Map path) {

        visited.add(node);
        for (Edge e : graphRep.get(node)) {
            if (e.node == end) {
                path.put(e.node, node);
                return;
            }
            if (!visited.contains(node)) {
              //Here's where I'm stuck. I have no idea how to traverse the graph by breadth
            }
        }
    }

How do I complete my breadth-first traversal method?

user_17949945 · Answer

BFS requires a container that will allow to retrieve nodes in the order they were visited. It can't be achieved with a Map. You need a Queue for that purpose (take a look carefully at the description of this algorithm).

Note that although BFS could be implemented recursively, the iterative approach is way better for this task.

Firstly, you need to create a queue and add a starting node into it. Then the queue will be passed as an argument to the recursiveBFS().

At each call of the recursiveBFS() a node at the beginning of the queue will be removed. If the queue is empty that will mean that the start-node and end-node are not connected.

That is how recursive implementation might look like:

public List breadthFirstSearch(T start, T end) {
    Map paths = new HashMap<>();
    Queue queue = new ArrayDeque<>();
    queue.add(start);
    recursiveBFS(end, new HashSet<>(), queue, paths);

    return getPath(start, end, paths);
}

public void recursiveBFS(T end, Set visited, Queue queue,  Map paths) {
    if (queue.isEmpty()) { // start-node and end-node are not connected
        return;
    }

    T parentNode = queue.remove();
    visited.add(parentNode);
    for (Edge edge : graphRep.get(parentNode)) { // avoid one-letter variables like "e" instead of edge
        if (visited.contains(parentNode)) {
            continue;
        }
        paths.put(edge.node, parentNode);
        // end node was found
        if (edge.node.equals(end)) { // don't compare object with "=="
            return;
        }
        recursiveBFS(end, visited, queue, paths); // this line was missing
    }
}

In order to make this solution adhere to the Single responsibility principle I extracted the logic for restoring the path from the start-node to end-node from the breadthFirstSearch() into the separate method.

public List getPath(T start, T end,  Map paths) {
    List path = new ArrayList();
    T current = end;
    path.add(current);
    while (current != start && current != null) { // if there's no path from start to end current eventually will become null
        path.add(paths.get(current));
        current = paths.get(current);
    }
    System.out.println(path);
    Collections.reverse(path);
    return current != null ? path : Collections.emptyList();
}

Recommendations:

The most important I want to point out is the overall design of your graph. While traversing the graph you heavily rely on the Map>> graphRep, edges are helpless without it. You might consider refining your graph so that its elements will be more self-contained. Firstly, in my opinion, the edge of a graph has to have two references because by definition it is meant to represent a connection between two vertices of the graph. And if you add a Vertex class to your graph then will contain reference a collection of edges then you can implement graph traversal algorithms using only edges and vertexes without a need to fall back on graphRep.
don't compare object with ==, use equals() method instead.
avoid one-letter variables like e.
don't name like myList, but try to come up with the name that explains the purpose of this variable (like path).

Update

Below is an iterative implementation of BFS:

public List breadthFirstSearch(T start, T end) {
    Map paths = new HashMap<>();
    Set visited = new HashSet<>();
    Queue queue = new ArrayDeque<>();
    queue.add(start);
    visited.add(start);
    boolean isFound = false;
    while (!isFound && !queue.isEmpty()) {
        T parentNode = queue.remove();
        for (Edge edge : graphRep.get(parentNode)) {
            if (!visited.add(edge.node)) {
                continue;
            }
            paths.put(edge.node, parentNode);
            // end node was found
            if (edge.node.equals(end)) {
                isFound = true;
                break;
            }
        }
    }
    return getPath(start, end, paths);
}

An iterative solution would be cleaner if you take into account recommendation above. And since for BFS as well as for DFS we don't need any information specific to edges (because vertex (node) can store data about adjusent vertexes) these algorithms could be implemented using vertecies only.

Implementing a BFS-search method for a graph

1 Answers