问题描述
有人问我一个问题，如何找到在社交网络中的发行人。假设（简体）社交网络只有下两个用户之间的关系，我们不能跟着自己。然后，我们定义了一个发布者为谁其次是其他所有用户，但不遵循任何一个用户。
更具体地讲，鉴于邻接矩阵的格式，这样的社会网络图，说N×N的布尔矩阵，其中细胞[I，J]表示是否我用户按照用户学家如何找到出版商。
我可以看到的是，至多有一个发布者可能存在（这很容易证明：自发行之后是其他人，那么其他人在至少一个用户，因此他们不是发布者）。我想出了一个天真的解决方案：首先扫描列一列，如果有一个所有真正的第j列（除当然细胞[J，J]），然后扫描行[J]，以确保它的全是假的
显然，性能是O（n ^ 2）朴素算法的事业，我们扫描整个矩阵。但是，有人告诉我，有一个O（n）的解决方案。那种我停留在为O（n）。任何提示？
如果你的数据是psented作为邻接矩阵$ P $，然后就可以进行如下操作。首先检查矩阵中的条目（1,2）。如果1如下2则1不是发布者，并且如果1不遵循2然后2不发行。除去谁是不发行（1或2），并让X为剩余节点。然后检查矩阵中的条目（X，3）。同样你会得到，要么X不是出版商或3不发行。除去谁是不是出版商，然后添加节点4，然后重复。当你重复这个过程，所有的n个节点，你将留下一个候选的发布者。然后，你可以检查的行和列的考生，以确认它是一个真正的出版商。总运行时间为O（n），整个算法，即使邻接矩阵具有大小为n ^ 2。
I was asked a question how to find a "publisher" in a social network. Suppose the (simplified) social network only has "following" relationship between two users and one cannot follow himself. Then we define a "publisher" as a user who is followed by ALL other users but does not follow anyone.
More specifically, given such a social network graph in the format of adjacency matrix, say NxN bool matrix, where cell[i,j] indicates whether or not user i follows user j. How to find out the publisher.
What I can see is that there is at most one publisher could exist.(it's easy to prove: since publisher is followed by everyone else, then everyone else follows at least one user, so they are not publisher). I do come up with a naive solution: first scan column by column, if there is a all true column j (except for cell[j,j] of course), then scan row[j] to make sure it's all false.
Obviously, the performance is O(n^2) for the naive algorithm cause we scan the whole matrix. However, I was told that there is an O(n) solution. I am kind of stuck at O(n). Any hints?
If your data is presented as an adjacency matrix, then you can proceed as follows. Start by checking entry (1,2) in the matrix. If 1 follows 2 then 1 is not the publisher, and if 1 does not follow 2 then 2 is not the publisher. Remove whoever is not the publisher (1 or 2) and let X be the remaining node. Then check entry (X,3) in the matrix. Similarly you will get that either X is not the publisher or 3 is not the publisher. Remove whoever is not the publisher and then add node 4 and repeat. After you have repeated this process with all n nodes, you will be left with one candidate for the publisher. Then you can check the row and column for the candidate to verify that it is a true publisher. Total running time is O(n) for the entire algorithm, even though the adjacency matrix has size n^2.
这篇关于O（n）的算法找到一个社交网络中的“发布者”的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！