深度优先遍历类似于一个人走迷宫:
如图所示,从起点开始选择一条边走到下一个顶点,没到一个顶点便标记此顶点已到达。
当来到一个标记过的顶点时回退到上一个顶点,再选择一条没有到达过的顶点。
当回退到的路口已没有可走的通道时继续回退。
而连通分量,看概念:无向图g的极大连通子图称为g的连通分量( connected component)。任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量。
下面看看具体实例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
package com.datastructure.graph; // 求无权图的联通分量 public class components { private graph graph; // 存放输入的数组 private boolean [] visited; // 存放节点被访问状态 private int componentcount; // 连通分量的数量 private int [] mark; // 存储节点所属联通分量的标记 // 构造函数,初始化私有属性 public components(graph graph) { this .graph = graph; componentcount = 0 ; // 连通分量初始数量为 0 visited = new boolean [graph.v()]; mark = new int [graph.v()]; for ( int i = 0 ; i < graph.v(); i++) { visited[i] = false ; // 节点初始访问状态为 false mark[i] = - 1 ; // 节点初始连通分量标记为 -1 } for ( int i = 0 ; i < graph.v(); i++) { // 对于未被访问的节点进行 dfs深度优先遍历 if (!visited[i]) { dfs(i); componentcount++; // 对一个节点进行dfs 到底后,一个连通分量结束,数量+1 } } } private void dfs( int i) { visited[i] = true ; // 节点 i 已被访问 mark[i] = componentcount; // 节点 i 属于当前连通分量的数量(标记) for ( int node : graph.adjacentnode(i)) { // 遍历图中节点 i 的邻接节点 if (!visited[node]) // 对未被访问的邻接节点进行 dfs dfs(node); } } public boolean isconnected( int v, int w) { return mark[v] == mark[w]; // 根据两节点所属连通分量的标记判断两节点是否相连 } public int getcomponentcount() { return componentcount; // 返回 graph 中连通分量的数量 } } //public class components { // // private graph g; // 图的引用 // private boolean[] visited; // 记录dfs的过程中节点是否被访问 // private int ccount; // 记录联通分量个数 // private int[] id; // 每个节点所对应的联通分量标记 // // // 图的深度优先遍历 // private void dfs(int v) { // // visited[v] = true; // 节点 v 的访问状态置为 true // id[v] = ccount; // 节点 v 对应的联通标记设置为 ccount // // // 遍历节点 v 的邻接点 i // for (int i : g.adjacentnode(v)) { // // 如果邻接点 i 尚未被访问 // if (!visited[i]) // // 对邻接点 i 进行深度优先遍历 // dfs(i); // } // } // // // 构造函数, 求出无权图的联通分量 // public components(graph graph) { // // // 算法初始化 // g = graph; // // // visited 数组存储 图g 中 节点的被访问状态 // visited = new boolean[g.v()]; // // // id 数组存储 图g 中 节点所属连通分量的标记 // id = new int[g.v()]; // // // 连通分量数量初始化为 0 // ccount = 0; // // // 将 visited 数组全部置为 false; id 数组全部置为 -1 // 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是否联通(节点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]; // } //} |
通分量数量为 3
总结
以上就是本文关于java编程实现深度优先遍历与连通分量代码示例的全部内容,希望对大家有所帮助。如有不足之处,欢迎留言指出。关注服务器之家,您会有更多收获。
原文链接:http://blog.csdn.net/heatdeath/article/details/78587762