Global variables.h(全局变量的声明):
//存放全局变量的声明,注意加extern
extern int Graph[100][100]; //邻接矩阵
extern int V, W; //点和边
extern int visited[100]; //判断是否访问
Global variables.cpp(全局变量的设置):
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include"Global variables.h"
//设置全局变量
int Graph[100][100]; //邻接矩阵
int V, W; //点和边
int visited[100]; //判断是否访问
head.h(头文件):
void BuildGraph();
void SDS();
int BFS(int v);
head.cpp(头文件中函数的实现):
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include"head.h"
#include"Global variables.h"
void BuildGraph() { //建立图
int i, j, n1, n2;
for (i = 0; i < V; i++) { //初始化
for (j = 0; j < V; j++) {
Graph[i][j] = 0;
}
}
for (i = 0; i < W; i++) { //建立图
scanf("%d%d", &n1, &n2);
Graph[n1][n2] = 1;
Graph[n2][n1] = 1;
}
}
void SDS() {
int i, j;
float rate;
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++)
visited[j] = 0;
rate = (float)BFS(i) / V;
printf("%d: %.2f%%\n", i + 1, rate * 100);
}
}
int BFS(int v) {
int cnt = 1, level = 0, last = v, i, n, tail;
int que[1000] = {}, rear, front; //模拟队列
rear = front = 0;
visited[v] = 1;
que[rear] = v;
rear++;
while (rear > front) {
n = que[front];
front++;
for (i = 0; i < V; i++) {
if (visited[i] == 0 && Graph[n + 1][i + 1] == 1) {
visited[i] = 1;
que[rear] = i;
rear++;
cnt++;
tail = i;
}
}
if (n == last) {
level++;
last = tail;
}
if (level == 6) {
break;
}
}
return cnt;
}
ceshi1.cpp(主函数):
#define _CRT_SECURE_NO_WARNINGS //六度空间
#include<stdio.h>
#include<stdlib.h>
#include"head.h"
#include"Global variables.h"
int main() {
scanf("%d%d", &V, &W);
BuildGraph();
SDS();
return 0;
}
测试结果: