c++ - 比较两个图

Question

我需要比较许 multimap 表(多达几百万个图表比较)，我想知道最快的方法是什么。

图的顶点最多可以有 8 个邻居/边，顶点可以有 0 或 1 的值。旋转图仍然是同一个图，每个图都有相同数量的顶点。

图表看起来像这样:

现在我正在通过从第一个图中获取一个顶点并将其与第二个图中的每个顶点进行比较来比较图。如果我找到相同的顶点，那么我会检查两个顶点的邻居是否相同，并重复此操作直到我知道图形是否相同。

这种方法太慢了。在不丢弃肯定不同的图的情况下，比较具有大约一百个顶点的数千张图需要 40 多秒。

我正在考虑计算每个图表的唯一值，然后只比较值。我尝试这样做，但我只设法得出如果相等则图形可能相等的值，如果值不同则图形也不同。
如果我的程序比较这些值，那么它会在大约 2.5 秒内计算完所有内容(这仍然太慢)。

将顶点添加到该图中并更新边的最佳/最快方法是什么？现在我将此图存储在 std::map< COORD, Vertex > 中因为我认为那样搜索顶点更容易/更快。
COORD 是游戏板上的顶点位置(顶点的位置与比较图形无关)，Vertex 是:

struct Vertex
{
    Player player; // Player is enum, FIRST = 0, SECOND = 1
    Vertex* neighbours[8];
};

这张图代表了五子棋的当前棋盘状态，棋盘边缘有包裹，棋盘大小为 n*n，其中 n 最大为 2^16。

我希望我在写这篇文章时没有犯太多错误。我希望有人能帮助我。

Answer 1

首先，您需要让每个图都具有一致的表示形式，执行此操作的自然方法是创建图的有序表示形式。

第一级排序是通过根据邻居的数量进行分组来实现的。

然后通过将邻居值(0 和 1)映射到二进制数来对具有相同邻居数的每组节点进行排序，然后使用该二进制数在组节点之间强制执行顺序。

然后您可以使用散列函数以有序形式遍历每个组的每个节点。然后可以使用散列值来提供加速查找