浙大数据结构的编程题——-图-列出连通集
数据结构-图-列出连通集
给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式:
按照"{ v1 v 2 … v k }“的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。
输入样例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5
输出样例：
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
思路
基础概念
边没有方向的图称为无向图。
dfs(深度优先搜索)是两个搜索中先理解并使用的，其实就是暴力把所有的路径都搜索出来，它运用了回溯，保存这次的位置，深入搜索，都搜索完了便回溯回来，搜下一个位置，直到把所有最深位置都搜一遍，要注意的一点是，搜索的时候有记录走过的位置，标记完后可能要改回来；可用递归进行实现。
bfs宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
两者区别
深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形：
- 把根节点压入栈中。
- 每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
- 找到所要找的元素时结束程序。
- 如果遍历整个树还没有找到，结束程序。
- 类似于树的前序遍历
其伪代码如下：
DFS(int u){ //DFS函数
vis[u]=true; //用数组vis记录结点是否被访问
for(从u出发所能到达的所有顶点v){ //枚举所有u能到达的顶点v
if(vis[v]==false){ //如果未被访问，递归进行访问
DFS(v);
}
}
}
DFSTrave(G){ //DFS的驱动函数
for(G的所有顶点u){ //对每一个连通分量都进行DFS遍历
if(vis[u]==false){
DFS(u)
}
}
}
广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形：
- 把根节点放到队列的末尾。
- 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
- 找到所要找的元素时结束程序。
- 如果遍历整个树还没有找到，结束程序。
- 类似于树的层序遍历
其伪代码如下：
BFS(u){
queue q;
q.push(u); //起始顶点入队并标记
vis[u]=ture;
while(队列q不空){
取出队首元素u进行访问;
for(从U出发可达到的所有顶点v){
if(vis[v]==false){ //如果v未曾加入过队列，入队并标记
将v入队;
vis[v]=ture;
}
}
}
}
BFSTrave(G){
for(G的所有顶点u，依此访问){
if(vis[u]==false){
BFS(u);
}
}
}
解题思路
首先要建立图，存储图。表示图主要有两种方式：
- 邻接矩阵G[N][N]：
- 用二维数组表示，直观易于理解。
- 方便检查任意一对顶点间是否存在边
- 方便查找任一顶点的所有“邻接点”（有边相连的顶点）
- 方便计算任一顶点的“度”（对应行列非0元素个数）
- 缺点：稀疏图浪费空间，数边时间复杂度较高
- 邻接表 G[N]为指针数组，对应矩阵每行一个链表，只存非0元素。
- 方便查找任一顶点的所有“邻接点”（有边相连的顶点）
- 节约稀疏图空间
- 方便计算任一顶点的“度” ，其对应链表元素个数
- 缺点：检查顶点间是否存在边需要遍历对应数组
建立图后，先输出DFS的结果，再输出BFS的结果 在每次有新的结点被遍历后，将新的被遍历的结点输出。
Code
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <iterator>
#include <math.h>
#include <stack>
#include <queue>
using namespace std;
#define Graph vector<vector<int>>
void DFS(Graph G,int node, vector<int> &visited) {
visited.push_back(node);
for (int i = 0 ; i < G.size(); i++) {
if (G[node][i] == 1 ) {//枚举所有u能到达的顶点v,如果未被访问，递归进行访问
if(find(visited.begin(),visited.end(),i)== visited.end())
DFS(G, i, visited);
}
}
}
void BFS(Graph G, int node, vector<int> &visited) {
queue<int> q;
q.push(node);
while (!q.empty())
{
int u = q.front();
//u被访问过，则跳出,
if (find(visited.begin(), visited.end(), u) != visited.end()) {
q.pop();
continue;
}
//u未被访问过,访问u
visited.push_back(u);
for (int i = 0; i < G.size(); i++) {
if (G[u][i] == 1) {//枚举所有u能到达的顶点v,压入queue
q.push(i);
}
}
}
}
int main() {
//begin: end:
ios::sync_with_stdio(false);
//建立图，邻接矩阵
int N,E; //分别是图的顶点数和边数
cin >> N >> E;
Graph G(N, vector<int>(N,0));//初始化
int x, y;
for (int i = 0; i < E; i++) {
cin >> x >> y;
G[x][y] = 1;
G[y][x] = 1;
}
//DFS
int DFS_out=0;//可以存个数
vector<int> visited;
for (int i = 0; i < N; i++) {
if (find(visited.begin(), visited.end(), i) == visited.end()) {
DFS(G, i, visited);
if (visited.size() > DFS_out) {//如有新访问的结点，则输出
cout << "{ ";
for (int i = DFS_out; i < visited.size(); i++) {
cout << visited[i] << " ";
}
DFS_out = visited.size();
cout << "}" << endl;
}
}
}
//BFS
int BFS_out = 0;
visited.clear();
for (int i = 0; i < N; i++) {
if (find(visited.begin(), visited.end(), i) == visited.end()) {
BFS(G, i, visited);
if (visited.size() > BFS_out) {//如有新访问的结点，则输出
cout << "{ ";
for (int i = BFS_out; i < visited.size(); i++) {
cout << visited[i] << " ";
}
BFS_out = visited.size();
cout << "}" << endl;
}
}
}
return 0;
}