FloodFill 模板

在无向图中，如果有从顶点 v 到顶点 w 的路径存在，则称 v和 w 是连通的。若图 G中任意两个顶点都是连通的，则称图 G为连通图，否则成为非连通图。

若图 G 的子图 G​s​​ 是连通的，我们就称子图 G​s 是图 G 的连通子图。如果对于图 G 的一个连通子图 G​s​​，不存在图 G 的其他连通子图G​max​​ 满足：G​s​​是 G​max​​ 的子图。则子图 G​s​​ 是图 GG 的极大连通子图，也就是图 G的连通分量。

如何求解无向图的连通分量呢？这要用到我们本章介绍的第一个图论算法：FloodFill 算法。

FloodFill 算法通常译作“洪水灌溉法”，算法通过给图中的顶点染色，最终使得同一个连通分量的顶点颜色相同，不同连通分量的顶点颜色不同。算法的描述如下：

1. 找到一个没有染色的顶点，将其染为新的颜色 Color_{new} Color​new​​，如果没有则算法结束。
2. 初始化一个空的队列，并将第一步的顶点插入队列。
3. 不断获得队首元素的值并弹出，将和队首元素相邻的未染色顶点染为Color_{new} Color​new​​，并将其加入队列。
4. 重复执行第一步，直到所有顶点都被染色，算法结束。

具体代码实现：

void floodfill(){
    int color_cnt=0;//颜色计数
    for(int i=0;i<n;i++){//遍历所有节点
        if(color[i]==0){//如果当前节点没有染色
            color_cnt++;//切换一种颜色
            color[i]=color_cnt;//染色
            queue<int>bfs;
            bfs.push(i);
            while(!bfs.empty()){//执行广度优先搜索
                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++){//输出所有染色结果
        cout<<i<<” “<<color[i]<<endl;
    }
}

作者：qratosone
链接：http://www.jianshu.com/p/1dd523c9e062