PTA 7-6 列出连通集

题目详情：

给定一个有 n 个顶点和 m 条边的无向图，请用深度优先遍历（DFS）和广度优先遍历（BFS）分别列出其所有的连通集。假设顶点从 0 到 n−1 编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式:

输入第 1 行给出 2 个整数 n (0<n≤10) 和 m，分别是图的顶点数和边数。随后 m 行，每行给出一条边的两个端点。每行中的数字之间用 1 空格分隔。

输出格式:

按照"{ v1 v2 ... vk }"的格式，每行输出一个连通集。先输出 DFS 的结果，再输出 BFS 的结果。

输入样例:

输出样例:

{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

题目解析

逐步分析

首先，图的表示方式。顶点数n不超过10，可以用邻接表或者邻接矩阵。因为需要按编号递增的顺序访问邻接点，所以邻接表里的每个顶点的邻接点应该按升序排列。或者，在每次访问邻接点的时候，按从小到大的顺序遍历。例如，对于邻接矩阵来说，每个顶点x的所有邻接点，可以按顶点编号从小到大遍历，即从0到n-1依次检查是否有边相连。

或者，邻接表的话，每个顶点的邻接点列表需要排序。例如，每次添加边的时候，把邻接点插入到正确的位置，保持列表的升序。或者，在生成邻接表之后，对每个顶点的邻接点列表进行排序。这一步很重要，因为DFS和BFS的遍历顺序必须按照邻接点的编号递增的顺序进行访问。所以，图的存储结构可能需要邻接表或者邻接矩阵，同时要保证遍历邻接点的顺序是递增的。

例如，邻接矩阵的话，对于每个顶点，遍历时检查所有顶点，按照编号顺序依次访问是否有边相连。这可能比较方便，特别是当顶点数目较小的时候（n<=10）。这样，在处理每个顶点的时候，只需要从0到n-1遍历，检查是否相连，并且是否未被访问过。这样就能保证按照编号递增的顺序访问邻接点。

那邻接矩阵可能更适合这个题目，因为处理顺序容易控制。比如，假设用邻接矩阵存储，那么每个顶点x的邻接点就是所有y满足matrix[x][y]为true，并且y按照从小到大排列。所以在遍历的时候，只需要从0到n-1循环，判断是否是邻接点，并且是否已访问过。

所以，邻接矩阵可能更简单。

整个流程应该是这样的：对于DFS和BFS各需要处理一次：初始化访问数组，所有顶点未被访问。然后，按照顶点编号从小到大（从0到n-1）的顺序，逐个检查顶点是否被访问。如果未被访问，则从该顶点开始进行DFS或BFS，并将访问到的顶点记录下来，形成一个连通集。这样就能保证每个连通分量都是从其中最小的顶点开始遍历，并且在遍历过程中，邻接点按照编号递增的顺序被访问。

大致步骤如下：

1. 读取输入n和m。

2. 构建邻接矩阵。初始化n×n的二维数组，初始为false。然后读取m条边，将对应的两个顶点之间的边设为true。

3. 进行DFS遍历：

a. 初始化一个访问数组visited，所有元素初始为false。

b. 按照顶点编号从小到大遍历每个顶点i：

i. 如果未被访问，则开始DFS遍历，并将结果记录为一个连通集。

ii. 在DFS过程中，将访问的顶点按顺序保存，并在结束后输出。

4. 进行BFS遍历，同样的逻辑，但使用队列。

推荐代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;void DFS(int v, vector<bool>& visited, const vector<vector<bool>>& adj, vector<int>& component) {visited[v] = true;component.push_back(v);for (int i = 0; i < adj.size(); ++i) {if (adj[v][i] && !visited[i]) {DFS(i, visited, adj, component);}}
}void BFS(int v, vector<bool>& visited, const vector<vector<bool>>& adj, vector<int>& component) {queue<int> q;q.push(v);visited[v] = true;component.push_back(v);while (!q.empty()) {int current = q.front();q.pop();for (int i = 0; i < adj.size(); ++i) {if (adj[current][i] && !visited[i]) {visited[i] = true;component.push_back(i);q.push(i);}}}
}int main() {int n, m;cin >> n >> m;vector<vector<bool>> adj(n, vector<bool>(n, false));for (int i = 0; i < m; ++i) {int u, v;cin >> u >> v;adj[u][v] = true;adj[v][u] = true;}// DFSvector<bool> visited(n, false);for (int i = 0; i < n; ++i) {if (!visited[i]) {vector<int> component;DFS(i, visited, adj, component);cout << "{ ";for (int v : component) {cout << v << " ";}cout << "}" << endl;}}// BFSvisited.assign(n, false);for (int i = 0; i < n; ++i) {if (!visited[i]) {vector<int> component;BFS(i, visited, adj, component);cout << "{ ";for (int v : component) {cout << v << " ";}cout << "}" << endl;}}return 0;
}

自我实现代码

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>using namespace std;int n,m;
int g[15][15];
int vis[15];
vector<int>res;
queue<int>q;void dfs(int x)
{res.push_back(x);vis[x]=1;for(int i=1;i<=n;++i){if(g[x][i]==1&&!vis[i]){vis[i]=1;dfs(i);}}
}void bfs(int x)
{res.push_back(x);q.push(x);vis[x]=1;while(!q.empty()){int xx=q.front();q.pop();for(int i=1;i<=n;++i){if(g[xx][i]==1&&!vis[i]){res.push_back(i);vis[i]=1;q.push(i);}}}}int main()
{cin>>n>>m;int a,b;for(int i=1;i<=m;++i){cin>>a>>b;g[a+1][b+1]=1;g[b+1][a+1]=1;	}for(int i=1;i<=n;++i){if(!vis[i]){res.clear();dfs(i);cout<<"{";for(int i=0;i<res.size();++i){cout<<" "<<res[i]-1;}cout<<" }"<<endl;}}memset(vis,0,sizeof(vis));for(int i=1;i<=n;++i){if(!vis[i]){while(!q.empty())q.pop();res.clear();bfs(i);cout<<"{";for(int i=0;i<res.size();++i){cout<<" "<<res[i]-1;}cout<<" }"<<endl;}}return 0;
}