com.mhhe.clrs2e
Class BFS

java.lang.Object
  |
  +--com.mhhe.clrs2e.BFS

public class BFS

extends java.lang.Object

Class that performs a breadth-first search on a graph. Based on BFS code on page 532 of Introduction to Algorithms, Second edition.

Field Summary

private com.mhhe.clrs2e.BFSInfo[]

bfsInfo Array of BFSInfo objects, one per vertex, to hold the result of the breadth-first search.

Constructor Summary

BFS()

Method Summary

com.mhhe.clrs2e.BFSInfo	getBFSInfo(int v) Returns a reference to the BFSInfo object for a given vertex.
com.mhhe.clrs2e.BFSInfo	getBFSInfo(com.mhhe.clrs2e.Vertex v) Returns a reference to the BFSInfo object for a given vertex.
void	search(com.mhhe.clrs2e.AdjacencyListGraph g, com.mhhe.clrs2e.Vertex s) Performs a breadth-first search on a graph from a given source vertex, filling in distances and parents in the predecessor graph in the bfsInfo array.

Methods inherited from class java.lang.Object

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

Field Detail

bfsInfo

private com.mhhe.clrs2e.BFSInfo[] bfsInfo

Array of BFSInfo objects, one per vertex, to hold the result of the breadth-first search.

Constructor Detail

BFS

public BFS()

Method Detail

search

public void search(com.mhhe.clrs2e.AdjacencyListGraph g,
                   com.mhhe.clrs2e.Vertex s)

Performs a breadth-first search on a graph from a given source vertex, filling in distances and parents in the predecessor graph in the bfsInfo array.

Parameters:

g - The graph.

s - The source vertex.

getBFSInfo

public com.mhhe.clrs2e.BFSInfo getBFSInfo(com.mhhe.clrs2e.Vertex v)

Returns a reference to the BFSInfo object for a given vertex.

Parameters:

v - The vertex for which the corresponding BFSInfo is returned.

getBFSInfo

public com.mhhe.clrs2e.BFSInfo getBFSInfo(int v)

Returns a reference to the BFSInfo object for a given vertex.

Parameters:

v - The index of the vertex for which the corresponding BFSInfo is returned.