深度优先遍历与连通分量(Java 实例代码源码包下载)

红太狼 2023-10-14 22:32 95阅读 0赞

**目录**

深度优先遍历与连通分量

Java 实例代码

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

--------------------

## 深度优先遍历与连通分量 ##

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

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

![e939335538f1ae1e7bcfc733b3a98d5b.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 实例代码 ####

**源码包下载：**[Download][]

### 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\];  
\}  
\}

[e939335538f1ae1e7bcfc733b3a98d5b.png]: https://img-blog.csdnimg.cn/img_convert/e939335538f1ae1e7bcfc733b3a98d5b.png
[Download]: https://www.runoob.com/wp-content/uploads/2020/10/runoob-algorithm-Graph-Theory.zip