最少转机问题

#include<iostream>
using namespace std;
#include<queue>
const int MAX = 10; //图的最大顶点个数为10
typedef int DataType;
class Graph 
{
private:
	//边的个数
	int arcNum;
	//顶点个数
	int vertexNum;
	//定义一个存放顶点的一位数组
	DataType vertex[MAX];
	//定义一个存放顶点间的边关系的二维数组
	int arc[MAX][MAX];
	//访问数组
	int visit[MAX];
public:
	//v[]数组存放用户输入的一维数组的顶点数据，n表示顶点个数，e是边的个数
	Graph(DataType v[], int n, int e,int VI[],int VJ[]);
    //BFS----广度优先遍历
	int BFS();
};
//有参构造函数的实现
Graph::Graph(DataType v[], int n, int e,int VI[],int VJ[])
{
	//初始化顶点个数
	vertexNum = n;
	//初始化边的个数
	arcNum = e;
	//初始化顶点数组
	for (int i = 0; i <n; i++)
	{
		vertex[i] = v[i];
	}
	//初始化边数组
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			arc[i][j] = 0;
	//初始化访问数组
	for (int i = 0; i < MAX; i++)
		visit[i] = 0;//一开始所有节点都处于未被访问的状态

	//由用户来决定，哪两个顶点之间存在边
	int vi=0, vj=0;
	for (int i = 0; i < arcNum; i++)
	{
		//两个顶点之间的边关系
		int vi = VI[i];
		int vj = VJ[i];
		cout << vi << "<---->" << vj << endl;
		//这是无向图的边初始化标志
		arc[vi][vj] = 1;//有边的标志
		arc[vj][vi] = 1;
	}
}
//BFS-----广度优先遍历
int Graph::BFS()
{
	int num = 0;//记录转机次数
	queue<DataType> q;//队列存储的是顶点信息
	//外层for循环，检查是否每个节点都被访问过，防止存在节点未被访问过
	for (int i = 0; i < vertexNum; i++)
	{
		if (visit[i]==0)//如果当前节点没有被访问过就进行处理
		{
			//设置当前节点被访问过
			visit[i] == 1;
			cout << vertex[i]<<" ";
			//说明找到了四号城市，退出当前遍历过程
			if (vertex[i] == 3)
			{
				return num;
			}
			//将此顶点入队
			q.push(vertex[i]);
			//若当前队列不为空---表示当前顶点还存在邻接点没有被访问过
			while (!q.empty())
			{   
	
				q.pop();//队头元素出队
				//遍历当前顶点在邻接矩阵中当前行，找找是否存在未被访问过的顶点
				for (int j = 0; j < vertexNum; j++)
				{
					//当前两个顶点之间有边   当前顶点的邻接点未被访问过
					if (arc[i][j] == 1 && visit[j] == 0)
					{
						//将找到的此节点标志设置为已经访问
						visit[j] = 1;
						//输出这两个被边连接的顶点
						cout <<vertex[j] <<" ";
		
						//找到一个邻接点，次数++
						num++;
						//将找到的此节点入队
						//每次把当前顶点入队都是为了得到它的邻接点，并判断是否被访问过
						q.push(vertex[j]);
					}
					//找到的当前邻接点为4号城市,退出遍历
					if (vertex[j] == 3)
					{
						return num;
					}
				}
			}

		}
	}
	//0号城市和4号城市之间不存在航线可以抵达
	return -1;
}
//测试-------------------
void test()
{
	//存储两个顶点之间边关系的数组
	int VI[14] = {0,0,2,2,2,3,3};
	int VJ[7] = { 1,2,1,4,3,1,4 };
	DataType v[5] = { 0,1,2,3,4 };
	cout << "存在航线的城市有：" << endl;
	Graph p(v, 5, 7,VI,VJ);
	cout << "输出所有城市:" << endl;
	int num=p.BFS();
	cout << endl;
	cout << "0号到3号城市之间的最少转机次数为："<<num << endl;
}
int main()
{
	
	test();
	system("pause");
	return 0;
}