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的结点就判断这一层是否结束，我们需要两个指针。

一个指针是tail，tail是更新得比较频繁的一个，每经过一个未被访问的结点，就将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，但此时的V是2，并不等于当前的last(6)，因此我们就继续从队列中取出下一个元素3，然后继续遍历。

直到我们取到了V为6的情况，此时的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