本文转载自微信公众号《内测学习JAVA》，作者Silently9527。转载本文请联系贝塔学习JAVA公众号。在上一篇文章中，我们了解了深度优先搜索以及如何通过深度优先搜索在图中找到一条路径；在本文中，我们将继续学习深度优先搜索算法的其他应用场景连通分量从一个图中找到所有的连通分量连通分量，这也是深度优先搜索的一个应用场景。什么是连通分量？这个定义在之前的文章《如何检测社交网络中两个人是否是朋友关系(union-find算法)》中已经提到，本文中使用了union-find算法实现的连通性检查。在本文中，我们将使用深度优先搜索的方法找出连通分量的所有连通分量的API定义publicclassDepthFirstCC{publicDepthFirstCC(Graphgraph);publicbooleanconnected(intv,intw);//检查两个顶点是否连通publicintcount();//连通分量总数publicintid(intv);//顶点v所在连通分量的标识符}的API实现连接的组件与以前相同。如果我们不扫描一个顶点，我们需要标记这个顶点，所以我们仍然需要定义一个marked[]数组。为了统计图中连通分量的总数，我们需要定义一个变量count来判断两个顶点是否连通，我们需要将连通的顶点对应的标识值记录为相同的值。调用connected方法时，直接取出两个顶点的标识值进行比较。如果相同则为连通，否则为不连通；我们使用计数值作为标识值，每个顶点都需要存储一个标识值，所以还需要一个ids[]数组。publicclassDepthFirstCC{privatebooleanmarked[];privateintcount;privateint[]ids;publicDepthFirstCC(Graphgraph){this.marked=newboolean[graph.V()];this.ids=newint[graph.V()];for(intv=0;v
