Breadth-First Search (BFS) Algorithm for Graph Searching

Graph Searching

Algorithms

Tree

Breadth-First Search (BFS)

Breadth-First Search (BFS)

u

x

v

y

z

w

Not

discovered

Discovered,

adjacent

white nodes

Discovered,

no adjacent

white nodes

Breadth-First Search (BFS)

u

x

v

y

z

w

BFS(G, u):

  1. Initialize the graph

    color[u] 



 gray

    π[u] 



 Nil

    d[u] 



 0

    for each other vertex

      color[u] 



 white

Breadth-First Search (BFS)

u

x

v

y

z

w

Q

BFS(G, u):

  2. Initialize the queue

    Q 



 Ø

    Enqueue(Q, u)

Breadth-First Search (BFS)

Q

BFS(G, u):

  3. While Q ≠ Ø

    1) t 



 Dequeue(Q)

u

x

v

y

z

w

t = u

Breadth-First Search (BFS)

u

x

v

y

z

w

Q

BFS(G, u):

  3. While Q ≠ Ø

    2) for each r adj to t

      if color[r] = white

        color[r] 



 gray

        π[r] 



 t

        d[r] 



 d[t] + 1

        Enqueue(Q, r)

t = u

r = x, v

Breadth-First Search (BFS)

u

x

v

y

z

w

Q

BFS(G, u):

  3. While Q ≠ Ø

    3) color[t] 



 black

t = u

r = x, v

Breadth-First Search (BFS)

u

x

v

y

z

w

Q

BFS(G, u):

  3. While Q ≠ Ø

    1) t 



 Dequeue(Q)

    2) for each r adj to t

        …

    3) color[t] 



 black

t = v

Breadth-First Search (BFS)

u

x

v

y

z

w

Q

BFS(G, u):

  3. While Q ≠ Ø

    1) t 



 Dequeue(Q)

    2) for each r adj to t

        …

    3) color[t] 



 black

t = v

r = y

Breadth-First Search (BFS)

u

x

v

y

z

w

Q

BFS(G, u):

  3. While Q ≠ Ø

    1) t 



 Dequeue(Q)

    2) for each r adj to t

        …

    3) color[t] 



 black

t = v

r = y

Breadth-First Search (BFS)

u

x

v

y

z

w

Q

BFS(G, u):

  3. While Q ≠ Ø

    1) t 



 Dequeue(Q)

    2) for each r adj to t

        …

    3) color[t] 



 black

t = x

r =

Breadth-First Search (BFS)

u

x

v

y

z

w

Q

BFS(G, u):

  3. While Q ≠ Ø

    1) t 



 Dequeue(Q)

    2) for each r adj to t

        …

    3) color[t] 



 black

t = y

r = w

Breadth-First Search (BFS)

u

x

v

y

z

w

Q

BFS(G, u):

  3. While Q ≠ Ø

    1) t 



 Dequeue(Q)

    2) for each r adj to t

        …

    3) color[t] 



 black

t = w

r = z

Breadth-First Search (BFS)

u

x

v

y

z

w

Q

BFS(G, u):

  3. While Q ≠ Ø

    1) t 



 Dequeue(Q)

    2) for each r adj to t

        …

    3) color[t] 



 black

t = z

r =

Breadth-First Search (BFS)

u

x

v

y

z

w

BFS(G, u):

  - the shortest-path distance

    from u

Breadth-First Search (BFS)

u

x

v

y

z

w

BFS(G, u):

  - the shortest-path distance

    from u

  - construct a tree

Breadth-First Search (BFS)

u

x

v

y

z

w

BFS(G, u):

  - Initialization: |V|

  - Enqueuing/dequeuing:

    |V|

  - Scanning adj vertices: |E|

Breadth-First Search (BFS)

u

x

v

y

z

w

BFS(G, u):

  - Initialization: O(|V|)

  - Enqueuing/dequeuing:

    O(|V|)

  - Scanning adjacent vertices:

    O(|E|)

  => total running time:

        O(|V| + |E|)

Depth-First Search (DFS)

Depth-First Search (DFS)

u

d[u]: when u is discovered

f[u]: when searching adj of u

         is finished

v

w

Depth-First Search (DFS)

u

d[u]: when u is discovered

f[u]: when searching adj of u

         is finished

timestamp: t

d[u] = t

v

w

Depth-First Search (DFS)

u

d[u]: when u is discovered

f[u]: when searching adj of u

         is finished

timestamp: t+1

d[u] = t

v

w

d[v] = t+1

Depth-First Search (DFS)

u

d[u]: when u is discovered

f[u]: when searching adj of u

         is finished

timestamp: t+2

d[u] = t

v

w

d[v] = t+1

f[v] = t+2

Depth-First Search (DFS)

u

d[u]: when u is discovered

f[u]: when searching adj of u

         is finished

timestamp: t+3

d[u] = t

v

w

d[v] = t+1

f[v] = t+2

d[w] = t+3

Depth-First Search (DFS)

u

d[u]: when u is discovered

f[u]: when searching adj of u

         is finished

timestamp: t+4

d[u] = t

v

w

d[v] = t+1

f[v] = t+2

d[w] = t+3

f[v] = t+4

Depth-First Search (DFS)

u

d[u]: when u is discovered

f[u]: when searching adj of u

         is finished

timestamp: t+5

d[u] = t

f[u] = t+5

v

w

d[v] = t+1

f[v] = t+2

d[w] = t+3

f[w] = t+4

Depth-First Search (DFS)

u

d[u]: when u is discovered

f[u]: when searching adj of u

         is finished

d[u] = t

f[u] = t+5

v

w

d[v] = t+1

f[v] = t+2

d[w] = t+3

f[w] = t+4

1.

d[u] < f[u]

2.

[ d[u], f[u] ] entirely contains

[ d[v], f[v] ]

3.

[ d[v], f[v] ] and [ d[w], f[w] ]

are entirely disjoint

Depth-First Search (DFS)

u

x

v

y

z

w

Not

discovered

Discovered,

adjacent

white nodes

Discovered,

no adjacent

white nodes

Depth-First Search (DFS)

u

x

v

y

z

w

Not

discovered

Discovered,

adjacent

white nodes

Discovered,

no adjacent

white nodes

Depth-First Search (DFS)

u

x

v

y

z

w

DFS(G):

  1. Initialization

    for each u    V[G],

      color[u] 



 white

      π[u] 



 Nil

    time 



 0

Depth-First Search (DFS)

DFS(G):

  1. Initialization

  2. For each u    V[G]

    if color[u] = white

      DFS-Visit(u)

DFS-Visit(u):

  1. Initial Setting

    color[u] 



 gray

    d[u] 



 time 



 time + 1

u

x

v

y

z

w

Depth-First Search (DFS)

DFS(G):

  1. Initialization

  2. For each u    V[G]

    if color[u] = white

      DFS-Visit(u)

DFS-Visit(u):

  1. Initial Setting

  2. for each adj v of white

        π[v] 



 u

       DFS-Visit[v]

u

x

v

y

z

w

Depth-First Search (DFS)

DFS(G):

  1. Initialization

  2. For each u    V[G]

    if color[u] = white

      DFS-Visit(u)

DFS-Visit(u):

  1. Initial Setting

  2. for each adj v of white

        π[v] 



 u

       DFS-Visit[v]

u

x

v

y

z

w

Depth-First Search (DFS)

DFS(G):

  1. Initialization

  2. For each u    V[G]

    if color[u] = white

      DFS-Visit(u)

DFS-Visit(u):

  1. Initial Setting

  2. for each adj v of white

        π[v] 



 u

       DFS-Visit[v]

u

x

v

y

z

w

Depth-First Search (DFS)

DFS(G):

  1. Initialization

  2. For each u    V[G]

    if color[u] = white

      DFS-Visit(u)

DFS-Visit(u):

  1. Initial Setting

  2. Handling adj vertices

  3. color[u] 



 black

    f[u] 



 time 



 time + 1

u

x

v

y

z

w

Depth-First Search (DFS)

DFS(G):

  1. Initialization

  2. For each u    V[G]

    if color[u] = white

      DFS-Visit(u)

DFS-Visit(u):

  1. Initial Setting

  2. Handling adj vertices

  3. color[u] 



 black

    f[u] 



 time 



 time + 1

u

x

v

y

z

w

Depth-First Search (DFS)

DFS(G):

  1. Initialization

  2. For each u    V[G]

    if color[u] = white

      DFS-Visit(u)

DFS-Visit(u):

  1. Initial Setting

  2. Handling adj vertices

  3. color[u] 



 black

    f[u] 



 time 



 time + 1

u

x

v

y

z

w

Depth-First Search (DFS)

DFS(G):

  1. Initialization

  2. For each u    V[G]

    if color[u] = white

      DFS-Visit(u)

DFS-Visit(u):

  1. Initial Setting

  2. Handling adj vertices

  3. color[u] 



 black

    f[u] 



 time 



 time + 1

u

x

v

y

z

w

Depth-First Search (DFS)

DFS(G):

  1. Initialization

  2. For each u    V[G]

    if color[u] = white

      DFS-Visit(u)

DFS-Visit(u):

  1. Initial Setting

  2. Handling adj vertices

  3. color[u] 



 black

    f[u] 



 time 



 time + 1

u

x

v

y

z

w

Depth-First Search (DFS)

DFS(G):

  1. Initialization

  2. For each u    V[G]

    if color[u] = white

      DFS-Visit(u)

DFS-Visit(u):

  1. Initial Setting

  2. Handling adj vertices

  3. color[u] 



 black

    f[u] 



 time 



 time + 1

u

x

v

y

z

w

Depth-First Search (DFS)

DFS(G):

  1. Initialization

  2. For each u    V[G]

    if color[u] = white

      DFS-Visit(u)

DFS-Visit(u):

  1. Initial Setting

  2. Handling adj vertices

  3. color[u] 



 black

    f[u] 



 time 



 time + 1

u

x

v

y

z

w

Depth-First Search (DFS)

DFS(G):

  1. Initialization

  2. For each u    V[G]

    if color[u] = white

      DFS-Visit(u)

DFS-Visit(u):

  1. Initial Setting

  2. Handling adj vertices

  3. color[u] 



 black

    f[u] 



 time 



 time + 1

u

x

v

y

z

w

Depth-First Search (DFS)

DFS(G):

  - construct a forest

u

x

v

y

z

w

Depth-First Search (DFS)

u

x

v

y

z

w

DFS(G):

  - Initialization: O(|V|)

  - Traversing vertices: O(|V|)

  - Scanning adjacent vertices:

    O(|E|)

  => total running time:

        O(|V| + |E|)

Topological Sorting

Topological Sorting

Brute-Force way

  1. Find a vertex

      without edges.

  2. Put it onto the front

      of the list, and

      remove it from G.

  3.  Remove all edges

       to the removed edge.

  4. Repeat 1~3.

O(|V|

2

 + |V||E|)

Or

O(|V|

2

)

Topological Sorting

Using DFS

  1. Call DFS(G)

  2. When a vertex is

      finished, put it onto

      the front of the list.

O(|V| + |E|)

Topological Sorting

Using DFS

  1. Call DFS(G)

  2. When a vertex is

      finished, put it onto

      the front of the list.

1) v is white:  d[u] < d[v] < f[u]

2) v is black:  f[v] < d[u]

3) v is gray:  d[v] < d[u] < f[v]

At d[u]:

v enters the

list before u?

Topological Sorting

Using DFS

  1. Call DFS(G)

  2. When a vertex is

      finished, put it onto

      the front of the list.

1) v is white:  d[u] < d[v]

At d[u]:

v enters the

list before u?

t is gray:  d[t] < d[u] < f[t]

t is black: f[t] < d[u]

Topological Sorting

1.

If v is a descendant,

      d[u] < d[v] < f[v] < f[u]

2.

If v is an anscestor,

      d[v] < d[u] < f[u] < f[v]

3.

Otherwise,

      d[v] < f[v] < d[u] < f[u]

      or

      d[u] < f[u] < d[v] < f[v]

u

v

w

Depth-First Search (DFS)

u

v

w

1.

d[u] < f[u]

2.

[ d[u], f[u] ] entirely contains

[ d[v], f[v] ]

3.

[ d[v], f[v] ] and [ d[w], f[w] ]

are entirely disjoint

In a depth-first forest,

  v is a descendant of u

    if and only if

      d[u] < d[v] < f[v] < f[u]

Topological Sorting

1.

If v is a descendant,

      d[u] < d[v] < f[v] < f[u]

2.

If v is an anscestor,

      d[v] < d[u] < f[u] < f[v]

3.

Otherwise,

      d[v] < f[v] < d[u] < f[u] or d[u] < f[u] < d[v] < f[v]

At d[u]:

1) v is white:  d[u] < d[v]

t is gray:  d[t] < d[u] < f[t]

t is black: f[t] < d[u]

Contradiction:

G is not acyclic.

Topological Sorting

1.

If v is a descendant,

      d[u] < d[v] < f[v] < f[u]

2.

If v is an anscestor,

      d[v] < d[u] < f[u] < f[v]

3.

Otherwise,

      d[v] < f[v] < d[u] < f[u] or d[u] < f[u] < d[v] < f[v]

At d[u]:

1) v is white:  d[u] < d[v]

t is gray:  d[t] < d[u] < f[t]

t is black: f[t] < d[u]

Contradiction:

v should be black.

Topological Sorting

1.

If v is a descendant,

      d[u] < d[v] < f[v] < f[u]

2.

If v is an anscestor,

      d[v] < d[u] < f[u] < f[v]

3.

Otherwise,

      d[v] < f[v] < d[u] < f[u] or d[u] < f[u] < d[v] < f[v]

At d[u]:

1) v is white:  d[u] < d[v]

t is white.

Topological Sorting

1.

If v is a descendant,

      d[u] < d[v] < f[v] < f[u]

2.

If v is an anscestor,

      d[v] < d[u] < f[u] < f[v]

3.

Otherwise,

      d[v] < f[v] < d[u] < f[u] or d[u] < f[u] < d[v] < f[v]

At d[u]:

1) v is white:  d[u] < d[v] < f[u]

t is white.

Topological Sorting

1.

If v is a descendant,

      d[u] < d[v] < f[v] < f[u]

2.

If v is an anscestor,

      d[v] < d[u] < f[u] < f[v]

3.

Otherwise,

      d[v] < f[v] < d[u] < f[u] or d[u] < f[u] < d[v] < f[v]

1) v is white:  d[u] < d[v] < f[u]

2) v is black:  f[v] < d[u]

3) v is gray:  d[v] < d[u] < f[v]

At d[u]:

v will enter the

list before u.

Topological Sorting

1.

If v is a descendant,

      d[u] < d[v] < f[v] < f[u]

2.

If v is an anscestor,

      d[v] < d[u] < f[u] < f[v]

3.

Otherwise,

      d[v] < f[v] < d[u] < f[u] or d[u] < f[u] < d[v] < f[v]

1) v is white:  d[u] < d[v] < f[u]

2) v is black:  f[v] < d[u]

3) v is gray:  d[v] < d[u] < f[v]

At d[u]:

v is already in

the list.

Topological Sorting

1.

If v is a descendant,

      d[u] < d[v] < f[v] < f[u]

2.

If v is an anscestor,

      d[v] < d[u] < f[u] < f[v]

3.

Otherwise,

      d[v] < f[v] < d[u] < f[u] or d[u] < f[u] < d[v] < f[v]

1) v is white:  d[u] < d[v] < f[u]

2) v is black:  f[v] < d[u]

3) v is gray:  d[v] < d[u] < f[v]

At d[u]:

Contradiction:

G is not acyclic.

Strongly Connected Component

Strongly Connected Component

Strongly Connected Component

Strongly Connected Component

1.

Call DFS(G)

2.

Arrange the vertices

     in order of decreasing f(u)

1

2

3

4

5

8

9

6

7

Strongly Connected Component

1.

Call DFS(G)

2.

Arrange the vertices

     in order of decreasing f(u)

3.

Compute G

T

1

2

3

4

5

8

9

6

7

Strongly Connected Component

1.

Call DFS(G)

2.

Arrange the vertices

     in order of decreasing f(u)

3.

Compute G

T

4.

Run DFS(G

T

)

1

2

3

4

5

8

9

6

7

Strongly Connected Component

1.

Call DFS(G)

2.

Arrange the vertices

     in order of decreasing f(u)

3.

Compute G

T

4.

Run DFS(G

T

)

1

2

3

4

5

8

9

6

7

Topological Sorting

Strongly Connected Component

Strongly Connected Component

Last f[u]

Last f[u]

>

Strongly Connected Component

1.

Call DFS(G)

2.

Arrange the vertices

     in order of decreasing f(u)

1

2

3

4

5

8

9

6

7

Strongly Connected Component

4

3

1

2

Strongly Connected Component

4

3

1

2

Adjacency Matrix of Graphs

Directed graph

Adjacency-Matrix

1      2     3      4      5

5

3

4

2

1

Adjacency Matrix of Graphs

A =

A

T

 =