0

我目前正在写关于图中聚类的硕士论文。我的教授说他希望将图表表示为哈希表。因为它比邻接矩阵需要更少的空间，并且在检查两个顶点之间是否存在边时比邻接列表更快。无论如何，我在理解如何使用（完美）散列函数构建图形时遇到很多问题。我知道里面应该有两张桌子。第一个包含每个节点，第二个包含所有相邻的顶点。但是我如何找到一个正确的哈希函数呢？构建图表后，我必须为每条边分配权重。建一个新图好还是保留旧图好？如何正确地将权重分配给每个边缘以及如何保存它？最后一个问题：我可以多快对一个顶点进行度数查询？奥（1）？

很抱歉所有这些问题，但我读了很多论文，我仍然感到困惑。预先感谢您的任何帮助！！！

丽莎

4

1 回答 1

0

你必须问你的教授，但我认为这很简单。

例如，假设您有一个三角形 A、B、C，然后在散列中您只需将其表示为

A {B,C}
B {A,C}
C {A,B}

所以链接 A,B 的入口可能来自 A 和 B。

于 2021-07-13T07:45:49.637 回答