PTA 六度空间 思路分析及代码解析

2024-03-29 14:38

本文主要是介绍PTA 六度空间 思路分析及代码解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

PTA 7-7 六度空间 思路分析及代码解析 v0.98

  • 一、前导
    • 1. 需要掌握的知识
    • 2. 题目信息
  • 二、解题思路分析
    • 1. 题意理解
    • 2. 思路分析(重点)
  • 三、具体实现
    • 1. 弯路和bug
    • 2. 代码框架(重点)
      • 2.1 采用的数据结构
      • 2.2 程序主体框架
      • 2.3 各分支函数
    • 3. 完整编码
  • 四、参考资料

一、前导

1. 需要掌握的知识

  1. 图的存储和遍历。
  2. 了解六度空间理论:一个数学领域的猜想,你和任何一个陌生人之间所间隔的人不会超过六个,即:最多通过6个中间人你就能够认识任何一个陌生人

2. 题目信息

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

二、解题思路分析

1. 题意理解

  1. 输入数据
10 9	//10表示网络中的顶点数,9表示网络中存在的边数
1 2  //如下9行表示图中的边
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
  1. 输出数据:打印与该结点距离不超过6的结点数占结点总数的百分比,精确到小数点后两位
1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%
  1. 题意
    图的广度优先搜索的应用

2. 思路分析(重点)

  1. 通过二维数组存储图
  2. 典型的BFS遍历,参考树的层序遍历实现即可
  3. 如果使用的是C++,输出格式有点小麻烦

三、具体实现

1. 弯路和bug

  1. 不要忘记初始化,每个顶点统计完毕后都需要进行 /(ㄒoㄒ)/~~
  2. 统计结果的变量需要设定为double,初始值为1:因为自己也满足统计要求

2. 代码框架(重点)

2.1 采用的数据结构

二维数组存储图,提升了编码效率;如果想进一步提升,需要再试试链表

int a[max][max];
int dist[max];  //通过dist[]数组记录层数
bool visited[max]; //通过visited[]数组统计顶点是否被访问

2.2 程序主体框架

               程序伪码描述
int main()
{	1.创建图2.循环,每个顶点执行BFS()并按要求打印输出
}

2.3 各分支函数

  1. void bfs(int node); //广度遍历 核心函数
    1.1 通过dist[ ]数组统计结点对应的层数:源点=0,与源点有边的顶点属于1层,以此类推
    1.2 通过result变量统计符合要求的人数:初始值为1(因为包括自己)。
    另外,统计结果需要保留小数点后两位,因此result使用double类型。
    1.3 while( !q.empty() ) 核心语句,可以参考树的层序遍历理解:
    1.3.1 弹出一个顶点后,队列中收入和‘弹出顶点’存在‘边关系’的顶点。循环执行该动作
    1.3.2 边数达到7层后执行打印并返回 或者 循环结束(符合要求的顶点都已经遍历)后执行打印并返回
double result=1;void bfs(int node)
{dist[node]=0;visited[node]=true;q.push(node);while(!q.empty()){front=q.front();q.pop();for(int i=1;i<N+1;i++){if(a[front][i] && !visited[i]){q.push(i);visited[i]=true;dist[i]=dist[front]+1;if(dist[i]>6){Print(node,result);return;}result++;}}}Print(node,result);return;
}
  1. void Print(int node,double result);
    对于C++,打印有点小麻烦,需要iomanip的帮助
 #include <iomanip>
void Print(int node,double result)
{result = result/N*100;cout.setf(ios::fixed);cout<<node<<": "<<fixed<<setprecision(2)<<result<<"%"<<endl;
}
  1. void creat(); //先创建一个空图,然后填充好边;由于是无向图,边需要存储两次
void creat()
{cin>>N>>M; //N represent Node, M represent Edgefor(int i=0;i<max;i++)for(int j=0;j<max;j++)a[i][j]=0;int x,y;for(int k=0;k<M;k++){cin>>x>>y;a[x][y]=1;a[y][x]=1;}return;
}
  1. void Default(); //初始化函数
void Default()
{result=1;  //满足要求的人重置为1,因为自己也满足要求for(int i=0;i<max;i++){dist[i]==-1;  //dist[]数组用来标记范围visited[i]=false; //将所有结点重置为未访问}while(!q.empty()) //清空队列q.pop(); 
}

3. 完整编码

如果本文帮到了您,请点赞鼓励,您的鼓励是作者持续原创的动力,谢谢 😃

#include <iomanip>
#include <queue>
#include <iostream>
using namespace std;#define max 1001  //N<=1000 int a[max][max];
int N,M;
queue<int> q;
double result=1;int dist[max];
bool visited[max];
void bfs(int node);
void creat();
void Default();
void Print(int node,double result);int main()
{Default();creat();for(int i=1;i<N+1;i++){bfs(i);Default();}return 0;
}void bfs(int node)
{int front;dist[node]=0;visited[node]=true;q.push(node);while(!q.empty()){front=q.front();q.pop();for(int i=1;i<N+1;i++){if(a[front][i] && !visited[i]){q.push(i);visited[i]=true;dist[i]=dist[front]+1;if(dist[i]>6){Print(node,result);return;}result++;}}}Print(node,result);return;
}void Print(int node,double result)
{result = result/N*100;cout.setf(ios::fixed);cout<<node<<": "<<fixed<<setprecision(2)<<result<<"%"<<endl;
}void Default()
{result=1;for(int i=0;i<max;i++){dist[i]==-1;visited[i]=false;}while(!q.empty())q.pop();
}void creat()
{cin>>N>>M;for(int i=0;i<max;i++){dist[i]==-1;visited[i]=false;for(int j=0;j<max;j++){a[i][j]=0;}}int x,y;for(int k=0;k<M;k++){cin>>x>>y;a[x][y]=1;a[y][x]=1;}return;
}

四、参考资料

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

这篇关于PTA 六度空间 思路分析及代码解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/858859

相关文章

Oracle数据库常见字段类型大全以及超详细解析

《Oracle数据库常见字段类型大全以及超详细解析》在Oracle数据库中查询特定表的字段个数通常需要使用SQL语句来完成,:本文主要介绍Oracle数据库常见字段类型大全以及超详细解析,文中通过... 目录前言一、字符类型(Character)1、CHAR:定长字符数据类型2、VARCHAR2:变长字符数

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON(序列化)2.2 JSON 转对象(反序列化)3.

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.