1

I'm working with a very large undirected graph (email networks for a company).

I’m bit confused about selecting the best and suitable technique of undirected graph of email networks. In that network, the vertices represent email addresses and an edge represents that there was at least one email in one direction between the two addresses.

Is there someone who knows the best technique to represent the algorithm?

I am using a large undirected graph of mailing, then which representation is good? Adjacency list or Adjacency Matrix?

4

2 回答 2

1

这取决于相互发送电子邮件的人数以及在图表上完成的操作。

如果两个人互相发送电子邮件的可能性很高，那么您应该使用邻接矩阵。

另一方面，如果边的数量（2 个人相互发送电子邮件至少一个）与您应该使用邻接列表的电子邮件地址数量相比较小。

要查看的另一件事是您在图表上执行了哪些类型的操作。

因此，如果大多数操作包括查询两个节点之间是否有边，那么邻接矩阵将是最佳选择。

另一方面，如果大多数操作是遍历图或查询连接到给定节点的节点列表，那么邻接表会更好。

如果您同时执行这两种类型的查询，则可以将图形表示为哈希表数组。因此，这将是使用哈希表而不是列表的邻接表表示。

更新

请检查这个问题的答案。他们详细解释了邻接表和邻接矩阵之间的区别。

为了找出边的数量

我会运行一个程序来计算边数。它如下所示：

mp = hash_table
for email in emails
   if !mp[email.sender][email.receiver]
       mp.insert({email.sender, email.receiver})
   end
end
return mp.size

如果程序崩溃了，那么你可能已经超出了内存，并且与电子邮件地址的数量相比，边的数量很大（因为电子邮件地址的数量是数百万 [如评论中所述]），你可能想去与邻接表。

如果您真的想找到确切的边数，您可以分割电子邮件，其中每个段由具有相同发件人的电子邮件组成，并在每个段上运行上述程序，那么最终答案将围绕结果的总和

于 2018-01-21T22:22:27.763 回答
0

是否应该使用邻接矩阵或邻接列表取决于图形的密度。表示公司电子邮件网络的图表通常是稀疏的，因为只有一小部分员工需要相互发送邮件。例如，您不会向与您不在同一部门的人发送电子邮件。因此，您可以使用邻接表。

于 2018-01-23T06:46:43.577 回答