我认为示例将比loooong描述好得多:)
假设我们有一个数组数组:
("Server1", "Server_1", "Main Server", "192.168.0.3")
("Server_1", "VIP Server", "Main Server")
("Server_2", "192.168.0.4")
("192.168.0.3", "192.168.0.5")
("Server_2", "Backup")
每行包含作为同义词的字符串。作为处理此数组的结果，我想得到这个:
("Server1", "Server_1", "Main Server", "192.168.0.3", "VIP Server", "192.168.0.5")
("Server_2", "192.168.0.4", "Backup")
所以我认为我需要一种递归算法。编程语言实际上并不重要-一般而言，我只需要一点点帮助即可。我将使用php或python。
谢谢!
最佳答案
这个问题可以简化为图论中的问题，在图论中可以找到图中的所有连接节点组。
解决此问题的有效方法是执行“泛洪填充”算法，该算法本质上是递归呼吸优先搜索。此wikipedia entry描述了洪水填充算法，以及如何将其应用于解决查找图形的连通区域的问题。
要查看如何将原始问题变成图表上的问题，请执行以下操作:将每个条目(例如“Server1”，“Server_1”等)作为图表上的节点。当且仅当它们是同义词时，才用边连接节点。如果您有足够的内存，矩阵数据结构特别适合跟踪边缘。否则，像 map 这样的稀疏数据结构将起作用，尤其是由于同义词的数量可能会受到限制。
然后edge [0] [1] = edge [1] [0] = 1表示节点＃0和＃1之间存在一条边(这意味着它们是同义词)。而edge [0] [2] = edge [2] [0] = 0表示Server1和Server_2是而不是同义词。
复杂度分析
创建此数据结构非常有效，因为只需进行一次线性遍历，即可查找字符串到节点号的映射关系。如果将字符串到节点号的映射关系存储在字典中，则这将是O(n log n)步骤。
进行洪水填充为O(n)，您只需访问图形中的每个节点一次。因此，该算法总计为O(n log n)。
关于php - 同义词查找器算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6134500/