当前位置:   article > 正文

PTA 六度空间超详细题解

PTA 六度空间超详细题解

首先给出题目链接:题目链接

这个题目的核心实现方法是通过BFS实现广度优先搜索遍历,但因为要求给出每个结点访问其他任意结点时符合六度空间的比例,我们应该在遍历的同时记录层数,也就是访问到一个结点时路径通过的结点数,这是抽象的概念,其实在具体情境里也就是通过了多少个人才联系上目标人。

伪代码是这样的:

void SDS(){
    for( each V in G ){
        count = BFS(V);
        //对图里的每个结点进行一次广度优先搜索
        Output ( count / N );
    }
}
int BFS( Vertex V ){
    visited[V] = true;
    count = 1;
    Enqueue(V, Q);
    while (!IsEmpty(Q)){
        V = Dequeue(Q);
        for ( V的每个邻接点W )
            if( !visited[W] ){
                visited[W] = true;
                Enqueue( W,Q );
                count++ ;
            }
    }
    return count;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

解释一下这段代码吧,光这样写就显得和陈越姥姥高度重合了,显得我很不专业,只会copy和paste。

首先SDS函数很好理解,就是遍历每个节点然后输出结果嘛。
那么重点就在于这个BFS是想做一个什么样的操作并返回一个什么样的东西。

理解题意之后,并不难发现这个count是符合要求的个数,用它去除以总数,就能得到符合六度空间理论的一个占比啦。

上面这段伪代码就是一个bfs框架套了一个计数的功能,bfs常用到的容器类型queue,也就是队列(这里我给学习c++的小伙伴推荐一个文档,可以很方便地查找到c++的STL函数,更重要的是他还是中文的!)

BFS由于是广度优先,所以他的核心就是以某个结点为中心,将和他关联的所有结点都先遍历一遍,打上visited的标记,直到和这个点相关的所有结点全部都被visited了,才会从和他i相关的第一个结点开始,再去遍历这个结点所有相关的子结点,其实也就可以抽象成一层一层地遍历。

count变量的作用,则是记录可以被访问到的结点数量。

如果不理解BFS的原理,那么请移步别的博客先搞懂BFS再来,笔者写这篇博文的主要目的是扫清本题里除了关于BFS的理解之外的其他可能问题,因此对BFS的讲解就比较粗略。

ok,搞懂了这个问题,你一定会觉得还有疑惑,就是为什么把点全部遍历了一遍呢,题目要求的不是六度以内的百分比吗。

这里我们就需要再引入几个指针来辅助我们解决问题了。可能因为笔者比较迟钝,听陈越姥姥的讲解还有一点云里雾里,所以在这里再说一说笔者的理解。

因为我们需要记录你在到达某个结点时是不是中间只通过了五个人,所以实际上遍历的层数包括起始结点在内,不可以超过6,一旦等于6,那么后续的结点就不用再计入count了,也就是说,我们应该在这时终止while循环。

陈越姥姥用的是level,last和tail。
level很好理解,就是层数嘛,那从一个结点开始就是1,但问题在于怎么增加这个level呢,什么情况下增加呢。对于第一个节点来说,自然是到它的所有相邻结点遍历完的时候该层结束,然后level可以加一,那么问题在于,如果是第二层上的某个结点,他的最后一个相邻结点不一定就代表这层结束了,为什么?

特地画了个图:
在这里插入图片描述

先看上面这幅,为了更加真实地体现这是一个图,我还有一些其他的点之间的边,但为了使讲解更加清晰,将不重要的边标成了灰色。

如果我们从1开始,去找1的六度顶点的话,如下图所示,为了防止干扰,我将本情况中不重要的边去掉,并将每层标成不同的颜色。

那么我们回到上面的问题,可以看到如果按照顺时针进行遍历,1的最后一个相邻结点是6,6也是这层的最后一个结点,那么在此时level应该+1变成2,但我们重新回到结点2去开始遍历时结点2的相邻节结点,第一个是1,但1已经被标记为visited了,所以下一个……2的最后一个结点是8,但8并不是蓝色这一层的最后一个结点,所以我们就不可以仅凭2的结点就判断这一层是否结束,我们需要两个指针。

在这里插入图片描述

一个指针是tailtail是更新得比较频繁的一个,每经过一个未被访问的结点,就将tail指向当前结点,由于队列先进先出,所以不必担心顺序上的错乱,tail一定是沿着顺时针移动的。

另一个指针是last。我们在最开始将last指针指向起始点,也就是1。然后每次循环完结点V所有相邻的结点后,判断当前的V是否等于last,如果等于last,那么就可以认为这一层已经结束,将level+1,并将last指向此时的tail

让我们来捋一下:起初,last指向的是1,在1的相邻结点全部遍历完时,判断last是否等于此时的V,也就是1,等于,此时tail指向的位置是6,那么我们可以将last指向6了。下一轮继续,当遍历完2的相邻结点时,发现tail指向8,但此时的V2,并不等于当前的last(6),因此我们就继续从队列中取出下一个元素3,然后继续遍历。

直到我们取到了V6的情况,此时的V终于等于last了,意味着这一层遍历结束,我们可以将level继续+1了,加完1还需要一步判断,就是level是否等于6?请注意,我们这里的level是在遍历完这一层后才更新的,也就是说level的意义实际上是已经走完了多少层,那么6层走完的时候,自然就可以退出这个while循环了。

最后,我们给出可以通过这道题的c++代码:

#include <iostream>
#include <queue>
#include <iomanip>
#include <algorithm>
using namespace std;
int N, M;

double BFS(int V,int** map) {
	int* visited = new int[N+1] {0};
	int level = 0,last=V,tail;
	visited[V] = 1;
	double count = 1;
	queue<int> q;
	q.push(V);
	while (!q.empty()) {
		int item = q.front();
		q.pop();
		for (int i = 1; i <= N; i++) {
			if (map[item][i]) {
				if (!visited[i]) {
					visited[i] = true;
					q.push(i);
					count++;
					tail = i;
				}
			}
		}
		if (item == last) {
			level++;
			last = tail;
		}
		if (level == 6)break;
	}
	return count;
}
void SDS(int** map) {
	double count;//不超过6的节点数
	for (int i = 1; i <= N; i++) {
		count = BFS(i, map);
		//对图里的每个结点进行一次广度优先搜索
		cout << i << ": " << fixed << setprecision(2) << count / (double)(N) *100<< '%' << endl;
	}
}
int main() {
	int start ,end;
	cin >> N >> M;
	int** map = new int* [N+1];
	for (int i = 0; i <= N; i++) {
		map[i] = new int[N+1]{0};
	}//建立图
	for (int i = 0; i < M; i++) {
		cin >> start >> end;
		map[start][end] = 1;
		map[end][start] = 1;
	}
	SDS(map);
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/677391
推荐阅读
相关标签
  

闽ICP备14008679号