Discrete Mathematics

204

DISCRETE

MATHEMATICS·------------------------~

6.6

BREADTH-FIRST SEARCH

6.6.1

Introduction

Breadth-first search is a variant

of

search that is guided by a queue, instead

of

depth-first search's stack.

The search always starts from a particular

nodes,

called the source, to discover all the vertices that can

be reached from s along the edges

of

the graph.

It

also computes the distance (fewest number

of

edges) from

s to each

of

these reachable vertices and it produces a breadth-first tree with

roots

that includes all the vertices

reachable from s such that for any vertex v reachable from

s,

the path from s to v

in

the breadth-first tree

corresponds ...