刷题时间：2021/04/02-2021/04/未完待续
数据结构实验之图论
一：基于邻接矩阵的广度优先搜索遍历
Description
给定一个无向连通图，顶点编号从0到n-1，用广度优先搜索(BFS)遍历，输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点，节点编号小的优先遍历）
Input
输入第一行为整数n（0< n <100），表示数据的组数。
对于每组数据，第一行是三个整数k，m，t（0＜k＜100，0＜m＜(k-1)*k/2，0＜ t＜k），表示有m条边，k个顶点，t为遍历的起始顶点。
下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。
Output
输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示BFS的遍历结果。
Sample
Input
1
6 7 0
0 3
0 4
1 4
1 5
2 3
2 4
3 5
Output
0 3 4 2 5 1
Hint
以邻接矩阵作为存储结构。
我的思路
广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。
深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。
二者区别：
深度优先搜素算法：不全部保留结点，占用空间少；有回溯操作(即有入栈、出栈操作)，运行速度慢。
广度优先搜索算法：保留全部结点，占用空间大； 无回溯操作(即无入栈、出栈操作)，运行速度快。
通常 深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用空间较少。
所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。
广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。
但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些
参考代码
#include <bits/stdc++.h>
using namespace std;
int a[110][110];//二维数组表示邻接矩阵
int p[110];//标记节点是否访问过
int b[110];//存储遍历节点栈
int k,m,t,u,v;
int top,low;//top栈顶,low bfs()
void bfs(int i){
for(int j=0;j<k;j++){
if(a[i][j]==1&&p[j]==0){//i通j并且j未被访问过
b[top++]=j;//把j进栈
p[j]=1;//把j标记
}
}
if(low<=top){
bfs(b[++low]);//每次bfs后，对下一个节点进行bfs
}
}
int main()
{
int n;
cin>>n;
while(n--){
cin>>k>>m>>t;
for(int i=0;i<m;i++){
cin>>u>>v;
a[u][v]=1;
a[v][u]=1;
}
top=0;
low=0;
b[top++]=t;//把第一个元素进栈
p[t]=1;//标记
bfs(t);
for(int i=0;i<k;i++){
if(i!=k-1){
cout<<b[i]<<" ";
}else {
cout<<b[i]<<endl;
}
}
}
return 0;
}
二：图的深度遍历
Description
请定一个无向图，顶点编号从0到n-1，用深度优先搜索(DFS)，遍历并输出。遍历时，先遍历节点编号小的。
Input
输入第一行为整数n（0 < n < 100），表示数据的组数。 对于每组数据，第一行是两个整数k,m（0 ＜ k ＜ 100，0 ＜ m ＜ k*k），表示有m条边，k个顶点。 下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。
Output
输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示DFS的遍历结果。
Sample
Input
1
4 4
0 1
0 2
0 3
2 3
Output
0 1 2 3
参考代码
#include <bits/stdc++.h>
using namespace std;
int a[110][110];
int p[110];
int k,m,u,v;
//深度遍历，递归
void dfs(int i){
for(int j=0;j<k;j++){//遍历k个节点
if(a[i][j]==1&&p[j]==0){//i->j通路并且j未被标记
cout<<" "<<j;
p[j]=1;//标记
dfs(j);
}
}
}
int main()
{
int n;
cin>>n;
while(n--){
cin>>k>>m;
memset(a,0,sizeof(a));//初始化
memset(p,0,sizeof(p));
for(int i=0;i<m;i++){
cin>>u>>v;
a[u][v]=1;
a[v][u]=1;
}
cout<<0;//把第一个输出
p[0]=1;//把第一个标记
dfs(0);
cout<<endl;
}
return 0;
}
三：判断可达性
Description
在古老的魔兽传说中，有两个军团，一个叫天灾，一个叫近卫。在他们所在的地域，有n个隘口，编号为1..n，某些隘口之间是有通道连接的。其中近卫军团在1号隘口，天灾军团在n号隘口。某一天，天灾军团的领袖巫妖王决定派兵攻打近卫军团，天灾军团的部队如此庞大，甚至可以填江过河。但是巫妖王不想付出不必要的代价，他想知道在不修建任何通道的前提下，部队是否可以通过隘口及其相关通道到达近卫军团展开攻击。由于n的值比较大（n<=1000），于是巫妖王找到了擅长编程的你 =_=，请你帮他解决这个问题，否则就把你吃掉变成他的魔法。为了拯救自己，赶紧想办法吧。
Input
输入包含多组，每组格式如下。
第一行包含两个整数n,m（分别代表n个隘口，这些隘口之间有m个通道）。
下面m行每行包含两个整数a，b；表示从a出发有一条通道到达b隘口（注意：通道是单向的）。
Output
如果天灾军团可以不修建任何通道就到达1号隘口，那么输出YES，否则输出NO。
Sample
Input
2 1
1 2
2 1
2 1
Output
NO
YES
参考代码
#include <bits/stdc++.h>
using namespace std;
int ab[1010][1010];//邻接矩阵
int p[1010];//标记访问节点
int n,m,a,b;
//深度遍历
void dfs(int i){
for(int j=0;j<n;j++){
if(ab[i][j]==1&&p[j]==0){
p[j]=1;
dfs(j);
}
}
}
int main()
{
while(cin>>n>>m){
memset(ab,0,sizeof(ab));
memset(p,0,sizeof(p));
for(int i=0;i<m;i++){
cin>>a>>b;
ab[a][b]=1;
}
p[n]=1;
dfs(n);
if(p[1]==1){//只要被标记过就是深度可以到达
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
return 0;
}
四：迷宫探索
Description
有一个地下迷宫，它的通道都是直的，而通道所有交叉点(包括通道的端点)上都有一盏灯和一个开关；请问如何从某个起点开始在迷宫中点亮所有的灯并回到起点？
Input
连续T组数据输入，每组数据第一行给出三个正整数，分别表示地下迷宫的结点数N(1 < N <= 1000)、边数M(M <= 3000)和起始结点编号S，随后M行对应M条边，每行给出一对正整数，表示一条边相关联的两个顶点的编号。
Output
若可以点亮所有结点的灯，则输出从S开始并以S结束的序列，序列中相邻的顶点一定有边，否则只输出部分点亮的灯的结点序列，最后输出0，表示此迷宫不是连通图。
访问顶点时约定以编号小的结点优先的次序访问，点亮所有可以点亮的灯后，以原路返回的方式回到起点。
Sample
Input
1
6 8 1
1 2
2 3
3 4
4 5
5 6
6 4
3 6
1 5
Output
1 2 3 4 5 6 5 4 3 2 1
Hint
参考代码
#include <bits/stdc++.h>
using namespace std;
int a[1010][1010];
int p[1010];
int b[1010];
int n,m,top;
//深度遍历
void dfs(int i){
b[top++]=i;//遍历开始入栈
p[i]=1;
for(int j=0;j<=n;j++){
if(a[i][j]==1&&p[j]==0){
dfs(j);
b[top++]=i;//这个遍历结束再次入栈，就会形成‘金字塔’（瞎起的名字）
}
}
}
int main()
{
int t;
int s,x,y;
cin>>t;
while(t--){
cin>>n>>m>>s;
memset(a,0,sizeof(a));//初始化
memset(p,0,sizeof(p));
memset(b,0,sizeof(b));
for(int i=0;i<m;i++){
cin>>x>>y;
a[x][y]=1;
a[y][x]=1;
}
top=0;
dfs(s);
for(int i=0;i<top;i++){
if(i==0){
cout<<b[i];
}else{
cout<<" "<<b[i];
}
}
if(top!=2*n-1){
cout<<" "<<0;
}
cout<<endl;//额，最后输出回车吧。。。
}
return 0;
}
五：从起始点到目标点的最短步数（BFS）
Description
在古老的魔兽传说中，有两个军团，一个叫天灾，一个叫近卫。在他们所在的地域，有n个隘口，编号为1..n，某些隘口之间是有通道连接的。其中近卫军团在1号隘口，天灾军团在n号隘口。某一天，天灾军团的领袖巫妖王决定派兵攻打近卫军团，天灾军团的部队如此庞大，甚至可以填江过河。但是巫妖王不想付出不必要的代价，他想知道在不修建任何通道的前提下，部队是否可以通过隘口及其相关通道到达近卫军团展开攻击；如果可以的话，最少需要经过多少通道。由于n的值比较大（n<=1000），于是巫妖王找到了擅长编程的你 =_=，请你帮他解决这个问题，否则就把你吃掉变成他的魔法。为了拯救自己，赶紧想办法吧。
Input
输入包含多组，每组格式如下。
第一行包含两个整数n,m（分别代表n个隘口，这些隘口之间有m个通道）。
下面m行每行包含两个整数a，b；表示从a出发有一条通道到达b隘口（注意：通道是单向的）。
Output
如果天灾军团可以不修建任何通道就到达1号隘口，那么输出最少经过多少通道，否则输出NO。
Sample
Input
2 1
1 2
2 1
2 1
Output
NO
1
参考代码
不能用DFS，得用BFS，得到每一步的最小值
#include <bits/stdc++.h>
using namespace std;
int ab[1010][1010];//邻接矩阵
int vis[1010];//标记节点是否访问过
int p[1010];//输出栈
int sum[1010];//到n节点最短距离
int n,m;
void bfs(int i){
int top=0,low=0;
p[top++]=i;//进栈
vis[i]=1;//标记
sum[i]=0;//自己距离自己为0
while(low<top){
int p1=p[low++];//当前根节点
for(int j=n;j>=1;j--){
if(ab[p1][j]==1&&vis[j]==0){//i->j连通&&j未被访问
p[top++]=j;//进栈
vis[j]=1;
if(sum[p1]<=sum[j]){
sum[j]=sum[p1]+1;
}
}
}
}
if(sum[1]==0x3f3f3f3f){
cout<<"NO"<<endl;
}else{
cout<<sum[1]<<endl;
}
}
int main()
{
while(cin>>n>>m){
memset(ab,0,sizeof(ab));//初始化
memset(vis,0,sizeof(vis));
memset(p,0,sizeof(p));
memset(sum,0x3f3f3f3f,sizeof(sum));//伪无穷大
//0x3f3f3f3f的十进制是1061109567，
//是10^9级别的（和0x7fffffff一个数量级），
//而一般场合下的数据都是小于10^9的，
//所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
ab[a][b]=1;
}
bfs(n);
}
return 0;
}
六：村村通公路
Description
当前农村公路建设正如火如荼的展开，某乡镇政府决定实现村村通公路，工程师现有各个村落之间的原始道路统计数据表，表中列出了各村之间可以建设公路的若干条道路的成本，你的任务是根据给出的数据表，求使得每个村都有公路连通所需要的最低成本。
Input
连续多组数据输入，每组数据包括村落数目N(N <= 1000)和可供选择的道路数目M(M <= 3000)，随后M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个村庄的编号和修建该道路的预算成本，村庄从1～N编号。
Output
输出使每个村庄都有公路连通所需要的最低成本，如果输入数据不能使所有村庄畅通，则输出-1，表示有些村庄之间没有路连通。
Sample
Input
5 8
1 2 12
1 3 9
1 4 11
1 5 3
2 3 6
2 4 9
3 4 4
4 5 6
Output
19
Hint
参考代码
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f//默认地图各点之间不连通，即无穷大
int vis[1010];//标记数组，看某个点是否被访问
int MAP[1010][1010];//邻接矩阵
int dis[1010];//到这个节点的min权值
int n;
void prim(){
int flag = 1;
for(int i=1;i<=n;i++){
dis[i] = MAP[1][i];
}
dis[1] = 0;//1距离1为0
vis[1] = 1;//标记1
int sum = 0;
for(int i=1;i<n;i++){
int now = INF;
int MIN = INF;
for(int j=1;j<=n;j++){//遍历循环找到可收纳进集合的最小权边
if(vis[j]==0&&dis[j]<MIN){
now = j;
MIN = dis[j];
}
}
if(MIN == INF){//不连通，不存在最小生成树
flag = 0;
break;
}
vis[now] = 1;//将此点收纳进集合
sum+=MIN;
for(int j=1;j<=n;j++){
if(vis[j]==0&&MAP[now][j]<dis[j]){//更新可收纳进集合的边权
dis[j]=MAP[now][j];
}
}
}
if(flag){
cout<<sum<<endl;
}else{
cout<<"-1"<<endl;
}
}
int main()
{
int m;
while(cin>>n>>m){
memset(MAP,0x3f3f3f,sizeof(MAP));//初始化无穷大
memset(vis,0,sizeof(vis));//初始化标记数组
for(int i=0;i<m;i++){
int u,v,c;
cin>>u>>v>>c;
MAP[u][v] = MAP[v][u] = c;
}
prim();//普利姆算法Prim
}
return 0;
}
评论区