Breadth first search & depth first search

This post is based on Chapter 22, <<Introduction to Algorithms>>, Third Edition.

BFS(G,s):
    for each vertex u in G.V - {s}:
        u.color = white
        u.d = infinity
        u.previous = NIL
    s.color = gray
    s.d = 0
    s.previous = NIL
    Q = a new queue
    ENQUEUE(Q,s)
    while Q is not empty:
        u = DEQUEUE(Q)
        for each v in G.Adj[u]:
            if v.color == white:
                v.color = gray
                v.d = u.d + 1
                v.previous = u
                ENQUEUE(Q,v)
    u.color = black
  • Running time of BFS: O(V+E)
  • print out the path from s to v
Print-path(G,s,v):
    if v==s:
        print s
    else if v.previous == NIL:
        print &quot;no path from s to v exists&quot;
    else:
        Print-path(G,s,v.previous)
        print v

 

  • DFS
DFS(G,s):
    for each vertex u in G.V:
        u.color = white
        u.previous = NIL
    time = 0
    for each vertex u in G.V: //ensure that all of the vertices are visited
        if u.color == white:
            DFS-VISIT(G,u)

DFS-VISIT(G,u):
    time = time + 1 //every time we update the time attribute of a node, we increment it by 1
    u.d = time
    u.color = gray
    for each v in G.Adj[u]:
        if v.color == white:
            v.previous = u
            DFS-VISIT(G,v) // Note the use of recursion in DFS; or we can use a stack to implement DFS-VISIT
    u.color = black
    time = time + 1 //every time we update the time attribute of a node, we increment it by 1
    u.f = time
  • Running time: O(V+E)

 

Parenthesis theorem: in any directed or undirected graph G(V, E) that has been DFS visited, any pair of vertices u and v satisfy that:

  • [u.d, u.f] and [v.d, v.f] do not overlap at all
  • one time frame of [u.d, u.f] and [v.d, v.f] is completed included in the other time frame

White-path theorem: In a directed or undirected graph G = (V, E)’s depth-first forests, vertice v is the cild of u if and only if there exists a path that is composed of all white vertices when u is just discovered.

Classification of edges of DFS:

  • tree edge: the edge in the depth-first forest.
  • backward edge: the edge that connects u to its “previous” vertice v. (Acyclic graph has no backward edges)
  • forward edge: the edge that connects u to its child vertice v.
  • cross edge: other edges. Can be an edge that connects two vertices in one depth-first tree or the one that connects two vertices in two different depth-first trees

During the process of DFS, for the edge (u,v):

  • if v is white, then (u,v) is a tree edge
  • if v is gray, then (u,v) is a backward edge
  • if v is black, then (u,v) is a forward edge or cross edge

Theorem: during the DFS in a undirected graph G, there can only exist tree edges and backward edges.
Topological Sort: only for directed acyclic graph

TOPOLOGICAL-SORT(G):
    call DFS(G) to compute finishing time v.f for each vertex v
    as each vertex is finished, insert it onto the front of a linked list
    return the linked list of vertices

 

Strongly connected component: see chapter 23 of the book

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s