在無(wú)向圖中，如果有從頂點(diǎn) v 到頂點(diǎn) w 的路徑存在，則稱 v和 w 是連通的得湘。若圖 G中任意兩個(gè)頂點(diǎn)都是連通的，則稱圖 G為連通圖顿仇，否則成為非連通圖淘正。
若圖 G 的子圖 G?s?? 是連通的，我們就稱子圖 G?s 是圖 G 的連通子圖臼闻。如果對(duì)于圖 G 的一個(gè)連通子圖 G?s??鸿吆，不存在圖 G 的其他連通子圖G?max?? 滿足：G?s??是 G?max?? 的子圖。則子圖 G?s?? 是圖 GG 的極大連通子圖述呐，也就是圖 G的連通分量惩淳。
如何求解無(wú)向圖的連通分量呢？這要用到我們本章介紹的第一個(gè)圖論算法：FloodFill 算法乓搬。
FloodFill 算法通常譯作“洪水灌溉法”思犁，算法通過(guò)給圖中的頂點(diǎn)染色，最終使得同一個(gè)連通分量的頂點(diǎn)顏色相同进肯，不同連通分量的頂點(diǎn)顏色不同激蹲。算法的描述如下：
- 找到一個(gè)沒(méi)有染色的頂點(diǎn)，將其染為新的顏色 Color_{new} Color?new??江掩，如果沒(méi)有則算法結(jié)束学辱。
- 初始化一個(gè)空的隊(duì)列，并將第一步的頂點(diǎn)插入隊(duì)列频敛。
- 不斷獲得隊(duì)首元素的值并彈出项郊，將和隊(duì)首元素相鄰的未染色頂點(diǎn)染為 Color_{new} Color?new??，并將其加入隊(duì)列斟赚。
- 重復(fù)執(zhí)行第一步着降，直到所有頂點(diǎn)都被染色，算法結(jié)束拗军。
FloodFill 演示
染色結(jié)果：
FloodFill 結(jié)果
具體代碼實(shí)現(xiàn)：
void floodfill(){
int color_cnt=0;//顏色計(jì)數(shù)
for(int i=0;i<n;i++){//遍歷所有節(jié)點(diǎn)
if(color[i]==0){//如果當(dāng)前節(jié)點(diǎn)沒(méi)有染色
color_cnt++;//切換一種顏色
color[i]=color_cnt;//染色
queue<int>bfs;
bfs.push(i);
while(!bfs.empty()){//執(zhí)行廣度優(yōu)先搜索
int vertex=bfs.front();
for(int adj_vertex:edges[vertex]){
if(color[adj_vertex]==0){
color[adj_vertex]=color_cnt;
bfs.push(adj_vertex);
}
}
bfs.pop();
}
}
}
for(int i=0;i<n;i++){//輸出所有染色結(jié)果
cout<<i<<” “<<color[i]<<endl;
}
}
