判斷圖的連通性的三種方法：DFS、BFS 和並查集
1 什麼是結點的連通性？
若圖 G 中兩個不同的結點 u 和 v 存在路徑 e，則稱結點 u 和結點 v 連通。
2 什麼是圖的連通性？
若圖 G 中任意兩個結點連通，則稱圖 G 連通。
3 怎樣判斷圖的連通性？
判斷圖的連通性的常見方法有三種：DFS、BFS 和並查集。
3。1 DFS
深度優先遍歷得到的是圖的一個連通分量。
演算法流程：
從某個結點 v 出發，訪問結點 v，並令
vis［v］ = 1
；
查詢 v 的所有鄰接點 i，若結點 i 並未被訪問過（
vis［i］ = 0
），則從結點 i 出發，深度優先遍歷圖，轉至步驟（1）。
遞迴結束後，遍歷 vis 陣列，若陣列中有一個值不為 1，則說明該點未被訪問，圖不連通。
3。2 BFS
演算法流程：
從某個結點 v 出發，將結點 v 放入佇列 q 中；
佇列不空時，彈出隊首結點 v；
如果結點 v 沒被訪問過，查詢 v 的所有鄰接點 i；
如果結點 i 沒被訪問過，放入佇列 q 中；
如果結點 i 已被訪問，跳過。
如果結點 v 已被訪問，跳過。
標記結點 v 已被訪問（
容易遺漏！！！
）。
佇列為空時，遍歷 vis 陣列，若陣列中有一個值不為 1，則說明該點未被訪問，圖不連通。
3。3 並查集
並查集可以簡單理解為找根結點，使用 father 陣列記錄每個結點的根節點。
演算法流程：
初始化每個結點的根節點為結點本身；（可使用
iota（）
函式）
從某個結點 v 開始，查詢 v 的所有鄰接點 i，如果結點 v 和結點 i 的根節點不同（
father［v］ ！= father［i］
），則把兩個結點的根節點設為下標較小的根節點（
father［v］ = father［i］ = min（father［v］， father［i］）
）。
迴圈結束時，遍歷 father 陣列，若陣列中有一個值不為 0，則說明該點的根節點並不是 0 號結點，圖不連通。
3。4 比較
DFS 和 BFS 都是記錄結點是否已訪問，而並查集是記錄每個結點的根節點。
三種演算法都需要查詢當前結點的所有鄰接點，因而建議以鄰接表的形式儲存圖。
三種演算法的時間複雜度和空間複雜度如下表所示，其中 E 為邊的數目，V 為結點的數目。
4 程式碼
#include
#include
#include
#include
using
namespace
std
；
vector
<
vector
<
int
>>
g
；
int
n
；
vector
<
int
>
vis
；
vector
<
int
>
father
；
void
dfs
（
int
v
）
{
cout
<<
v
<<
“ ”
；
vis
［
v
］
=
1
；
for
（
int
i
=
0
；
i
<
g
［
v
］。
size
（）；
i
++
）
{
if
（
！
vis
［
g
［
v
］［
i
］］）
{
dfs
（
g
［
v
］［
i
］）；
}
}
}
void
bfs
（）
{
queue
<
int
>
q
；
q
。
push
（
0
）；
while
（
！
q
。
empty
（））
{
int
v
=
q
。
front
（）；
cout
<<
v
<<
“ ”
；
q
。
pop
（）；
if
（
！
vis
［
v
］）
{
for
（
int
i
=
0
；
i
<
g
［
v
］。
size
（）；
i
++
）
{
if
（
！
vis
［
g
［
v
］［
i
］］）
{
q
。
push
（
g
［
v
］［
i
］）；
}
}
}
vis
［
v
］
=
1
；
}
}
int
Find
（
int
x
）
{
int
a
=
x
；
while
（
x
！=
father
［
x
］）
{
x
=
father
［
x
］；
}
while
（
a
！=
father
［
a
］）
{
int
z
=
a
；
a
=
father
［
a
］；
father
［
a
］
=
x
；
}
return
x
；
}
void
Union
（
int
a
，
int
b
）
{
int
fA
=
Find
（
a
）；
int
fB
=
Find
（
b
）；
father
［
a
］
=
father
［
b
］
=
min
（
fA
，
fB
）；
}
int
main
（）
{
n
=
6
；
g
=
vector
<
vector
<
int
>>
（
n
，
vector
<
int
>
（））；
// 插入 6 條邊（雙向）
g
［
0
］。
push_back
（
1
）；
g
［
0
］。
push_back
（
2
）；
g
［
0
］。
push_back
（
5
）；
g
［
1
］。
push_back
（
0
）；
g
［
2
］。
push_back
（
0
）；
g
［
2
］。
push_back
（
3
）；
g
［
3
］。
push_back
（
2
）；
g
［
3
］。
push_back
（
4
）；
g
［
3
］。
push_back
（
5
）；
g
［
4
］。
push_back
（
3
）；
g
［
5
］。
push_back
（
0
）；
g
［
5
］。
push_back
（
3
）；
// DFS
vis
=
vector
<
int
>
（
n
，
0
）；
dfs
（
0
）；
cout
<<
endl
；
//0 1 2 3 4 5
// BFS
vis
=
vector
<
int
>
（
n
，
0
）；
bfs
（）；
cout
<<
endl
；
//0 1 2 5 3 3 4
// Union-Find Set
father
=
vector
<
int
>
（
n
）；
iota
（
father
。
begin
（），
father
。
end
（），
0
）；
for
（
int
i
=
0
；
i
<
n
；
i
++
）
{
for
（
int
j
=
0
；
j
<
g
［
i
］。
size
（）；
j
++
）
{
if
（
father
［
i
］
！=
father
［
g
［
i
］［
j
］］）
{
cout
<<
i
<<
“ ”
<<
g
［
i
］［
j
］
<<
endl
；
Union
（
i
，
g
［
i
］［
j
］）；
}
}
}
//0 1
//0 2
//0 5
//2 3
//3 4
// 可透過求和判斷陣列內所有元素是否都為 0：
cout
<<
（
accumulate
（
father
。
begin
（），
father
。
end
（），
0
）
==
0
）
<<
endl
；
//1
return
0
；
}
References
無向圖連通性判斷的五種方法（BFS、DFS、Union-find、Warshell、Tarjan）
上一篇:稻盛和夫？
