【数据结构】广度优先遍历 最小转机问题

【数据结构】广度优先遍历 最小转机问题

题目描述:

小哼和小哈一同坐飞机去旅游，他们现在位于1号城市，目标是5号城市，可是0号城市并没有到4号城市的直航。

不过小哼已经收集了很多航班的信息，现在小哼希望找到一种乘坐方式，使得转机的次数最少，如何解决？

输入:

问题：

小哼和小哈一同坐飞机去旅游，他们现在位于1号城市，目标是5号城市，可是1号城市并没有到5号城市的直航。

不过小哼已经收集了很多航班的信息，现在小哼希望找到一种乘坐方式，使得转机的次数最少，如何解决呢?

验证数据：

5 7 0 4
0 1
0 2
1 2
1 3
2 3
2 4
3 4
第一行的5表示有5个城市(城市编号为1~5)，7表示有7条航线，0表示起点城市，4表示目标城市。

c++模板和typedef的原理一样吗?

回答1：
不一样，typedef就是定义类型的别名，是纯粹的语法糖；
模板则相当于把你实例化过的各写一遍，只是减少了代码量，但程序会膨胀。
回答2：
4 、与函数模板的区别
函数模板，可以传递类型参数给到模板，让其根据需要生成我们需要的函数代码，这些代码的特点是参数类型可以不同，但是函数名相同，这样就方便我们调用。详见：C++模板简介。

typedef定义的是指向某一类函数的指针，这一类函数的参数类型和返回值类型都是相同的，只是函数名不同，用指针的的方法，将相同参数类型，但函数名不同的函数统一起来，方便我们使用。

二者目的相同，都是为了实现编写代码的简洁，但途径有所不同，函数模板是从函数生成的角度出发，生成函数名一致参数不同的代码；typedef是将函数名不同，参数类型相同的函数名称用指针别名的方法统一起来。

main.cpp

#include"Graph.h"

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号到4号城市之间的最少转机次数为："< 
Graph.h 
#include
#include
const int MAX = 10;
typedef int DataType;

using namespace std;

class Graph {
private:
	DataType vertex[MAX]; //存放顶点的一维数组
	DataType arc[MAX][MAX]; //存放顶点间边关系的二维数组
	int arcNum, vertexNum; //边的个数，顶点个数
	int visited[MAX]; //访问数组

public:
	Graph(DataType v[],int n,int e,int vi[],int vj[]);

	int BFS();
};
 
Graph.cpp 
#include"Graph.h"

//有参构造函数的实现
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++)
		visited[i] = 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;
	}
}
int Graph::BFS(){
	
	int num = 0;//记录转机次数
	queueq;
	for(int i=0;i 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5579074.html