在上篇中我们学习了深度优先搜索，知道了如何通过深度优先搜索在图中寻找路径;本篇我们继续一起来学习深度优先搜索算法的其他应用场景

连通分量

从一幅图中找出所有的连通分量，这是也是深度优先搜索的一个应用场景。什么是连通分量?这个定义在之前的文章中已有提到《如何检测社交网络中两个人是否是朋友关系(union-find算法)》

在这篇采用的是union-find算法实现的连通性检查，本篇我们将采用深度优先搜索的方式来找出图中的所有连通分量

连通分量的API定义

1. public class DepthFirstCC { 
2.     public DepthFirstCC(Graph graph);  
3.      
4.     public boolean connected(int v, int w); //检查两个顶点是否连通 
5.  
6.     public int count(); //统计连通分量的总数 
7.  
8.     public int id(int v); //顶点v所在连通分量的标识 
9. } 

连通分量的API实现

与之前一样没扫描到一个顶点我们就需要标记这个顶点，所以依然需要定义一个marked[]数组

为了统计出图中总共有多少连通分量，所以需要定义一个变量count

为了判断两个顶点是否相连，我们需要把相连的顶点对应的标识值记录成相同值，当在调用connected方法的时候直接取出两个顶点的标识值比较，如果相同就是连通的，否则就是非连通;

这个的标识值我们使用的是count的值，每个顶点都需要存一个标识值，所以还需要一个ids[]数组。

1. public class DepthFirstCC { 
2.     private boolean marked[]; 
3.     private int count; 
4.     private int[] ids; 
5.  
6.     public DepthFirstCC(Graph graph) { 
7.         this.marked = new boolean[graph.V()]; 
8.         this.ids = new int[graph.V()]; 
9.  
10.         for (int v = 0; v < graph.V(); v++) { 
11.             if (!this.marked[v]) { 
12.                 dfs(graph, v); 
13.                 count++; 
14.             } 
15.         } 
16.     } 
17.  
18.     private void dfs(Graph graph, int v) { 
19.         this.marked[v] = true; 
20.         this.ids[v] = count; 
21.         for (int w : graph.adj(v)) { 
22.             if (!this.marked[w]) { 
23.                 dfs(graph, w); 
24.             } 
25.         } 
26.     } 
27.  
28.     public boolean connected(int v, int w) { 
29.         return id(v) == id(w); 
30.     } 
31.  
32.     public int count() { 
33.         return count; 
34.     } 
35.  
36.     public int id(int v) { 
37.         return ids[v]; 
38.     } 
39.  
40. } 

单元测试

构造这样一个图，连通分量的总数应该是3

1. @Test 
2. public void test() { 
3.     Graph graph = new Graph(10); 
4.     graph.addEdge(0, 1); 
5.     graph.addEdge(0, 2); 
6.     graph.addEdge(0, 5); 
7.     graph.addEdge(1, 3); 
8.     graph.addEdge(2, 4); 
9.     graph.addEdge(4, 3); 
10.     graph.addEdge(5, 3); 
11.  
12.     graph.addEdge(6, 7); 
13.  
14.     graph.addEdge(8, 9); 
15.  
16.     DepthFirstCC cc = new DepthFirstCC(graph); 
17.  
18.     System.out.println(cc.connected(0,5)); 
19.     System.out.println(cc.connected(1,2)); 
20.  
21.     System.out.println(cc.count()); 
22. } 

基于深度优先搜索实现的连通性检查理论上说要比以前实现的union-find算法更快，因为检查连通性深度优先搜索实现的版本能够保证在常量时间内完成，而union-find算法不行;

但是union-find也有自己的优势: 不需要把完整的构造并表示一张图，更重要的是union-find算法是动态的添加节点。