算法期中考试题目+代码

【题目】据美国动物分类学家内斯特·迈尔推算，世界上有超过100万种动物，各种动物都有自己的语言，假设动物A可以与动物B进行通信，但它不能与动物C通信，动物C只能与动物B通信，所以动物A、B之间的通信需要动物B来当翻译，问两个动物之间相互通信至少需要多少个翻译。

C++版代码

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define MAXV 4

//问题表示
int A[MAXV][MAXV];					//图的邻接矩阵
int n,m,k;
int sno,eno;
int visited[MAXV];
struct NodeType
{
	int vno;						//顶点编号
	int length;						//路径长度
};
int bfs(int sno,int eno)			//广度优先搜索算法
{
	if (sno==eno) return 0;
	NodeType e,e1;
	queue<NodeType> qu;				//定义队列
	e.vno=sno;
	e.length=0;
	qu.push(e);						//结点e进队
	visited[e.vno]=1;
	while (!qu.empty())				//队列不空循环
	{
		e=qu.front(); qu.pop();		//出队结点e
		if(e.vno==eno) 
			return e.length-1;
		for(int j=0;j<n;j++)
		{
			if(A[e.vno][j]!=0)		//到顶点j有边
			{
				if(visited[j]==0)
				{
					e1.vno=j;
					e1.length=e.length+1;
					qu.push(e1);
					visited[j]=1;
				}
			}
		}
	}
	return -1;
}
int main()
{
	while (scanf_s("%d%d",&n,&m)==2)
	{
		int a,b,i;
		memset(A,0,sizeof(A));
		memset(visited,0,sizeof(visited));
		for(i=0;i<m;i++)			//根据输入建立邻接矩阵
		{
			scanf_s("%d%d",&a,&b);
			A[a][b]=1;				//无向图
			A[b][a]=1;
		}
		scanf_s("%d",&k);
		for(i=0;i<k;i++)
		{
			scanf_s("%d %d",&sno,&eno);
			printf("%d\n",bfs(sno,eno));
		}
	}
	return 0;
}