深度优先遍历与连通分量

男娘i 2024-03-17 11:45 18阅读 0赞

深度优先遍历(Depth First Search)的主要思想是首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直至所有的顶点都被访问过。

下图示例的图从 0 开始遍历顺序如右图所示：

![f0242c25bbe89d1696dd1b3d958bb6f5.png][]

无向图 G 的一个极大连通子图称为 G 的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。连通分量与连通分量之间没有任何边相连。深度优先遍历可以用来求连通分量。

下面以求连通分量为例，来实现图的深度优先遍历，称为 dfs。下面代码片段中，visited 数组记录 dfs 的过程中节点是否被访问，ccount 记录联通分量个数，id 数组代表每个节点所对应的联通分量标记，两个节点拥有相同的 id 值代表属于同一联通分量。

> ...  
> // 构造函数, 求出无权图的联通分量  
> public Components(Graph graph)\{  
> // 算法初始化  
> G = graph;  
> visited = new boolean\[G.V()\];  
> id = new int\[G.V()\];  
> ccount = 0;  
> for( int i = 0 ; i < G.V() ; i ++ )\{  
> visited\[i\] = false;  
> id\[i\] = -1;  
> \}  
> // 求图的联通分量  
> for( int i = 0 ; i < G.V() ; i ++ )  
> if( !visited\[i\] )\{  
> dfs(i);  
> ccount ++;  
> \}  
> \}  
> ...

图的深度优先遍历是个递归过程，实现代码：

> ...  
> // 图的深度优先遍历  
> void dfs( int v )\{  
>   
> visited\[v\] = true;  
> id\[v\] = ccount;  
>   
> for( int i: G.adj(v) )\{  
> if( !visited\[i\] )  
> dfs(i);  
> \}  
> \}  
> ...

#### Java 实例代码 ####

### src/runoob/graph/Components.java 文件代码： ###

> package runoob.graph;  
>   
> import runoob.graph.read.Graph;  
>   
> /\*\*  
> \* 深度优先遍历  
> \*/  
> public class Components \{  
>   
> Graph G; // 图的引用  
> private boolean\[\] visited; // 记录dfs的过程中节点是否被访问  
> private int ccount; // 记录联通分量个数  
> private int\[\] id; // 每个节点所对应的联通分量标记  
>   
> // 图的深度优先遍历  
> void dfs( int v )\{  
>   
> visited\[v\] = true;  
> id\[v\] = ccount;  
>   
> for( int i: G.adj(v) )\{  
> if( !visited\[i\] )  
> dfs(i);  
> \}  
> \}  
>   
> // 构造函数, 求出无权图的联通分量  
> public Components(Graph graph)\{  
>   
> // 算法初始化  
> G = graph;  
> visited = new boolean\[G.V()\];  
> id = new int\[G.V()\];  
> ccount = 0;  
> for( int i = 0 ; i < G.V() ; i ++ )\{  
> visited\[i\] = false;  
> id\[i\] = -1;  
> \}  
>   
> // 求图的联通分量  
> for( int i = 0 ; i < G.V() ; i ++ )  
> if( !visited\[i\] )\{  
> dfs(i);  
> ccount ++;  
> \}  
> \}  
>   
> // 返回图的联通分量个数  
> int count()\{  
> return ccount;  
> \}  
>   
> // 查询点v和点w是否联通  
> boolean isConnected( int v , int w )\{  
> assert v >= 0 && v < G.V();  
> assert w >= 0 && w < G.V();  
> return id\[v\] == id\[w\];  
> \}  
> \}

[f0242c25bbe89d1696dd1b3d958bb6f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ab938b2104fc483db5c7fc2fe29e6c00.png