数据结构实验六图结构及其应用

Jimmy 徐2019年5月11日数据结构0 条评论

1,633 次

一、实验目的

掌握图类的邻接矩阵存储结构的实现；
掌握图的基本操作，包括图的建立、广度优先遍历和深度优先遍历算法；
掌握求最短路径的Dijkastra算法。

二、实验要求

复习课本中第7章关于图的相关知识内容；
用C++语言完成算法和程序设计并且调试通过；

三、实验题目与要求

1．图的遍历

详细描述：利用以提供的源程序素材，实现对不多于30个结点的图的建立以及广度优先和深度优先遍历算法。

具体功能要求：从键盘中输入网中顶点的个数，以及顶点的数据值，并以顶点的输入次序作为顶点的编号输入顶点与顶点之间的邻接边的权值（注：若为无向图，则每条边可由两条方向相反的有向边构成）；若无边相连则已设定的权值最大值MaxWeight=1000代替。利用顶点与边的信息建立网的邻接矩阵，并第一个输入的顶点为原点对网进行深度优先和广度优先遍历，并输入遍历的顶点序列。

例：如下图7-1图所示，则输入为：
6 ABCDEF 18 A B 34 A E 12 B A 34 B C 46 B F 19 C B 46 C D 17 C F 25 D C 17 D E 38 D F 25 E A 12 E D 38 E F 26 F B 19 F D 25 F C 25 F E 26

在提供的程序模板中，完成以下函数，实现上述功能；

(1) DFSTraverse (MGraph G)

功能描述：对网进行深度优先遍历，网可以非连通

(2) BFSTraverse (MGraph G)

功能描述：对网进行广度优先遍历，网可以非连通

2．最短路径求解

详细描述:在第一题的基础上，Dijkastra算法求解从第A个顶点到其余各个顶点的最短路径的所经过的顶点以及路径的长度。

例：如图7-1所示，则该求出顶点A到其余个顶点的最短路径所经过的顶点，以及路径的长度；输出如下所示：

A->B: A B 34 A->C: A E F C 63 A->D: A E D 50 A->E: A E 12 A->F: A E F 38

在提供的程序模板中，完成以下函数，实现上述功能；

void dijkstra(MGraph G, int vs )

3.验证练习

先对下图7-2和7-3进行深度和广度优先遍历，并求出以A作为源点求最短路径的结果。并通过输入图的信息执行图的遍历和求最短路径程序，比较运行结果与你求的结果是否一致，若有不一致请查明原因。

四、程序代码及运行结果

【程序代码】

#include <stdio.h>
#include <stdlib.h>
//#include <stdbool.h>
#include <limits.h>

#define bool int
#define true 1
#define false 0

#define MAX_VERTEX_NUM 20    //最大顶点个数 
#define INFINITY INT_MAX  //最大值∞ 

typedef char VertexType;   //顶点向量类型 
typedef int VRType;
typedef int InfoType;
typedef int QElemType;

//图的数组存储表示 
typedef struct {
	VertexType vexs[MAX_VERTEX_NUM];    //顶点向量
	VRType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];;  //邻接矩阵,于无权图1、0表示两个顶点是否相邻，对于有权图为权值
	int vexnum, arcnum; //图的顶点数和弧数
}MGraph;

bool visited[MAX_VERTEX_NUM];  //标记顶点是否被访问，访问为true,否则为false

//查找顶点在顶点向量中的位置
int locateVertex(MGraph umg, VertexType v)
{
	int i;
	for (i = 0; i < umg.vexnum; i++)
	{
		if (v == umg.vexs[i])
			return i;
	}
	return -1;
}
//创建无向（有向）无权图
void createUMGraph(MGraph *umg)
{
	int i, j, v;
	char v1, v2;
	printf("输入无权图的顶点数和边数\n");
	scanf("%d %d", &(*umg).vexnum, &(*umg).arcnum);
	for (v = 0; v < (*umg).vexnum; v++)
		visited[v] = false;
	getchar();
	printf("输入顶点名称\n");
	for (v = 0; v < (*umg).vexnum; v++)
	{
		printf("输入第%d个顶点名称：", v);
		scanf("%c", &(*umg).vexs[v]);
		getchar();
	}

	//初始化邻接矩阵
	for (i = 0; i < (*umg).vexnum; i++)
		for (j = 0; j < (*umg).vexnum; j++)
			(*umg).arcs[i][j] = 0;

	//将图中相邻的顶点的邻接矩阵值设为1，不相邻仍为0 
	printf("输入边的信息，输入边的两个顶点名称v1 v2\n");
	for (v = 0; v < (*umg).arcnum; v++)
	{
		printf("输入第%d条边两个顶点:", v);
		scanf("%c %c", &v1, &v2);
		getchar();
		printf("\n");
		i = locateVertex(*umg, v1);
		j = locateVertex(*umg, v2);
		//  (*umg).arcs[i][j] = (*umg).arcs[j][i] = 1;    //由于是无向图，因此一条边关联两个顶点 
		(*umg).arcs[i][j] = 1;    //有向图，边为单向 
	}
}

//创建无向（有向）有权图
void createMGraph(MGraph *mg)
{
	int i, j, v, w;
	char v1, v2;
	printf("输入有权图的顶点数和边数\n");
	scanf("%d %d", &(*mg).vexnum, &(*mg).arcnum);
	for (v = 0; v < (*mg).vexnum; v++)
		visited[v] = false;
	getchar();
	printf("输入顶点名称\n");
	for (v = 0; v < (*mg).vexnum; v++)
	{
		printf("输入第%d个顶点名称：", v);
		scanf("%c", &(*mg).vexs[v]);
		getchar();
	}

	//初始化邻接矩阵
	for (i = 0; i < (*mg).vexnum; i++)
		for (j = 0; j < (*mg).vexnum; j++)
			(*mg).arcs[i][j] = INFINITY;

	//将图中相邻的顶点的邻接矩阵值设为边的权值 
	printf("输入边的信息，输入边的两个顶点名称和权值v1 v2 w\n");
	for (v = 0; v < (*mg).arcnum; v++)
	{
		printf("输入第%d条边两个顶点和权值:", v);
		scanf("%c %c %d", &v1, &v2, &w);
		getchar();
		i = locateVertex(*mg, v1);
		j = locateVertex(*mg, v2);
		//  (*mg).arcs[i][j] = (*mg).arcs[j][i] = w;    //由于是无向图，因此一条边关联两个顶点 
		(*mg).arcs[i][j] = w;    //有向图，边为单向 
	}
}

//打印图的邻接矩阵
void print(MGraph G)
{
	int i, j;
	printf("图的邻接矩阵\n");
	for (i = 0; i < G.vexnum; i++)
	{
		for (j = 0; j < G.vexnum; j++)
		{
			if (G.arcs[i][j] != INFINITY)
				printf("%d  ", G.arcs[i][j]);
			else
				printf("∞ ");
		}
		printf("\n");
	}
	printf("\n");
}

//深度优先遍历图 
int FirstAdjVex(MGraph G, int v)
{   //获取与顶点v相邻的第一个顶点下标 
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		if (G.arcs[v][i] != 0 && G.arcs[v][i] != INFINITY && !visited[i])
			return i;
	}
	return -1;
}

int NextAdjVex(MGraph G, int v, int w)
{   //得到v的下一个未被访问的相邻顶点下标 
	int i;
	for (i = w; i < G.vexnum; i++)
	{
		if (G.arcs[v][i] != 0 && G.arcs[v][i] != INFINITY && !visited[i])
			return i;
	}
	return -1;
}

void DFS(MGraph G, int v)
{
	int w;
	visited[v] = true;
	printf("%c ", G.vexs[v]);         //访问第v个顶点 
	for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
		if (!visited[w])
			DFS(G, w);              //对v的尚未访问的邻接顶点w递归调用DFS 

}

void DFSTraverse(MGraph G)
{
	printf("深度优先遍历序列：");

	int v;
	for (v = 0; v < G.vexnum; v++)
		visited[v] = false;
	for (v = 0; v < G.vexnum; v++)
		if (!visited[v])
			DFS(G, v);

	printf("\n");
}

//广度优先遍历

//创建用于广度优先遍历的队列
typedef struct QNode
{
	QElemType data;
	struct QNode *qnext;
}QNode, *PQNode;

typedef struct Queue
{
	PQNode front;
	PQNode rear;
}Queue, *PQueue;

//初始化一个空队列 
PQueue initQueue()
{
	PQueue pqueue = (PQueue)malloc(sizeof(Queue));
	PQNode pqnode = (PQNode)malloc(sizeof(QNode));
	if (pqnode == NULL)
	{
		printf("队列头空间申请失败！\n");
		exit(-1);
	}
	pqueue->front = pqueue->rear = pqnode;
	pqnode->qnext = NULL;
	return pqueue;
}

//队尾入队
void enQueue(PQueue pqueue, QElemType data)
{
	PQNode pqnode = (PQNode)malloc(sizeof(QNode));
	if (pqnode == NULL)
	{
		printf("队列结点申请失败！\n");
		exit(-1);
	}
	pqnode->data = data;
	pqnode->qnext = NULL;
	pqueue->rear->qnext = pqnode;
	pqueue->rear = pqnode;
}
//判断队列是否为空
bool isEmpty(PQueue pqueue)
{
	if (pqueue->front == pqueue->rear)
		return true;
	return false;
}
//队头出队
QElemType deQueue(PQueue pqueue)
{
	if (isEmpty(pqueue))
	{
		printf("队列为空\n");
		exit(-1);
	}

	PQNode pqnode = pqueue->front->qnext;
	pqueue->front->qnext = pqnode->qnext;
	if (pqnode == pqueue->rear)
		pqueue->rear = pqueue->front;
	QElemType data = pqnode->data;
	free(pqnode);
	return data;

}
void BFSTraverse(MGraph G)
{
	printf("广度优先遍历序列：");
	int i, v, w;
	for (i = 0; i < G.vexnum; i++)
		visited[i] = false;
	PQueue pqueue = initQueue();    //初始化辅助队列 
	for (i = 0; i < G.vexnum; i++)
	{
		if (!visited[i])             //i未被访问 
		{
			visited[i] = true;
			printf("%c ", G.vexs[i]);
			enQueue(pqueue, i);
			while (!isEmpty(pqueue))
			{
				v = deQueue(pqueue);    //队头元素出队 
				for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
					if (!visited[w])            //w为v的尚未访问的邻接顶点 
					{
						visited[w] = true;
						printf("%c ", G.vexs[w]);
						enQueue(pqueue, w);
					}

			}
		}
	}
	printf("\n");
}

void Dispath(MGraph g, int dist[], int path[], int S[], int v)
//输出从顶点v出发的所有最短路径
{
	int i, j, k;
	int apath[MAX_VERTEX_NUM], d;					//存放一条最短路径(逆向)及其顶点个数
	for (i = 0; i < g.vexnum; i++)				//循环输出从顶点v到i的路径
		if (S[i] == 1 && i != v)
		{
			printf("%c -> %c:\t", g.vexs[v], g.vexs[i]);
			d = 0; apath[d] = i;			//添加路径上的终点
			k = path[i];
			if (k == -1)				//没有路径的情况
				printf("无路径\n");
			else						//存在路径时输出该路径
			{
				while (k != v)
				{
					d++; apath[d] = k;
					k = path[k];
				}
				d++; apath[d] = v;		//添加路径上的起点
				printf("%c", g.vexs[apath[d]]);	//先输出起点
				for (j = d - 1; j >= 0; j--)	//再输出其他顶点
					printf(" %c", g.vexs[apath[j]]);
				printf("\t %d", dist[i]);
				printf("\n");
			}
		}
}

void dijkstra(MGraph G, int vs)//求图G中从vs顶点到达其余各顶点的最短路径 
{
	int *prev = (int *)malloc(sizeof(int)*G.arcnum);
	int *dist = (int *)malloc(sizeof(int)*G.arcnum);
	int *flag = (int *)malloc(sizeof(int)*G.arcnum);      // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。

	int i, j, k;
	int min;
	int tmp;

	// 初始化
	for (i = 0; i < G.vexnum; i++)
	{
		flag[i] = 0;              // 顶点i的最短路径还没获取到。
		prev[i] = 0;              // 顶点i的前驱顶点为0。
		dist[i] = G.arcs[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。
	}

	// 对"顶点vs"自身进行初始化
	flag[vs] = 1;
	dist[vs] = 0;

	// 遍历G.vexnum-1次；每次找出一个顶点的最短路径。
	for (i = 1; i < G.vexnum; i++)
	{
		// 寻找当前最小的路径；
		// 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
		min = INFINITY;
		for (j = 0; j < G.vexnum; j++)
		{
			if (flag[j] == 0 && dist[j] < min)
			{
				min = dist[j];
				k = j;
			}
		}
		// 标记"顶点k"为已经获取到最短路径
		flag[k] = 1;

		// 修正当前最短路径和前驱顶点
		// 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
		for (j = 0; j < G.vexnum; j++)
		{
			tmp = (G.arcs[k][j] == INFINITY ? INFINITY : (min + G.arcs[k][j])); // 防止溢出
			if (flag[j] == 0 && (tmp < dist[j]))
			{
				dist[j] = tmp;
				prev[j] = k;
			}
		}
	}

	// 打印dijkstra最短路径的结果
	//printf("dijkstra(%c): \n", G.vexs[vs]);
	//for (i = 0; i < G.vexnum; i++)
	//	printf("  shortest(%c, %c)=%d\n", G.vexs[vs], G.vexs[i], dist[i]);

	Dispath(G, dist, prev, flag, vs);	//输出最短路径
}

int main()
{
	// MGraph umg;  //无权图
	//  createUMGraph(&umg);  //创建无权图 
	//  print(umg);
	MGraph mg;
	createMGraph(&mg);
	print(mg);
	DFSTraverse(mg);
	BFSTraverse(mg);
	dijkstra(mg, 0);
	return 0;
}

【运行结果】

五、实验心得体会

巩固了深度优先搜索、广度优先搜索和图的知识。

Tags:
数据结构

Jimmy 徐

每一天都是新鲜的！

数据结构实验六图结构及其应用

一、实验目的

二、实验要求

三、实验题目与要求

四、程序代码及运行结果

五、实验心得体会

赞过：

Jimmy 徐

评论取消回复

近期文章

分类

官方订阅号

官方小程序

一、实验目的

二、实验要求

三、实验题目与要求

四、程序代码及运行结果

五、实验心得体会

赞过：

Jimmy 徐

评论 取消回复

近期文章

分类

官方订阅号

官方小程序

评论取消回复