com.codemelon.graph.algorithm.search

Class BreadthFirstSearch<T extends BfsVertex>

java.lang.Object

com.codemelon.graph.algorithm.search.BreadthFirstSearch<T>

public class BreadthFirstSearch<T extends BfsVertex>
extends java.lang.Object

Implementation of breadth-first search following CLRS, pp. 594ff. The graph to be searched may be directed or undirected.

Constructor Summary

Constructors

Constructor and Description
BreadthFirstSearch(AbstractGraph<T> graph) Prepares the search on the given graph

Method Summary

Methods

Modifier and Type	Method and Description
T	getSourceVertex() Returns the source vertex specified when search() was called.
java.util.LinkedList<BfsVertex>	path(BfsVertex target) Shows a shortest path from the source vertex passed in the search() method to any given vertex in the graph.
void	search(T source) Executes the search on the input graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BreadthFirstSearch

public BreadthFirstSearch(AbstractGraph<T> graph)

Prepares the search on the given graph

Parameters:

graph - graph that will be searched

Method Detail

search

public void search(T source)

Executes the search on the input graph. Sets the parent of the source vertex to null and sets parents for all vertices reachable from source according to a shortest path from source to the given vertex. Unreachable vertices will have parent set to null after this method call. Reachable vertices will further have distances entered according to the minimum number of steps (edges) required to reach them from source. The source vertex will show a distance of 0, and unreachable vertices will have distances set to -1

Parameters:

source - source vertex from which shortest paths are to be determined

getSourceVertex

public T getSourceVertex()

Returns the source vertex specified when search() was called.

Returns:

the source vertex specified when search() was called

path

public java.util.LinkedList<BfsVertex> path(BfsVertex target)

Shows a shortest path from the source vertex passed in the search() method to any given vertex in the graph. For actually getting the list rather than just printing, a loop seems easier than the recursion used by CLRS (p. 601)

Parameters:

target - the vertex to which the path is returned

Returns:

the shortest path from the source vertex passed in a prior call of search() to the target vertex. Returns null if the target is not reachable from the source vertex.

Throws:

java.lang.IllegalStateException - if search() has not yet been called