7-2 列出连通集 (25分)
给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式:
按照"{ v1 v2 … vk }"的格式，每行输出一个连通集。先输出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 }
题解
创建二维矩阵，输入的边的值为1，没有边为0，再利用bfs，dfs进行输出
编写深度优先搜索函数，广度优先搜索函数，再通过函数调用进行输出。
伪代码
Dfs算法 { 访问过的点 = 1; cout << " " << a; for (int i = 0; i < N; i++) { if (其他点到这个点有边并且该点未被访问过)//该点未访问过并且其他点到这个点有边 { Dfs递归 } } } Bfs算法 { 创建队列 将点压入队列； 访问过该点 = 1; while (队列不为空) { 设an为队首元素; 弹出队首元素; 将an输出; for (int i = 0; i < N; i++) { if (该点未访问过并且该点与其他点有边) { 标记该点为1，被访问过 将该点压入队列 } } } }
代码
#include<iostream> #include<algorithm> #include<stdio.h> #include<vector> #include<stack> #include<math.h> #include<queue> using namespace std; const int inf = 99999; const int maxn = 12; int n, e, G[maxn][maxn]; bool vis[maxn], inq[maxn]; // 深度优先搜索 void DFS(int u) { vis[u] = true; cout << " " << u; for (int v = 0; v < n; v++) { if (vis[v] == false && G[u][v] != inf) { DFS(v); } } } void DFSTravel() { for (int u = 0; u < n; u++) { if (vis[u] == false) // 避免没有通路情况 { cout << "{"; DFS(u); cout << " }\n"; } } } // 广度优先搜索 void BFS(int u) { queue<int> q; q.push(u); inq[u] = true; // 访问过标记true while (!q.empty()) { int temp = q.front(); cout << " " << temp; q.pop(); for (int v = 0; v < n; v++) { if (inq[v] == false && G[temp][v] != inf) { q.push(v); inq[v] = true; } } } } void BFSTravel() { for (int u = 0; u < n; u++) { if (inq[u] == false) { cout << "{"; BFS(u); cout << " }\n"; } } } int main() { fill(G[0], G[0] + maxn * maxn, inf); cin >> n >> e; for (int i = 0; i < e; i++) { int a, b; cin >> a >> b; G[a][b] = G[b][a] = 1; // 通路赋值为1 } DFSTravel(); // 深度优先搜索 BFSTravel(); // 广度优先搜索 return 0; }
