我被问到如何在社交网络中找到"发布者"的问题.假设(简化的)社交网络仅在两个用户之间具有"跟随"关系,并且一个人不能跟随他自己.然后我们将"发布者"定义为所有其他用户都遵循但不跟随任何人的用户.
更具体地,给定这种邻接矩阵格式的社交网络图,例如NxN布尔矩阵,其中cell [i,j]指示用户i是否跟随用户j.如何找出出版商.
我可以看到,最多只有一个发布者可以存在.(很容易证明:由于发布者后面跟着其他人,所以其他人都至少跟踪一个用户,所以他们不是发布者).我想出了一个天真的解决方案:首先逐列扫描,如果有一个全真列j(当然除了单元格[j,j]),则扫描行[j]以确保它全部为假.
显然,对于朴素算法,性能是O(n ^ 2),因为我们扫描整个矩阵.但是,我被告知有一个O(n)解决方案.我有点困在O(n).任何提示？
use*_*092 10
如果您的数据显示为邻接矩阵,则可以按以下步骤操作.首先检查矩阵中的条目(1,2).如果1跟随2,那么1不是发布者,如果1不跟随2,那么2不是发布者.删除不是发布者(1或2)的任何人,让X成为剩余的节点.然后检查矩阵中的条目(X,3).同样地,您将得到X不是发布者或3不是发布者.删除不是发布者的人,然后添加节点4并重复.在您使用所有n个节点重复此过程后,您将留下一个候选人用于发布者.然后,您可以检查候选人的行和列,以验证它是否是真正的发布者.即使邻接矩阵的大小为n ^ 2,整个算法的总运行时间也是O(n).