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