Graph/BreadthFirstSearch/counter_bfs.cxx File Reference

Extends Breadth First Search with counter

A breadth-first search implementation that increments a counter with each vertex found, to be able to compare results against corresponding depth-first search implementations. More...

#include "bfs.h"

Functions

void bfs_search (Graph const &graph, int s, vector< int > &dist, vector< int > &pred)
 Given (directed or undirected) graph, perform a breadth first search starting from the provided source vertex, and compute the BFS distance and predecessor vertex for all vertices in the graph.


Detailed Description

Extends Breadth First Search with counter

A breadth-first search implementation that increments a counter with each vertex found, to be able to compare results against corresponding depth-first search implementations.

Author:
George Heineman
Date:
6/15/08

Function Documentation

void bfs_search ( const Graph graph,
int  s,
vector< int > &  dist,
vector< int > &  pred 
)

Given (directed or undirected) graph, perform a breadth first search starting from the provided source vertex, and compute the BFS distance and predecessor vertex for all vertices in the graph.

Parameters:
graph the graph to be processed.
s the initial vertex (0 <= s < n) from which to search.
dist the computed dist[] array for each vertex from s.
pred the computed pred[] array to be able to recover path.

Algorithm Development Kit 1.0