University of Tuebingen Lehrstuhl Kognitive Systeme, Prof Dr. Zell
print version HomeJOELib JOELib Tutorial Algorithms BFS
 
Home
Introduction
Users/Publications
Screenshots
JOELib Tutorial
Contents
Preface
Installation
Basics
Functionalities
Utilities
Maintenance
Descriptors
Algorithms
BFS
DFS
Distance matrix
Geom. dist. matrix
Morgan
Interfaces
Interfaces JNI
Interface ML
Documentation
Examples
Applications
Support
Structures
Bibliography
Glossary
Index
JOELib2 Tutorial
JOELib API
JOELib2 API
Download
Mailing lists
License
Acknowledgements
Links
 
JOELib@FM
JOELib@SF
PMD Online
PMD Offline
CVS Repository
 
Research at WSI-RA
Software at WSI-RA
WSI-RA Department
Faculty
University
 

Chapter 6. Algorithms

Breadth First Search (BFS)

The BFS method performs a breadth-first search [clr98] of a graph. A breadth-first search visits vertices that are closer to the source before visiting vertices that are further away. In this context `distance' is defined as the number of edges in the shortest path from the source vertex.

Figure 6-1. Pseudocode for the BFS algorithm

paint all vertices white;
paint the source grey, set its distance to 0 and enqueue it;
repeat
  dequeue vertex v;
  if v is the target, we're done - exit this algorithm;
  paint v black;
  for each white neighbor w of v
	paint w grey;
	set distance w to (distance v + 1);
	set parent w to v;
	enqueue w
until the queue is empty
if we haven't yet exited, we didn't find the target
The time complexity is [clr98].


Last changes: 08.12.2010, 16:50 CET (UTC/GMT +1 hour) wegner.
http://www.ra.cs.uni-tuebingen.de/software/joelib/tutorial/algorithms/algorithms.html
2003 University of Tübingen, Germany