【PTA】L3-01 六度空间_pta六度空间c

方法1：弗洛伊德算法

#include<iostream>
#include<iomanip>//c++用于格式化输出
#include<climits>
using namespace std;
 
int main() {
    int n, e;//顶点和边
    cin >> n >> e;
    //动态生成一个二维数组来保存图的边之间的信息
    //因为图的顶点一般是从1开始的，而数组是默认从0开始，所以需要定义n+1个空间
    int** G = new int* [n + 1];//动态定义二维数组的行
    for (int i = 0; i <= n; i++) {
        G[i] = new int[n + 1] {0};//动态定义二维数组的列，并初始化所有值为0
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j)G[i][j] = INT_MAX;//除了左对角线以外都先赋值为无穷大（这里采用int类型的最大值）
        }
    }
    //输入关联的边
    for (int i = 1; i <= e; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        G[v1][v2] = G[v2][v1] = 1;//无向图有双向边
    }
    //弗洛伊德算法：路径最短算法
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (G[i][k] != INT_MAX && G[k][j] != INT_MAX) {//防止两个数相加超过int的范围
                    if (G[i][k] + G[k][j] < G[i][j]) {//找到了更小的路径
                        G[i][j] = G[i][k] + G[k][j];//更新图的最小路径
                    }
                }
            }
        }
    }
    //输出
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 1; j <= n; j++) {
            if (G[i][j] <= 6)cnt++;
        }
        //c++的格式化函数setprecision(x),表示保留x为小数
        cout << i << fixed << setprecision(2) << ": " << 100.0 * cnt/n<<"%"<< endl;
    }
 
    //释放开辟的空间
    for (int i = 0; i <= n; i++) {
        if (G[i] != NULL) {
            delete[] G[i];
            G[i] = NULL;
        }
    }
    delete[] G;
    G = NULL;
}

方法2：图的广度优先遍历

#include<iostream>
#include<iomanip>//c++的格式化输出函数库
#include<queue>
using namespace std;
int n, e;//顶点和边
//图的广度优先遍历函数：返回值是满足六度空间的边的个数
int BFS(int v,int** G) {
	bool *visited = new bool[n + 1] {0};//记录顶点的遍历情况（0未遍历 1遍历过）
	queue<int>q;//定义一个队列
	q.push(v);
	visited[v] = true;
	//cnt记录满足6度空间边的个数，tail用于保存队列中的最后一个元素
	int cnt = 1, last = v, tail = v,level=1;//last保存的是队列中的第一个元素
	while (q.size()) {//队列不为空时进入循环
		int item = q.front();
		q.pop();
		for (int i = 1; i <= n; i++) {//遍历队列中第一个元素的每个关联的边
			if (G[i][item] && !visited[i]) {
				visited[i] = true;
				q.push(i);//将满足条件的顶点加入队列
				cnt++;//满足条件的边
				tail = i;//更新当前正在队列中的最后一个元素
			}
		}
		if (item == last) {//判断是否是本层最后一个节点
			last = tail;
			level++;
		}
		if (level > 6)break;
	}
	delete[]visited;//释放开辟的空间
	return cnt;
}
//六度空间输出函数
void SDS(int** G) {
	for (int i = 1; i <= n; i++) {
		int cnt = BFS(i, G);
		//setprecision(x),输出小数点后x位
		cout << i << fixed << setprecision(2) << ": " << 100.0 * cnt / n << "%" << endl;
	}
}
int main() {
	cin >> n >> e;
	int** G = new int* [n + 1];//定义二维数组的行
	for (int i = 0; i <= n; i++)
		G[i] = new int[n + 1] {0};//定义二维数组的列并赋值为0
	//输入边之间的关联
	for (int i = 1; i <= e; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		G[v1][v2] = G[v2][v1] = 1;//无向图有双向边
	}
	//调用函数
	SDS(G);
	//释放动态开辟的空间
	for (int i = 0; i <= n; i++) {
		if (G[i] != NULL) {
			delete[]G[i];
			G[i] = NULL;
		}
	}
	delete[] G;
	G = NULL;
 
	return 0;
}

参考代码：

7-1 六度空间 (PTA-数据结构)-CSDN博客

PTA 六度空间超详细题解-CSDN博客