BreadthFirstSearcher

java.lang.Object

dsa.lab10.exercises.BreadthFirstSearcher

public class BreadthFirstSearcher extends Object

Breadth-first search (BFS).

Constructor Summary

Constructors

Constructor

Description

BreadthFirstSearcher()
Method Summary

Modifier and Type

Method

Description

static <Vertex, Weight> Map<Vertex,Path<Vertex,Integer>>

search(DirectedGraph<Vertex,Weight> graph, Vertex source)

Perform breadth-first search on the given graph from the given vertex.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details
- BreadthFirstSearcher
  
  public BreadthFirstSearcher()
Method Details
- search
  
  public static <Vertex, Weight> Map<Vertex,Path<Vertex,Integer>> search(DirectedGraph<Vertex,Weight> graph, Vertex source)
  
  Perform breadth-first search on the given graph from the given vertex.
  Returns a map whose keys are the connected vertices, i.e. the vertices that are reachable starting from the given source, and whose values are information about _how_ they're reachable, i.e. about a path that connects the source to it.
  The path information for each connected vertex is (a) the distance between the source and it (since we're ignoring edge weights, this is the number of steps/edges to get from the source to it) using the path found by BFS (which will use the minimum possible number of steps, but may not be the shortest if edge weights are taken into account), and (b) the previous vertex in the path found by BFS.
  For example, if the graph is a -> b -> c -> d e and the source is b, then the map returned by BFS will be b => null, 0; c => b, 1; d => c, 2;.
  
  Type Parameters:
  
  Vertex - the vertex type
  
  Weight - the weight type (on the edges)
  
  Parameters:
  
  graph - the graph
  
  source - the source vertex
  
  Returns:
  
  information about the vertices reachable from the given source