PTA 7-6 列出连通集
题目详情：
给定一个有 n 个顶点和 m 条边的无向图，请用深度优先遍历（DFS）和广度优先遍历（BFS）分别列出其所有的连通集。假设顶点从 0 到 n−1 编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:
输入第 1 行给出 2 个整数 n (0<n≤10) 和 m，分别是图的顶点数和边数。随后 m 行，每行给出一条边的两个端点。每行中的数字之间用 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 }题目解析
逐步分析
首先，图的表示方式。顶点数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;
}
// DFS
vector<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;
}
}
// BFS
visited.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;
}