有一个有向图具有一个称为根的指定节点，所有其他节点都可以从该节点到达。每个终端节点（没有出边）采用一个字符串值。中间节点有一个或多个出边，但没有与之关联的值。将节点连接到其邻居的边具有字符串标签。从单个节点发出的边的标签是唯一的。图中可能存在循环！
检查两个这样的有向（可能有循环）图（如上所述）是否相等的最佳图算法是什么？
问问题
967 次
1 回答
1
图同构问题是 TCS 中比较有趣的问题之一。在 wiki上有一个专门的页面。
在您的特定情况下，您有两个带有源和接收器的有根有向图。
您可以并行启动两个 BFS，并逐级检查同构；即水平化图并检查每个级别的节点子集是否在两个图中同构。
请注意，由于您有一个有向、有根图，您仍然应该能够对其进行平整化以找到同构。不要将 BFS 期间已经访问过的节点加入队列；即在确定要分组的级别时，使用从根到节点的最短路径进行级别化。
在一组内，比较应该相对容易。您有许多属性可以区分同一级别的节点（度数、标签），并且应该能够创建合适的签名来对它们进行排序。由于您正在寻找完美的同构，因此您应该得到完全匹配。
于 2012-07-05T07:27:42.907 回答