Scribd
Upload
46 views50 pages

Understanding Breadth First Search

The document describes how breadth-first search (BFS) works to traverse and search a graph data structure. BFS uses a queue to keep track of nodes to visit at each level. It starts by enqueueing the source node, then dequeueing nodes and exploring their unvisited neighbors before moving down to the next level.

Uploaded by

Jorge Prado
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
46 views50 pages

Understanding Breadth First Search

The document describes how breadth-first search (BFS) works to traverse and search a graph data structure. BFS uses a queue to keep track of nodes to visit at each level. It starts by enqueueing the source node, then dequeueing nodes and exploring their unvisited neighbors before moving down to the next level.

Uploaded by

Jorge Prado
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Breadth First Search

-
A B C D

E F G H

front

FIFO Queue
Breadth First Search

-
A B C D

E F G H

enqueue source node front A


FIFO Queue
Breadth First Search

-
A B C D

E F G H

dequeue next vertex front A


FIFO Queue
Breadth First Search

-
A B C D

E F G H

visit neighbors of A front

FIFO Queue
Breadth First Search

-
A B C D

E F G H

visit neighbors of A front

FIFO Queue
Breadth First Search

- A
A B C D

E F G H

B discovered front B
FIFO Queue
Breadth First Search

- A
A B C D

E F G H

visit neighbors of A front B


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I discovered front B I
FIFO Queue
Breadth First Search

- A
A B C D

E F G H

finished with A front B I


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

dequeue next vertex front B I


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

visit neighbors of B front I


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

visit neighbors of B front I


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

F discovered front I F
FIFO Queue
Breadth First Search

- A
A B C D

E F G H

visit neighbors of B front I F


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

A already discovered front I F


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

finished with B front I F


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

dequeue next vertex front I F


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

visit neighbors of I front F


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

visit neighbors of I front F


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

A already discovered front F


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

visit neighbors of I front F


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I B

E discovered front F E
FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I B

visit neighbors of I front F E


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I B

F already discovered front F E


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I B

I finished front F E
FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I B

dequeue next vertex front F E


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I B

visit neighbors of F front E


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I B F

G discovered front E G
FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I B F

F finished front E G
FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I B F

dequeue next vertex front E G


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I B F

visit neighbors of E front G


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I B F

E finished front G
FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I B F

dequeue next vertex front G


FIFO Queue
Breadth First Search

- A
A B C D

E F G H

I B F

visit neighbors of G front

FIFO Queue
Breadth First Search

- A G
A B C D

E F G H

I B F

C discovered front C
FIFO Queue
Breadth First Search

- A G
A B C D

E F G H

I B F

visit neighbors of G front C


FIFO Queue
Breadth First Search

- A G
A B C D

E F G H

I B F G

H discovered front C H
FIFO Queue
Breadth First Search

- A G
A B C D

E F G H

I B F G

G finished front C H
FIFO Queue
Breadth First Search

- A G
A B C D

E F G H

I B F G

dequeue next vertex front C H


FIFO Queue
Breadth First Search

- A G
A B C D

E F G H

I B F G

visit neighbors of C front H


FIFO Queue
Breadth First Search

- A G C
A B C D

E F G H

I B F G

D discovered front H D
FIFO Queue
Breadth First Search

- A G C
A B C D

E F G H

I B F G

C finished front H D
FIFO Queue
Breadth First Search

- A G C
A B C D

E F G H

I B F G

get next vertex front H D


FIFO Queue
Breadth First Search

- A G C
A B C D

E F G H

I B F G

visit neighbors of H front D


FIFO Queue
Breadth First Search

- A G C
A B C D

E F G H

I B F G

finished H front D
FIFO Queue
Breadth First Search

- A G C
A B C D

E F G H

I B F G

dequeue next vertex front D


FIFO Queue
Breadth First Search

- A G C
A B C D

E F G H

I B F G

visit neighbors of D front

FIFO Queue
Breadth First Search

- A G C
A B C D

E F G H

I B F G

D finished front

FIFO Queue
Breadth First Search

- A G C
A B C D

E F G H

I B F G

dequeue next vertex front

FIFO Queue
Breadth First Search

- A G C
A B C D

E F G H

I B F G

STOP front

FIFO Queue

You might also like