Breadth-first search from one node to another

user_18000842 0
Viewed 167

I'm implementing my own graph class, and I'm currently making my own BFS-search method. Right now it traverses all vertices from one root vertex.

public List<T> breadthFirstSearch(T start, T end) {
    List<T> visited = new ArrayList<T>();
    Queue<T> path = new LinkedList<T>();
    visited.add(start);
    path.add(start);
    while (!path.isEmpty()){
        T currentNode = path.poll();
        for (Edge<T> edge: graphRep.get(currentNode)) {
            if (!visited.contains(edge.node)) {
                visited.add(edge.node);
                path.add(edge.node);
            }
        }
    }
    System.out.println(visited);
    return visited;
}

What I want to do is to find the path from vertex start to vertex end, but right now it finds the path between the start to all nodes. How do I change my code so that it only finds the path between the start to end?

breadth-first-search depth-first-search graph java
1 Answers

There are several mistakes in your solution:

  • you not checking whether you find the target node;
  • case, when it is not possible to reach the end from the start node, is not covered in your solution;
  • the list visited will contain all a sequence of visited nodes, but not a path from the start node to end node;
  • method contains() costs O(n) for a list, you definitely have to use a HashSet for that purpose;
  • ArrayDeque will perform better than LinkedList (technically it's not a mistake but rather a strong recommendation).

So to fix your code you need to add a check whether the node to which points the current edge is equal to the end node and a boolean flag to break out from the loop (there's no need to do farther iterations).

In the code below HashMap paths is used for two purposes:

  • to track the parent node for each visited node in order to restore the path from start to end;
  • to check whether a new node is already visited.

Method getPath() will either return list nodes that represents a direct path from start to end an empty list if the path doesn't exist.

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

public List<T> getPath(T start, T end,  Map<T, T> paths) {
    List<T> path = new ArrayList<T>();
    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();
}
user_179499450
Related