Scribd
Upload
21 views50 pages

Understanding Breadth First Search

The document describes how breadth first search of a graph is performed. It shows the steps of enqueueing the source node, dequeueing nodes and visiting their neighbors, and tracking visited nodes in a FIFO queue.

Uploaded by

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

Topics covered

  • Graph Node Processing,
  • Traversal Applications,
  • Traversal Methodologies,
  • Traversal Efficiency,
  • Search Algorithm Steps,
  • Traversal Algorithm Steps,
  • Queue Management,
  • Data Processing,
  • Graph Traversal Techniques,
  • Queue Operations
21 views50 pages

Understanding Breadth First Search

The document describes how breadth first search of a graph is performed. It shows the steps of enqueueing the source node, dequeueing nodes and visiting their neighbors, and tracking visited nodes in a FIFO queue.

Uploaded by

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

Topics covered

  • Graph Node Processing,
  • Traversal Applications,
  • Traversal Methodologies,
  • Traversal Efficiency,
  • Search Algorithm Steps,
  • Traversal Algorithm Steps,
  • Queue Management,
  • Data Processing,
  • Graph Traversal Techniques,
  • Queue Operations

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