c++ - 检查是否存在一串始终通向同一顶点的方向

Question

有一个图有 n 个顶点。每个都有 4 条边，分别代表世界的每一侧。所有这些都是定向的。我必须编写一个程序来检查是否存在一串始终指向相同顶点的方向，无论您从哪里开始。例如:

example 1

如果你去 S W S，你将永远在 3。

example 2

这样的方向字符串不存在。

我知道如何去做，但我需要一个大小为 2^n 的 bool 数组。但是，程序必须适用于大小不超过 1000 的 n。最好的方法是什么？

Answer 1

您描述的那种字符串称为 synchronizing word .如果您只是想测试这样的词是否存在，可以使用多项式时间算法 described in these lecture slides .直观地，对于每对节点 u 和 v，您构建一个新图，其中起始节点是对 {u, v}。每个节点都有一个在每个字符 c 上定义到集合 {t(c, u), t(c, v)} 的转换，其中 t(c, u) 表示通过读取状态 u 中的字符 c 转换到的节点。您可以使用 DFS 或 BFS 扩展此图。当且仅当对于每对节点 {u, v}，上述过程生成的图具有从 {u, v} 到某个单例节点的路径时，原始图才具有同步词。

如果您在线搜索，您可以找到关于该主题的各种其他读物。希望术语和以上链接可以帮助您入门!