Graph/BreadthFirstSearch/bfs.h File Reference

Defines the interface to Breadth-First Search

Defines the interface to breadth-first search. More...

#include <queue>
#include "Graph.h"

Go to the source code of this file.

Functions

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.


Detailed Description

Defines the interface to Breadth-First Search

Defines the interface to breadth-first search.

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