有人问我如何在社交网络中找到“发布者”的问题。假设（简化的）社交网络仅在两个用户之间具有“关注”关系，并且一个用户不能关注自己。然后，我们将“发布者”定义为被所有其他用户关注但不关注任何人的用户。
更具体地说，给定这样一个邻接矩阵格式的社交网络图，比如 NxN 布尔矩阵，其中 cell[i,j] 指示用户 i 是否关注用户 j。如何找到出版商。
我所看到的是，最多可以存在一个发布者。（很容易证明：因为发布者被其他人关注，那么其他人至少关注一个用户，所以他们不是发布者）。我确实想出了一个天真的解决方案：首先逐列扫描，如果有全真列 j （当然除了单元格 [j，j] ），然后扫描行 [j] 以确保它都是假的。
显然，对于朴素算法来说，性能是 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)。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
