擅长:python、mysql、java
<p>你所做的不是真正的聚类分析,而是<a href="http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29" rel="noreferrer">connected component</a>分析。聚类分析就是从一大堆单独的点中找出圆圈。但您可能感兴趣的是,将点分配到初始邻域和通过重叠邻域进行基于聚类的可达性的组合是<a href="http://en.wikipedia.org/wiki/DBSCAN" rel="noreferrer">DBSCAN</a>思想及其<a href="http://en.wikipedia.org/wiki/Cluster_analysis#Density-based_clustering" rel="noreferrer">density-based clustering</a>变体的核心。在</p>
<p>在任何情况下,因为你是从圆开始的,一旦你完成了碰撞检测,你所说的重叠列表就是邻接列表,而你所称的集群就是连接的组件。算法相当简单:</p>
<ol>
<li>创建所有节点的列表<code>L</code>。在</li>
<li>创建已连接组件的空列表<code>Cs</code></li>
<li>当<code>L</code>不为空时:
<ol>
<li>选择任意节点<code>N</code></li>
<li>创建一个连接的组件列表<code>C</code>,用<code>N</code>初始化</li>
<li>使用邻接列表执行广度优先或深度优先遍历,将遇到的每个节点添加到<code>C</code></li>
<li>将<code>C</code>追加到<code>Cs</code></li>
<li>从<code>L</code>中删除<code>C</code>中的所有节点</li>
</ol></li>
</ol>