一个图可能有好几个连通子图,比如一个图有四个顶点,而这张图只有2个边,分别是第一个顶点和第二个顶点相连,第三个和第四个顶点相连。那形成的图则有两个连通子图。这个有三种实现方式分别基于DFS,BFS,并查集,其本质是一样的。
DFS关键代码如下:
for (int i = 0; i <G.n; i++) {
if (vis[i])
continue;
DFS(G, i);
cout << endl;
count++;
}
近期评论