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?
There are several mistakes in your solution:
visited
will contain all a sequence of visited nodes, but not a path from the start node to end node;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:
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();
}