Data Abstraction and Problem Solving with C++

Walls and Mirrors

by Frank M. Carrano

BFS Class Reference

#include <BFS.h>

List of all members.

Detailed Description

A breadth-first search of the Graph class.

Definition at line 25 of file BFS.h.

Public Member Functions

BFS (const Graph &g)

void startSearch ()

Protected Member Functions

void search (Edge e)

Protected Attributes

const Graph & g

int count

vector< int > mark

vector< int > parents

Constructor & Destructor Documentation

BFS::BFS ( const Graph & g )

Constructor
Precondition:
The graph exists.

Postcondition:
Initializes arguments and starts the breadth-first search.

Definition at line 20 of file BFS.cpp.
References startSearch().

Member Function Documentation

void BFS::search ( Edge e ) [protected]

Searches the adjacency list of each vertex breadth first.
Precondition:
The edge exists in the graph.

Postcondition:
Performs a breadth first search of the adjacency list of vertex w in Edge e.

Definition at line 34 of file BFS.cpp.
References Graph::adjList, count, g, mark, parents, Edge::v, Edge::w, and Edge::weight.
Referenced by startSearch().

void BFS::startSearch ( )

Searches each unvisited vertex
Precondition:
The edge exists in the graph.

Postcondition:
Starts a breadth first search with each unvisited vertex.

Definition at line 26 of file BFS.cpp.
References g, Graph::getNumVertices(), mark, and search().
Referenced by BFS().

Member Data Documentation

const Graph& BFS::g [protected]

Definition at line 28 of file BFS.h.
Referenced by search(), and startSearch().

int BFS::count [protected]

Used to mark vertices as visited.
Definition at line 31 of file BFS.h.
Referenced by search().

vector<int> BFS::mark [protected]

Marked vertices.
Definition at line 34 of file BFS.h.
Referenced by search(), and startSearch().

vector<int> BFS::parents [protected]

Parents of each vertex.
Definition at line 37 of file BFS.h.
Referenced by search().

The documentation for this class was generated from the following files:

Generated on Sun Aug 27 22:27:08 2006 for

1.4.6