Nice blog post about “Social network connectivity” problem that appears in Coursera Algorithms I (https://class.coursera.org/algs4partI-009)

一只软件工程师的日常

Q: Given a social network containing N members and a log file containing M timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend … of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be MlogN or better and use extra space proportional to N.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

When solving dynamic connectivity problems (like whether there is a path between two nodes but we don’t care what the exact path is), we can try using the Union-Find algorithm. And this is a typical application of union-find in social network.

This question asks if we can determine the earliest time at which all…

View original post 391 more words

Advertisements

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