Have you ever thought how Facebook suggests you groups to join or pages to like or even "people you may know" . If not then have a look here. In fact Facebook uses graph to represent people. You can visit http://graph.facebook.com/vikashvverma to have a look how each individual is represented on Facebook. This is the beautiful application of Graph on social networking sites. Let us hve a look on the same.
A graph is said to be strongly connected if there is a path from each vertex to every other vertex i.e if u and v are two vertices then there is a path from u to v and also from v to u. One of the algorithm to compute the strongly connected components of a graph is due to Kosaraju ; a bachelor of engineering from Andhra University, masters from IIT Kharagpur and PhD from University of Pennsylvania. He used Depth First Search of Graph to find strongly connected components of the graph in O(m+n) time.The strongly connected component of a graph is shown below (The vertices inside the colored part shows strongly connected components ) :
Algorithm :
1) G is a directed graph and S is a stack.
2) While S does not contain all vertices perform step 3.
3)choose a random vertex v and perform depth first search on it. Each time DFS finishes expanding vertex v, push v on to the stack S. (This guarantees that the vertex with maximum finish time will more closer to the top of the stack).
4) Obtain a transpose of the G by reversing the direction of the edge.
5)While S is not empty perform step 6.
6) Remove v=top of S and again perform DFS on it The set of all visited vertices will give the strongly connected components containing v. Remove all visited vertices from stack.
Read full article from Geek: Kosaraju's Algorithm to Find Strongly Connected Components
No comments:
Post a Comment