数据结构暑期自学--MOOC浙江大学pta(7-7 六度空间)

题目链接

典型的BFS，以前自学算法的时候，都是用的c++，这次挑战个c

1、如何判断一个点已经遍历到6度？

用last, level tail三个变量

last指当前层可以与v连接，且未访问过的最后一个结点

level 指层数

tail 每次更新，都保存着与v连接，且未访问过的结点

当last==v 说明当前取出的（Dequeue）的结点已经是该层（也就是上一层最后插入的）的最后一个结点，此时进入下一层（level++; last == tail）

2、每次判断前都要将以访问过的点，初始化。

# include 
# include 
# include 
int n, m;
int g[1000+10][1000+10];//存连接点，连接就为1，不连接为0 
int visited[1000+10];//判断是否访问过 
typedef struct queue *Queue;//建队列 
struct queue{
	int q[1100];
	int front;
	int rear;
};
Queue createq()
{
	Queue Q = (Queue)malloc(sizeof(struct queue));
	Q->front = -1;
	Q->rear = -1;
	return Q;
}
void Enqueue(int x, Queue Q)
{
	Q->q[++Q->rear] = x;
}
int Dequeue(Queue Q)
{
	return Q->q[++Q->front];
}
int emptyq(Queue Q)
{
	if (Q->front==Q->rear)
	return 1;
	else
	return 0;
}
int isconnected(int x, int v) //判断两点是否连接 
{
	if (g[x][v])
	return 1;
	else
	return 0;
}
double BFS(int v)
{
	visited[v] = 1;
	int last = v;
	int level = 0;
	int count = 1;
	int tail = 0;
	Queue Q;
	Q = createq();
	Enqueue(v, Q);
	while (!emptyq(Q))
	{
		v = Dequeue(Q);
		for (int i=1; i<=n; i++)
		{
			if (!visited[i]&&isconnected(i, v))//判断所有与v连接的点，且未访问过的点 
			{
				visited[i] = 1;
				Enqueue(i, Q);
				count++;
				tail = i;
			}
		}
		if (v==last)
		{
			last = tail;
			level++;
		}
		if (level==6)
		break;
	}
	return count;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		g[x][y] = 1;
		g[y][x] = 1;
	}
	for (int i=1; i<=n; i++)
	{
		memset(visited, 0, sizeof(visited));//每次判断都要重新清零 
		double num = BFS(i);
		printf("%d: %.2lf", i, num/n*100);
		printf("%%n");
	}
	
	
	return 0;
 }