擅长:python、mysql、java
<p>这个问题可以归结为图论中的一个问题,即在图中找到所有连通的节点组。在</p>
<p>解决这个问题的一个有效方法是使用“洪水填充”算法,这本质上是一个递归的呼吸优先搜索。这个<a href="http://en.wikipedia.org/wiki/Flood_fill" rel="nofollow">wikipedia entry</a>描述了泛洪填充算法及其如何应用于解决图的连通区域的问题。在</p>
<p>要了解如何将原始问题转化为图形问题,请将每个条目(例如“Server1”、“Server1”等)设为图形上的一个节点。当且仅当节点是同义词时,才使用边连接节点。如果有足够的内存,矩阵数据结构特别适合于跟踪边。否则,像地图这样的稀疏数据结构将起作用,特别是因为同义词的数量可能会受到限制。在</p>
<ul>
<li>服务器1是节点0</li>
<li>服务器1是节点1</li>
<li>服务器2是节点2</li>
</ul>
<p>然后edge[0][1]=edge[1][0]=1,表示节点0和节点1之间有一条边(这意味着它们是同义词)。而edge[0][2]=edge[2][0]=0,表示Server1和server2是<strong>非</strong>同义词。在</p>
<p><strong>复杂性分析</strong></p>
<p>创建这个数据结构是非常有效的,因为一个单一的线性过程和查找字符串到节点号的映射就足够了。如果在字典中存储字符串到节点号的映射,那么这将是一个O(n logn)步骤。在</p>
<p>执行泛洪填充是O(n),您只访问图中的每个节点一次。因此,该算法是O(nlogn)。在</p>