PTA 列出连通集 思路分析及代码解析

本文主要是介绍PTA 列出连通集 思路分析及代码解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、前导

1. 需要掌握的知识

图的存储和遍历、树的层序遍历、堆栈和队列

2. 题目信息

题目来源：PTA / 拼题A
题目地址：https://pintia.cn/problem-sets/15/problems/714

二、解题思路分析

1. 题意理解

基础题，存储图并通过深度优先和广度优先分别进行遍历

1. 输入数据

8 6	\\ 8代表图的顶点数；6代表图的边数，下面6行表示边
0 7
0 1
2 0
4 1
2 4
3 5

2. 输出数据

{ 0 1 4 2 7 } \\先进行DFS、再进行BFS，按指定格式{ x y z }即可输出
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

3. 题意
   先存储图，然后遍历图中的元素

2. 思路分析（重点）

1. 可以考虑用二维数组或链表来存储图。使用二维数组的话，编码比较容易。后面有时间的话，我会再通过链表存储试试
2. 顶点从0到 N-1编号

三、具体实现

1. 弯路和bug

1. DFS后，注意将结点初始化为未访问状态

2. 代码框架（重点）

2.1 采用的数据结构

#define max 10
int a[max][max]; //为提高解题速度，通过二维数组存储数据 且 二维数组a为全局变量
bool visited[max];	//visited[]数组用来标记元素是否已访问

2.2 程序主体框架

               程序伪码描述
int main()
{	1.创建图并完成元素的存储;2.dfs();3.bfs();
}

2.3 各分支函数

1. void creat(); 创建图并完成元素存储；对于无向图，边需要存储两次

void creat()
{cin>>N>>E; //顶点数和边数for(int i=0;i<N;i++) //创建一个空图{for(int j=0;j<N;j++)a[i][j]=0;visited[i]=false; 	}int x,y;for(int k=0;k<E;k++) //录入边{cin>>x>>y;a[x][y]=1;a[y][x]=1;}
}

2. bool isEdge(int start,int end); 判定两个结点间是否有边

bool isEdge(int start,int end)
{if(a[start][end]) return true;else return false;
}

3. void dfs(int node); 深度优先遍历的递归实现：代码简洁易懂

void dfs(int node) //deep first search
{visited[node]=true;cout<<node<<" ";for(int i=0;i<N;i++){if(isEdge(node,i) && !visited[i])dfs1(i); }return;
}

4. void dfs(int node); 方法二，通过堆栈实现DFS

void dfs(int node) //deep first search 
{visited[node]=true;s.push(node); //stack<int> s; cout<<node<<' ';front=s.top();int i;while(!s.empty()){for(i=0;i<N;i++){if(isEdge[front][i] && !visited[i]){visited[i]=true;s.push(i);cout<<i<<' ';front=s.top();break;}}if(i==N) // i==N,意味着找不到邻接点了,这条深度优先路径走到头了{s.pop();if(s.empty()) return; front=s.top(); }}return;
}

5. void bfs(int node); 参照树的层序遍历，通过队列实现BFS：一层层的收入元素，按照先进先出的顺序弹出

void bfs(int node) //breadth first search
{visited[node]=true;q.push(node); //q equal queuewhile(!q.empty()){front=q.front();q.pop();cout<<front<<" ";for(int i=0;i<N;i++){if(isEdge[front][i] && !visited[i]){visited[i]=true; q.push(i);}}	}return;
}

3. 完整编码

#include <stack>
#include <queue>
#include <iostream>
using namespace std;#define max 10
int a[max][max];
bool visited[max];int N,E;queue<int> q;
stack<int> s;void creat(); 
void bfs(int node);
void dfs(int node);
bool isEdge(int start,int end);int main()
{creat();for(int i=0;i<N;i++)if(!visited[i]){cout<<"{ "; dfs(i); cout<<"}"<<endl;}for(int i=0;i<N;i++) { visited[i]=false; }for(int i=0;i<N;i++){if(!visited[i]) {cout<<"{ "; bfs(i);cout<<"}"<<endl;}	}return 0;
}void dfs(int node) //deep first search
{visited[node]=true;cout<<node<<" ";for(int i=0;i<N;i++){if(isEdge(node,i) && !visited[i])dfs(i); }return;
}bool isEdge(int start,int end)
{if(a[start][end]) return true;else return false;
}void creat()
{cin>>N>>E;for(int i=0;i<N;i++){for(int j=0;j<N;j++)a[i][j]=0;visited[i]=false; 	}int x,y;for(int k=0;k<E;k++){cin>>x>>y;a[x][y]=1;a[y][x]=1;}
}void bfs(int node) //breadth first search
{int front;visited[node]=true;q.push(node);while(!q.empty()){front=q.front();q.pop();cout<<front<<" ";for(int i=0;i<N;i++){if(isEdge(front,i) && !visited[i]){visited[i]=true; q.push(i);}}	}return;
}

2021.10.19 ：应试流解法

#include <queue>
#include <iostream>
using namespace std;#define MAX 10
int a[MAX][MAX] = { 0 };
int checked[MAX] = { 0 };
int N, M;void DFS(int Start);
void BFS(int Start);int main()
{cin >> N>>M;int x, y;for (int i = 0; i < M; i++){cin >> x >> y;a[x][y] = 1;a[y][x] = 1;}for (int i = 0; i < N; i++){if (!checked[i]){cout << "{";DFS(i);cout << " }" << endl;}}for (int i = 0; i < N; i++)checked[i] = false;for (int i = 0; i < N; i++){if (!checked[i]){cout << "{";BFS(i);cout << " }" << endl;}}return 0;
}void DFS(int Start)
{checked[Start] = true;cout << " " << Start;for (int i = 0; i < N; i++)if (a[Start][i] && !checked[i])DFS(i);return;
}void BFS(int Start)
{queue<int> q; int Front;q.push(Start); checked[Start] = true;while (!q.empty()){Front = q.front();q.pop();cout << " " << Front;for (int i = 0; i < N; i++){if (a[Front][i] && !checked[i]){q.push(i);checked[i] = true;}}						}return;
}

四、参考

1. 浙江大学 陈越、何钦铭老师主讲的数据结构

这篇关于PTA 列出连通集 思路分析及代码解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---