'Implementing a BFS-search method for a graph

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<T, List<Edge<T>>> graphRep = new HashMap<>();

    private static class Edge<T> {
        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<T> depthFirstSearch(T start, T end) {
        Set<T> visited = new HashSet<T>();
        Map<T,T> path = new HashMap<>();
        recursiveDFS(start, end, visited,path);
        List<T> myList = new ArrayList<T>();
        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<T> visited, Map<T, T> path) {
        // uppdatera path och visited
        visited.add(node);
        for (Edge<T> 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<T> breadthFirstSearch(T start, T end) {

        Set<T> visited = new HashSet<T>();
        Map<T,T> path = new HashMap<>();
        recursiveBFS(start, end, visited,path);
        List<T> myList = new ArrayList<T>();
        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<T> visited, Map<T, T> path) {

        visited.add(node);
        for (Edge<T> 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?



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source