Bfs

Breadth-First Search

5/7/2002 11:06 AM

Outline and Reading Breadth-first search (§6.3.3)

Breadth-First Search

Algorithm Example Properties Analysis Applications

„ „ „

L0 L1

A

B

„

C

L2

E

„

D

DFS vs. BFS (§6.3.3)

F

Comparison of applications Comparison of edge labels

„ „

5/7/2002 11:06 AM

Breadth-First Search

1

5/7/2002 11:06 AM

Breadth-First Search Breadth-first search (BFS) is a general technique for traversing a graph A BFS traversal of a graph G „

„

„

„

Visits all the vertices and edges of G Determines whether G is connected Computes the connected components of G Computes a spanning forest of G

5/7/2002 11:06 AM

„

A

L0 L1

L1

B

C E

5/7/2002 11:06 AM

D

L0

A

B

L0 L1

F

C

D

L1

Breadth-First Search

4

B

L0

A

B

F

C E

L0

A C E

Breadth-First Search

5/7/2002 11:06 AM

Algorithm BFS(G, s) L0 ← new empty sequence L0.insertLast(s) setLabel(s, VISITED) i←0 while ¬Li.isEmpty() Li +1 ← new empty sequence for all v ∈ Li.elements() for all e ∈ G.incidentEdges(v) if getLabel(e) = UNEXPLORED w ← opposite(v,e) if getLabel(w) = UNEXPLORED setLabel(e, DISCOVERY) setLabel(w, VISITED) Li +1.insertLast(w) else setLabel(e, CROSS) i ← i +1

Example (cont.)

E

A

Algorithm BFS(G) Input graph G Output labeling of the edges and partition of the vertices of G for all u ∈ G.vertices() setLabel(u, UNEXPLORED) for all e ∈ G.edges() setLabel(e, UNEXPLORED) for all v ∈ G.vertices() if getLabel(v) = UNEXPLORED BFS(G, v)

3

L0

unexplored vertex visited vertex unexplored edge discovery edge cross edge

A

The algorithm uses a mechanism for setting and getting “labels” of vertices and edges

Find and report a path with the minimum number of edges between two given vertices Find a simple cycle, if there is one

Breadth-First Search

Example

2

BFS Algorithm

BFS on a graph with n vertices and m edges takes O(n + m ) time BFS can be further extended to solve other graph problems „

Breadth-First Search

D

L1

F 5

F

L0 C

E

5/7/2002 11:06 AM

D

L1

Breadth-First Search

C E

D F

A

B

L2

F

A

B

L2

A

B

L2

D

L1

C E

D F 6

1

Breadth-First Search

5/7/2002 11:06 AM

Example (cont.) L0 L1

A

B

L2

C

Notation

A

B

C

L2

F

D

E

F

Property 3 C

E

„

„

F Breadth-First Search

7

once as UNEXPLORED once as VISITED

„

once as UNEXPLORED once as DISCOVERY or CROSS

Recall that

„ „

„

Σv deg(v) = 2m

5/7/2002 11:06 AM

Breadth-First Search

9

DFS vs. BFS Applications

DFS

BFS

√

√

Shortest paths

B

C

L2

D

E

F

Breadth-First Search

8

L0

E

Breadth-First Search

10

Back edge (v,w) „

D

Cross edge (v,w)

w is an ancestor of v in the tree of discovery edges

„

w is in the same level as v or in the next level in the tree of discovery edges

√

A C

Compute the connected components of G Compute a spanning forest of G Find a simple cycle in G, or report that G is a forest Given two vertices of G, find a path in G between them with the minimum number of edges, or report that no such path exists

5/7/2002 11:06 AM

√

Biconnected components

L1

C E

B

D

C E

F

D

L1

F

11

5/7/2002 11:06 AM

A

B

L2

DFS

BFS Breadth-First Search

L0

A

A

B

L2

F

DFS 5/7/2002 11:06 AM

A

DFS vs. BFS (cont.)

Spanning forest, connected components, paths, cycles

B

F

Using the template method pattern, we can specialize the BFS traversal of a graph G to solve the following problems in O(n + m) time

Each vertex is inserted once into a sequence Li Method incidentEdges is called once for each vertex BFS runs in O(n + m) time provided the graph is represented by the adjacency list structure „

L0

The path of Ts from s to v has i edges Every path from s to v in Gs has at least i edges

5/7/2002 11:06 AM

D

Applications

Each edge is labeled twice „

C E

L1

For each vertex v in Li

D

Setting/getting a vertex/edge label takes O(1) time Each vertex is labeled twice

„

B

BFS(G, s) visits all the vertices and edges of Gs

Property 2

Analysis

„

Property 1

The discovery edges labeled by BFS(G, s) form a spanning tree Ts of Gs

5/7/2002 11:06 AM

„

A

Gs: connected component of s

A

B

L2

L1

D

E

L0 L1

Properties L0

C E

D F

BFS Breadth-First Search

12

2