有人问我一个问题,如何在社交网络中找到“发布者”。假设(简化的)社交网络在两个用户之间仅具有“跟随”关系,而一个用户无法跟随自己。然后,我们将“发布者”定义为所有其他用户都关注但没有关注任何人的用户。
更具体地说,给定这种具有邻接矩阵格式的社交网络图,例如NxN bool矩阵,其中cell [i,j]指示用户i是否跟随用户j。如何查找发布者。
我看到的是最多可以存在一个发布者(很容易证明:由于发布者被其他所有人关注,因此其他所有人都至少关注一个用户,因此他们不是发布者)。我确实提出了一个幼稚的解决方案:首先逐列扫描,如果有一个全为true的j列(当然,cell [j,j]除外),然后扫描row [j]以确保全为false。
显然,天真算法的性能为O(n ^ 2),因为我们扫描了整个矩阵。但是,有人告诉我有一个O(n)解决方案。我有点被O(n)困住了。有什么提示吗?
如果您的数据显示为邻接矩阵,则可以按以下步骤进行。首先检查矩阵中的条目(1,2)。如果1跟随2,则1不是发布者,如果1不跟随2,则2不是发布者。删除不是发布者的任何人(1或2),并让X为其余节点。然后检查矩阵中的条目(X,3)。同样,您将获得X不是发布者或3不是发布者。删除不是发布者的任何人,然后添加节点4并重复。在所有n个节点上重复此过程之后,将剩下一个发布者候选者。然后,您可以检查候选人的行和列,以确认它是真正的发布者。即使邻接矩阵的大小为n ^ 2,整个算法的总运行时间为O(n)。