Introduction to Graph Search

1.  A few motivations for Graph Search:

    a)  check if a network is connected ( can get to anywhere from anywhere else)

    b)  driving direction

    c)  formulate a plan ( the nodes are the steps and arcs are the choose of the step sequences)

    d)  compute the "pieces" or "components" of a graph

 

2.  Generic Graph Search:

    Goals: a)  find everything findable from a given start vertex

               b)  don't explore anything twice

    Algorithm: Given Graph G , vertex s :

    a)  initially s is explored and all the other vertices are unexplored

    b)  while possible :

        --  choose an edge (u, v) with u explored and v unexplored

        --  mark v explored

 

3.  Claim : at then end of Generic Graph Search, v is explored <==> G has a path from s to v.

     Proof : (==>) by induction on number of iterations

                (<==)  by contradiction: if G has path from s to v and v is unexplored, there must be an edge (u, w) in the path , that u is explored and w is unexplored, in that case, the algorithm should not terminate.

 

4.  BFS V.S. DFS: how to choose among the possible many "frontier" edges.

    Breadth-FIrst-Search :

    --  explore nodes in "layers"

    --  can compute "shortest path"

    --  can compute connected components of an undirected graph

    Depth-First-Search:

    --  explored aggressively like a maze, backtrack only when necessary.

    --  can compute topological ordering of directed acyclic graph

    --  can compute connected components of a directed graph

 

5.  Breadth-First-Search Implementation:BFS(Graph G, start vertex s)

    a)  all nodes initially unexplored

    b)  mark s as explored

    c)  let Q = queue data structure (FIFO) , initialized with s

    d)  while Q is not empty :

        --  remove the first node of Q , call it v

        --  for each edge (v, w)

                 --  if w is unexplored, mark w as explored and add w to Q at end

    Running Time is  O ( m + n)

 

6.  Application of BFS : Shortest Path:

    Goal : compute dist(v) , the fewest number of edges on a path from s to v.

    Extra code than BFS :

       a)  initialize dist(v) = 0 if v=s or plus inifitive if v != s

       b)  when considering an edge (v,w) :

               if w is unexplored , then set dist(w) = dist(v) + 1

    Claim : at termination , dist(v) = i <==> v in ith layer <==> shortest s-v path has i edges

    Proof : every node w in layer i is added to Q by a node v in layer i - 1 via the edge (v, w)

 

7.  Application of BFS : Undirected Connectivity:

    Let G = (V, E) be an undirected graph.

    Equivalent relation u ~ v <==> there is a path from u to v.

    Definition of connected components: equivalence classes of relation ~

    Application : check if network is disconnected, graph visualization ( clustering)

    Algorithm to compute all connected components of an undirected graph:

    a)  initally all nodes unexplored

    b)  for i = 1 to n :

            -- if node i not yet explored , BFS( G, i )

    Running time:  O (m + n)

 

8.  Non-Recursive implementation of DFS(Graph G, start vertex s)

    a)  all nodes initially unexplored

    b)  mark s as explored

    c)  let Stack = stack data structure (FILO) , initialized with s

    d)  while Stack is not empty :

        --  remove the last node of Stack , call it v

        --  for the next edge (v, w) that is not explored through v

                 --  if w is unexplored, mark w as explored and add v to Stack at end

    Running Time is  O ( m + n)

 

9. Recursive implementation of DFS(Graph G, start vertex s):

    -- initially all nodes unexplored

    -- mark s as explroed

    -- for every edge (s, v) :

             --  if v unexplored : DFS(G, v)

 

10. Application of DFS : Topological Sort :

    Definition : A topological ordering of a directed graph G is a labelling f of G's nodes such that :

    a)  for different v , f(v) is different and f(v) is in {1, 2, .., n}

    b)  If there is an edge (u, v)  in G => f(u) < f(v)

    Motivation : Sequence tasks while respecting all precedence constraints.

    Claim : G has directed cycle => no topological ordering.

                no directed cycle => can compute topological ordering in O( m + n ) time.

 

11. Claim : Every directed acyclic graph has a sink vertex ( vertex that doesn't has outgoing arcs)

      Proof : if not can keep following outgoing arcs to produce a path that has more than n-1 arcs, then it must contain duplicated vertex.

 

12. To compute topological ordering :

    --  Let v be a sink vertex of G

    --  Set f(v) = n

    --  recurse on  G-{v}   // A DAG removing a vertex is still a DAG

 

13. Topological Sort via DFS:

      DFS-Loop ( graph G ) :

      --  mark all nodes unexplored.

      --  current-label = n

      --  for each vertex v in G

           -- if v not yet explored ,  DFS (G, v)

 

      DFS (G, s)

      -- mark s as explroed

      -- for every edge (s, v) :

             --  if v unexplored : DFS(G, v)

      -- label s as current-label

      -- current-label --

 

14. Proof of correctness of DFS for computing topological ordering:

      Goal : need to show that if ( u, v ) is an edge in G, then f(u) < f(v);

      case 1: if u is explored before v => recursive call on v finishes before that on u, so f(u) < f(v)

      case 2: if u isexplored after v => because there is no cycle in the graph , so there is not path from v to u, so after v finish the recursive call , u is still not explored so , f(u) < f(v)

 

15. The strong connected components (scc) of a directed graph G are the equivalence classes of the relation ~ :

       u ~ v <==> there is a path from u to v and a path from v to u.

 

16. Kosaraju’s Two-Pass Algorithm for computing SCC:

    a) Let G(rev) = G with all arcs reversed

    b)  run DFS-Loop on G(rev), Let f(v) = "finishing time" of each v in G

       (Goal : compute magical ordering of notes. )

    c)  run DFS-Loop on G , proccessing nodes in decreasing order of finishing times

       (Goal : discover the SCCs one by one , SCCs = nodes with the same "leader" )

   

    DFS-Loop ( graph G ) :

      --  mark all nodes unexplored.

      --  global variable t = 0 // # of nodes finished so far, for finishing time in 1st DFS loop

      --  global variable l = NULL // current source vertex , for leaders in 2nd DFS loop

      --  for i = n downto 1

             -- v = ith node in G

             -- if v not yet explored ,  l = v , DFS (G, v)

 

      DFS (G, s)

      -- mark s as explroed

      -- for every edge (s, v) :

             --  if v unexplored : DFS(G, v)

      -- f(s) = ++ t

      -- leader(s) = l

 

17. SCC in G and G(rev) are exactly the same.

 

18. Claim: Consider two ajacent SCCs in G, if there is a path from SCC1 to SCC2 ( no path from SCC2 to SCC1 , otherwise they are in the same SCC), Let f(v) = finishing times of DFS-Loop in G(rev), then:

                max ( v in SCC1){f(v)}  < max (v in SCC2) {f(v)}

 

      Proof: Let v = 1st node of SCC1 U SCC2 explored by 1st pass of DFS-Loop ( on G(rev) ).

      Case 1 : v is in SCC1, in G(rev) no path from SCC1 to SCC2, so all nodes in SCC1 get explored before nodes in SCC2. So finishing times of nodes SCC2 are greater than all those in SCC1.      Case 2 : v is in SCC2, there is a path from SCC2 to SCC1 in G(rev) , so DFS on v won't finish untill all nodes in SCC1 U SCC2 are explored. so f(v) has the greater finishing time.

 

19.  Correctness of DFS for computing SCC :

        a) max value of f(v) in G must lie in a "Sink SCC" SCC*

        b) First call to DFS of 2nd pass DFS-Loop on G discoveres SCC*

        c) rest of DFS-Loop on G like recursing on G with SCC* deleted.

        d) successive calls to DFS "peal off" the SCCs one by one.(in the reverse topological order of "meta-Graph")

 

20.  The Web Graph:

      a)  vertices = web pages

      b)  directed edges = hyperlinks

      c)  the graph forms a Bow Tie :

     Main Findings:

    a)  all 4 parts have roughly the same size

    b)  within core , very well connected

    c)  outside, surprisingly poorly connected