Graph Search and Connectivity

GRAPH CONNECTIVITY.

The goal of Searching in a graph: O(m+n) time.

Generic Search Algorithm (Given graph G, initial vertex S){
Initially, S explored, all other vertexes unexplored.
While possible:
   Choose an edge(u,v) with one explored and one unexplored.
   Mark the new vertex explored.

BFS: (Explores nodes in layers, Uses Queue)

• Can compute shortest paths.
• Can compute connected components of an undirected graph.

DFS:(Explores aggressively, uses stack)

• Compute topological ordering or a directed acyclic graph.
• Can compute connected components of a directed graph.

BFS:(Graph G, start vertex S):
      Mark S explored.
      Q= queue, initialized with S.
      While(Q!=null):
         Remove the first node of Q, call it v.   
         For each edge(v,w):
            Mark w explored; add to Queue

 

COMPUTE SHORTEST PATH:

Use BFS only, add extra code:
Initialize dist(V) : 0 if V==s, infinite if V!=S.
When considering edge (v,w) : if W is unexplored, dist(w) = dist(v) +1;

 

UNDIRECTED CONNECTIVITY:

To compute all components:
   All nodes unexplored.
   for i =1 to n (n number of nodes):
      if (i not explored): BFS(G,i);

Running Time : O(m+n).

----------------------------------------------------------------------------------------------------

DFS Algo:
mimics BFS, uses a stack; Can do the whole thing recursively too. Try it out.

DFS(Graph G , vertex S):
   Mark S explored.
   For every edge (S,v):
      if V unepxlored:
         DFS(G,v).

%f(v) = current_label--;% (F   rom topological sort)

 

------------------------------------------------------------------------------------------------------------

Topological Ordering:
   Let V be the sink vertex of graph G.
   F(V) = n.
   Delete that node and recurse on G-{v}

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

• F(v) belongs to the set of vertexes.
• (u,v) -> f(u)

If G is cyclic, there can be no topological sort.

Every directed acyclic graph has a sink vertex.

DFS_LOOP(GRAPH G):
   mark all nodes unexplored.
   current_label = n,
   for each vertex v in G:
      if v is not explored:
         DFS(G,v).

---------------------------------------------------------------------------------------------------------

STRONGLY CONNECTED COMPONENTS:

A graph is strongly connected if you can get from any one point to any other point.
Problem: We can get an SCC only if we start from the right node.

 

KOSARAJU'S TWO PASS ALGORITHM:

1) Reverse all the paths of the graph. Represented by G^(rev).
2) Run DFS-LOOP n the reverse graph from the highest node to the lowest. (It will compute a magical ordering of nodes).
      -Let f(v) be the finishing time of each vertex.

3) Run DFS-LOOP on the original graph. (Once it goes through the magical prdering, it will reveal the SCC's one by one).
      -SCC's - All nodes which have the same leader.

DFS Loop(Graph G):
   global variable t = 0 (# of nodes so far) (For first pass).
   global variable s = NULL (most recent source vertex) (For second pass).
   Assume nodes labelled 1 to n.
   for i =1 to n:
      if i unexplored:
         S:=i;
         DFS(G,i);

DFS(Graph G, vertex i):
   mark i as explored.
   set leader(i) = s; //second pass
   for (each arc(i,j)):
      if j unexplored.
      DFS(G,j);

   t++;   //first pass
   set (f(i) = t;   //first pass

 

• SCC's can have complex structures but if we zoom out and treat every SCC as a single node, they have a simple directed acyclic graph.
• If SCC1 has an outer edge to SCC2, then max F(SCC2) > max F(SCC1).
• Leader is the same as the highest finishing time for that SCC.

--------------------------------------------------------------------------------------------------------------------------------------------------------------------

STRUCTURE OF THE WEB (OPTIONAL):

Vertices: Web Pages
Directed edges: Hyperlinks