Computer Science

Graph Traversal BFS & DFS

1

Graph Traversal Overview

To traverse means to visit the vertices in some systematic order We are familiar with tree traversal

 Preorder  Inorder  Postorder

Tree traversal is different but related to graph traversal How can we traverse a graph? How does graph traversal related to tree traversal?

2

Graph Traversal Methods

Two methods

breadth first search (BFS) depth first search (DFS)

Both construct spanning trees with certain properties useful in other graph algorithms Useful for undirected & directed graph

3

BFS

choose some starting vertex x mark x enqueue(Q,x) // Q is a queue tree T = x the tree T constructed by the algorithm is while Q nonempty called a breadth first search tree. It is also a v = dequeue(Q) spanning tree. visit v for each unmarked neighbor w mark w

enqueue(Q,w)

add edge v-w to T

4

BFS - illustration

unmark all vertices 1 3 4 G 5 2 4 T 5 3 1 2

1

2

3

4

5

mark

Q

0

0

0

0

0

5

BFS - illustration

choose some starting vertex x (choose 1) mark x enqueue(Q,x) tree T = x 1 2 4 G 5 3 2 4 T 5 1 3

1

2

3

4

5

mark

Q 1

1

0

0

0

0

6

BFS - illustration

while Q nonempty v = dequeue(Q) = 1 visit v for each unmarked neighbor w (2, 4) mark w enqueue(Q,x) add edge v-w to T

1 2 4 G

1 3 5 2 4

1 3 5 T

1 mark

Q 24

2 1

3 0

4 1

5 0

7

1

BFS - illustration

while Q nonempty v = dequeue(Q) = 2 visit v for each unmarked neighbor w (3, 5) mark w enqueue(Q,x) add edge v-w to T

1

1

1

2

2

4 G 5

3

2 4 T 5

3

1 mark

Q 435

2 1

3 1

4 1

5 1

8

1

BFS - illustration

while Q nonempty v = dequeue(Q) = 4 visit v for each unmarked neighbor w ( null ) mark w enqueue(Q,x) add edge v-w to T

1

1

1

2

2

4 G 5

3

2 4 T 5

3

3

1 mark

Q 35

2 1

3 1

4 1

5 1

9

1

BFS - illustration

while Q nonempty v = dequeue(Q) =...