深度優(yōu)先遍歷類似于一個(gè)人走迷宮：
如圖所示，從起點(diǎn)開(kāi)始選擇一條邊走到下一個(gè)頂點(diǎn)，沒(méi)到一個(gè)頂點(diǎn)便標(biāo)記此頂點(diǎn)已到達(dá)。
當(dāng)來(lái)到一個(gè)標(biāo)記過(guò)的頂點(diǎn)時(shí)回退到上一個(gè)頂點(diǎn)，再選擇一條沒(méi)有到達(dá)過(guò)的頂點(diǎn)。
當(dāng)回退到的路口已沒(méi)有可走的通道時(shí)繼續(xù)回退。
而連通分量，看概念：無(wú)向圖g的極大連通子圖稱為g的連通分量( connected component)。任何連通圖的連通分量只有一個(gè)，即是其自身，非連通的無(wú)向圖有多個(gè)連通分量。
下面看看具體實(shí)例：
|
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;// 求無(wú)權(quán)圖的聯(lián)通分量public class components { private graph graph; // 存放輸入的數(shù)組 private boolean[] visited; // 存放節(jié)點(diǎn)被訪問(wèn)狀態(tài) private int componentcount; // 連通分量的數(shù)量 private int[] mark; // 存儲(chǔ)節(jié)點(diǎn)所屬聯(lián)通分量的標(biāo)記 // 構(gòu)造函數(shù)，初始化私有屬性 public components(graph graph) { this.graph = graph; componentcount = 0; // 連通分量初始數(shù)量為 0 visited = new boolean[graph.v()]; mark = new int[graph.v()]; for (int i = 0; i < graph.v(); i++) { visited[i] = false; // 節(jié)點(diǎn)初始訪問(wèn)狀態(tài)為 false mark[i] = -1; // 節(jié)點(diǎn)初始連通分量標(biāo)記為 -1 } for (int i = 0; i < graph.v(); i++) { // 對(duì)于未被訪問(wèn)的節(jié)點(diǎn)進(jìn)行 dfs深度優(yōu)先遍歷 if (!visited[i]) { dfs(i); componentcount++; // 對(duì)一個(gè)節(jié)點(diǎn)進(jìn)行dfs 到底后，一個(gè)連通分量結(jié)束，數(shù)量+1 } } } private void dfs(int i) { visited[i] = true; // 節(jié)點(diǎn) i 已被訪問(wèn) mark[i] = componentcount; // 節(jié)點(diǎn) i 屬于當(dāng)前連通分量的數(shù)量（標(biāo)記） for (int node : graph.adjacentnode(i)) { // 遍歷圖中節(jié)點(diǎn) i 的鄰接節(jié)點(diǎn) if (!visited[node]) // 對(duì)未被訪問(wèn)的鄰接節(jié)點(diǎn)進(jìn)行 dfs dfs(node); } } public boolean isconnected(int v, int w) { return mark[v] == mark[w]; // 根據(jù)兩節(jié)點(diǎn)所屬連通分量的標(biāo)記判斷兩節(jié)點(diǎn)是否相連 } public int getcomponentcount() { return componentcount; // 返回 graph 中連通分量的數(shù)量 }}//public class components {//// private graph g; // 圖的引用// private boolean[] visited; // 記錄dfs的過(guò)程中節(jié)點(diǎn)是否被訪問(wèn)// private int ccount; // 記錄聯(lián)通分量個(gè)數(shù)// private int[] id; // 每個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的聯(lián)通分量標(biāo)記//// // 圖的深度優(yōu)先遍歷// private void dfs(int v) {//// visited[v] = true; // 節(jié)點(diǎn) v 的訪問(wèn)狀態(tài)置為 true// id[v] = ccount; // 節(jié)點(diǎn) v 對(duì)應(yīng)的聯(lián)通標(biāo)記設(shè)置為 ccount//// // 遍歷節(jié)點(diǎn) v 的鄰接點(diǎn) i// for (int i : g.adjacentnode(v)) {// // 如果鄰接點(diǎn) i 尚未被訪問(wèn)// if (!visited[i])// // 對(duì)鄰接點(diǎn) i 進(jìn)行深度優(yōu)先遍歷// dfs(i);// }// }//// // 構(gòu)造函數(shù), 求出無(wú)權(quán)圖的聯(lián)通分量// public components(graph graph) {//// // 算法初始化// g = graph;//// // visited 數(shù)組存儲(chǔ) 圖g 中 節(jié)點(diǎn)的被訪問(wèn)狀態(tài)// visited = new boolean[g.v()];//// // id 數(shù)組存儲(chǔ) 圖g 中 節(jié)點(diǎn)所屬連通分量的標(biāo)記// id = new int[g.v()];//// // 連通分量數(shù)量初始化為 0// ccount = 0;//// // 將 visited 數(shù)組全部置為 false； id 數(shù)組全部置為 -1// for (int i = 0; i < g.v(); i++) {// visited[i] = false;// id[i] = -1;// }//// // 求圖的聯(lián)通分量// for (int i = 0; i < g.v(); i++)// // 訪問(wèn)一個(gè)未曾被訪問(wèn)的節(jié)點(diǎn)// if (!visited[i]) {// // 對(duì)其進(jìn)行深度優(yōu)先遍歷// dfs(i);// ccount++;// }// }//// // 返回圖的聯(lián)通分量個(gè)數(shù)// int count() {// return ccount;// }//// // 查詢點(diǎn)v和點(diǎn)w是否聯(lián)通（節(jié)點(diǎn)v 和 w 的聯(lián)通分量的標(biāo)記是否相同// boolean isconnected(int v, int w) {// assert v >= 0 && v < g.v();// assert w >= 0 && w < g.v();// return id[v] == id[w];// }//} |
通分量數(shù)量為 3
總結(jié)
以上就是本文關(guān)于java編程實(shí)現(xiàn)深度優(yōu)先遍歷與連通分量代碼示例的全部?jī)?nèi)容，希望對(duì)大家有所幫助。如有不足之處，歡迎留言指出。關(guān)注服務(wù)器之家，您會(huì)有更多收獲。
原文鏈接：http://blog.csdn.net/heatdeath/article/details/78587762
