开课实验室：计算机科学与工程实验(电子楼)       2020年12月17日

学院	计算机科学与网络工程学院		年级、专业、班	网络工程194	姓名	jwt	学号
实验课程		数据结构实验					成绩
实验项目		实验三 图的操作与实现					指导老师

一、实验目的

1、线性表的链表实现：遍历、查找、插入、删除、翻转

2、栈的链式存储结构实现：入栈、出栈

3、队列的链式存储结构的实现：入队、出队

4、线性表、栈和队列的应用实现

二、使用仪器、器材

操作系统：Win10

编程软件：C++

三、实验内容及原理

1、图的邻接表和邻接矩阵存储

建立下图的邻接表或邻接矩阵，并输出之。

思路: (邻接矩阵)采用二维数组来存储顶点之间的相邻关系，若两个顶点之间有直连边，则在数组对应位置赋予相应的权值(自身到自身的权值设置为0)，若两个顶点之间没有直连边,则赋予32267，即int型的最大值，意为无穷大；在输入各边的权值时，写了一个找到顶点对应位置的函数，返回顶点对应的下标，这样输入时就能把权值赋予对应的位置。定义一个结构体,结构体属性包括邻接矩阵、存储顶点信息的数组、边数、顶点数。输出用二重循环即可。

2、图的各种遍历算法实现

以0结点为起点实现上述图的深度优先和广度优先遍历算法。

思路:（深度优先遍历）用寻找顶点下标的函数返回‘0’的下标，然后开始遍历。采用递归的方式，在邻接矩阵中，找到第一个邻接边，然后又从另一顶点开始，依次递归下去（访问过的顶点用visited[]数组记录），直到所有顶点均已被遍历。

（广度优先遍历）访问起点的所有邻接点，然后从近到远（即下标从小到大）再访问邻接点的所有邻接点，直到遍历完成。

3、最小生成树的算法实现

利用普里姆(Prim)算法或克鲁斯卡尔(Kruskal)算法求上图的最小生成树，算法实现代码必须有注释。

思路：（普里姆算法）假设有两个集合，一个U，一个V-U，初始时，U里只有起点u1，V-U则为其余顶点，在V-U中寻找权值最小的（u1，vi），然后把vi加入到U，该边对应也加入到最小生成树中，依次类推最终可以得到n个顶点n-1条边的最小生成树。

4、最短路径的算法实现

利用狄克斯特拉(Dijkstra)算法求上图中0结点到其它结点的最短路径，算法实现代码必须有注释。

思路：设有两个集合，一个U，一个V-U；一维数组dist[]用于存储起点到各顶点的最短路径长度；一维数组path[]用于存储最短路径。初始时，U里只有起点u1，V-U则为其余顶点，dist[]数组置为起点的邻接信息。从V-U中寻找较小的顶点（即从dist的值较小的顶点），将它添加到U中，考查该顶点的邻接信息，若该顶点与其他顶点之间有边，则与原定最短路径长度进行比较，新路径插入了中间点，（如新路径0-1-2与原路径0-2比较）更新最短路径长度（如dist[i]）为较小者。重复上述步骤，直到U中包含所有顶点。

四、实验过程原始数据记录

题目1：图的邻接表和邻接矩阵存储

#define MaxInt 32767
#define MAX 50
bool visited[MAX]; //访问标志数组，其初值为"false" 
typedef struct
{
	int vexs[MAX];            		//顶点表 
	int arcs[MAX][MAX];      		//邻接矩阵 
	int vexnum, arcnum;              //图的当前点数和边数 
}AMGraph;
int findVex(AMGraph G, int c)//查找顶点位置
{
	for (int i = 0; i < G.vexnum; i++)
		if (G.vexs[i] == c)//找到该元素
			return i;
	cout << "图中没有该结点" << endl;
	return -1;
}
void createAdj(AMGraph& G)//用邻接矩阵存储无向图
{
	int i, j, k;
	cout << "------------------邻接矩阵的创建-------------------" << endl;
	cout << endl;
	cout << "请输入顶点数：";
	cin >> G.vexnum;
	cout << "请输入边数： ";
	cin >> G.arcnum;
	for (i = 0; i < G.vexnum; i++)//初始化邻接矩阵，对角线权值赋予0，没有直连边则赋予最大值
	{
		for (j = 0; j < G.vexnum; j++)
		{
			if (i == j)//对角线置0 
				G.arcs[i][j] = 0;
			else//没有直连边则赋予最大值
				G.arcs[i][j] = MaxInt;
		}
	}
	cout << endl;
	cout << "------------------顶点信息的录入-------------------" << endl;
	cout << endl;
	cout << "请输入顶点标号： " << endl;
	for (i = 0; i < G.vexnum; i++)//输入各个顶点
		cin >> G.vexs[i];
	cout << endl;
	cout << "------------------邻接矩阵的录入-------------------" << endl;
	cout << endl;
	cout << "输入边依附的顶点及权值，如 v0 v1 28" << endl;
	for (k = 0; k < G.arcnum; ++k)
	{							//构造邻接矩阵 
		int v1, v2;
		int w;
		cout << "请输入第" << (k + 1) << "条边依附的顶点及权值:";
		cin >> v1 >> v2 >> w;							//输入一条边依附的顶点及权值
		i = findVex(G, v1);  j = findVex(G, v2);		//确定v1和v2在G中的位置，即顶点数组的下标 
		G.arcs[i][j] = w;								//边<v1, v2>的权值置为w 
		G.arcs[j][i] = G.arcs[i][j];					//置<v1, v2>的对称边<v2, v1>的权值为w 
	}
}
void outputGraph(AMGraph G)
{
	cout << endl;
	cout << "------------------顶点数组的输出-------------------" << endl;
	cout << endl;
	cout << "无向图的顶点为： ";
	for (int i = 0; i < G.vexnum; i++)//输出无向图的顶点信息
		cout << G.vexs[i] << "  ";
	cout << endl;
	cout << endl;
	cout << "------------------邻接矩阵的输出-------------------" << endl;
	cout << endl;
	for (int i = 0; i < G.vexnum; i++)//输出邻接矩阵
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			cout << G.arcs[i][j] << "\t";
		}
		cout << endl;
	}
	cout << endl;
}

题目2：图的各种遍历算法实现

void DFSGraph(AMGraph G, int v) //深度优先遍历
{
	//图G为邻接矩阵类型 
	int w;
	cout << G.vexs[v] << "  ";
	visited[v] = true;  //访问第v个顶点，并置访问标志数组相应分量值为true 
	for (w = 0; w < G.vexnum; w++) //依次检查邻接矩阵v所在的行  
	{
		if ((G.arcs[v][w] != 0) && (G.arcs[v][w] != MaxInt) && (!visited[w]))
			//G.arcs[v][w] != 0 &&G.arcs[v][w] != MaxInt表示w是v的邻接点，如果w未访问，则递归调用DFS 
			DFSGraph(G, w);
	}
}
void BFSGraph(AMGraph G, int v)//广度优先遍历
{
	int i, j, w;
	SqQueue Q;    //定义队列
	InitQueue(Q); //初始化队列
	for (i = 0; i < G.vexnum; i++)//标志数组置0
		visited[i] = 0;                                                 
	cout << G.vexs[v];
	visited[v] = 1;  //已访问结点置访问标志为1
	EnQueue(Q, v);//起点进队
	while (!QueueEmpty(Q)) 
	{   //队列不空
		DeQueue(Q, j);    //顶点v出队
		for (w = 0; w < G.vexnum; w++)
			if ((G.arcs[j][w] != MaxInt) && (!visited[w]))
			{   //对j的每个邻接点w进行访问，再对w的每个邻接点进行访问，依此类推，并置相应标志为1，直到遍历完成
				cout <<"  " << G.vexs[w];
				visited[w] = 1;
				EnQueue(Q, w);
			}
	}
}

题目3：最小生成树的算法实现

void Prim(AMGraph G, int v)
{
	int clovex[MAX];
	int min, i, j, k=0;
	int lowest[MAX];//lowest[i]=0表示已存在于集合U中
	for (i = 0; i < G.vexnum; i++)//初始化
	{
		lowest[i] = G.arcs[v][i];//lowest存储起点的邻接信息
		clovex[i] = G.vexs[v];//clovex数组全置为起点v
	}
	for (i = 1; i < G.vexnum; i++)//寻找其余顶点
	{
		min = MaxInt;
		for (j = 0; j < G.vexnum; j++)//在V-U中寻找最短的边
		{
			if (lowest[j] != 0 && lowest[j] < min)
			{
				min = lowest[j];
				k = j;//k记录最近的顶点下标
			}
		}
		//输出最小生成树的各边
		cout << "第" << i << "条边为： " << clovex[k] << "  " << G.vexs[k] << "  " << min << endl;
		lowest[k] = 0;//把最近顶点加入集合U
		for (j = 0; j < G.vexnum; j++)//对集合V-U中的顶点进行调整
		{
			if (lowest[j] != 0 && G.arcs[k][j] < lowest[j])
			{
				lowest[j] = G.arcs[k][j];
				clovex[j] = k;              //修改数据，为下一次循环输出最小生成树的边准备
			}
		}
	}
}

题目4：最短路径的算法实现

void outputPath(AMGraph G,int dist[],int path[],int U[],int v)//输出各条最短路径
{
	int i, j, k,l;
	int temp[MAX];//逆向存储路径的各个下标
	for (i = 0; i < G.vexnum; i++)
	{
		if (i != v)
		{
			//先输出路径长度
			cout << "从起点" << G.vexs[v] << "到顶点" << G.vexs[i] << "的路径为长度为： " << dist[i] << "  ";
			l = 0;	
			temp[l] = i;//终点下标
			k = path[i];//k赋予原路径终点的前一顶点下标
			if (k == -1)//k=-1表示没有路径
				cout << "没有路径，无法到达！" << endl;
			else	//输出路径
			{
				while(k!=v)
				{
					l++;
					temp[l] = k;
					k = path[k];
				}
				l++;
				temp[l] = v;  //逆向路径的最后一个元素赋予原路径的起点
				cout << G.vexs[temp[l]];//先输出起点
				for (j = l - 1; j >= 0; j--)//输出路径的其他顶点
					cout << "-" << G.vexs[temp[j]];
				cout << endl;
			}
		}
	}
}
void Dijkstra(AMGraph G, int v)
{
	int dist[MAX];//存取各最小路径长度
	int path[MAX];//路径数组,存取所经过路径的下标
	int U[MAX];//集合U，若U[i]=1，则表示顶点在集合U中；若U[i]=0,则表示顶点在集合V-U中
	int min,i, j, k=0;
	for (i = 0; i < G.vexnum; i++)//初始化
	{
		dist[i] = G.arcs[v][i];//距离初始化
		U[i] = 0;//初始时集合U中没有顶点
		if (G.arcs[v][i] != MaxInt)//当另一顶点与起点存在直连边时，该顶点的前一顶点置为起点v
			path[i] = v;
		else                       //没有边时，置为-1
			path[i] = -1;
	}
	U[v] = 1;	//起点加入到集合U中
	for (i = 0; i < G.vexnum; i++)
	{
		min = MaxInt;
		for (j = 0; j < G.vexnum; j++)//先找到权值最小的边
		{
			if (U[j] == 0 && dist[j] < min)
			{
				min = dist[j];
				k = j;
			}
		}
		U[k] = 1;//把另一顶点加入集合U中
		for (j = 0; j < G.vexnum; j++)
		{
			if ((U[j] == 0) && (G.arcs[k][j] < MaxInt)&&((dist[k] + G.arcs[k][j]) < dist[j]))
			{	//若加入新的中间点后，所得路径比原来小，则更新最小路径
				dist[j] = dist[k] + G.arcs[k][j];
				path[j] = k;
			}
		}
	}
	outputPath(G,dist, path, U, v);
}

五、实验结果及分析

测试结果：正确

首先输入无向图的顶点数和边数，根据顶点数创建多少阶邻接矩阵，然后输入顶点，再输入各边的信息（每次输入时先输入边相连的两个顶点，还有一个权值），由于是无向图，所以矩阵是对称的，对角线元素均为0，没有边的赋予整形最大值（意味无穷大）。输入完毕后，输出顶点信息，输出邻接矩阵。

测试结果：正确

先由用户确定起点，输入起点后，调用findVex（）函数返回起点对应的下标，从该顶点开始深度优先遍历无向图。

测试结果：正确

如图，根据普利姆算法生成最小生成树，并输出最小生成树的各条边。

测试结果：正确

设置‘0’为起点，计算从‘0’到各个顶点的最小路径长度，并把路径输出。

总结：

1. 在对邻接矩阵赋值时，一开始没有边和到自身的情况下，我都赋予了0，但是这样会导致后边的普利姆算法在判断最小边时发生错误，所以把没有边的情况改为了赋予整型最大值32267。
2. 深度、广度优先遍历要用到一个数组来判断各个顶点是否被访问过，然后根据邻接边递归调用访问下一顶点，直到所有顶点都被访问一次。
3. 普利姆算法中，要用一个数组判断顶点是否在集合U中，还要用一个数组保存U中的顶点，便于输出最小生成树的边。在找到一条最小边后，要把另一顶点加入到集合U中，并且重新调整集合V-U的顶点信息。需要注意的是，这个算法是用来生成最小生成树的，是整个集合判断权值是否最小，而不是单源最短路径，写代码时不能搞混……
4. Dijkstra算法和Prim算法有点相似，不同的是更新最短路径，判断最短路径时要把中间结点加入进去与原定最短路径进行判断。在输出路径时，新定义一个数组逆向存储路径经过的顶点下标，然后从尾开始输出，依次循环输出起点到各个顶点的最短路径。

Pass：仅作为实验参考，有些地方可能不够完善，见谅一下。转载请注明出处！