写一篇数据结构关于图应用实验报告要求用C语言写出代码

实验题目：图应用——寻找最短路径

实验目的：

了解图的基本概念及其存储方式；
学习最短路径算法——Dijkstra算法；
实现Dijkstra算法，并应用于寻找最短路径的问题。

实验内容：

实现图的存储，包括邻接矩阵和邻接表两种方式；
实现Dijkstra算法，求解图中任意两点之间的最短路径；
编写主程序，实现用户输入起点和终点，输出最短路径及其长度。

实验步骤：

图的存储：

（1）邻接矩阵：定义一个二维数组G[V][V]，其中V为顶点数，如果V1到V2有边，则G[V1][V2]为边的权值，否则设为无穷大。

（2）邻接表：定义一个结构体数组，其中每个结构体包括一个顶点和它所连的边。在该结构体中可以用指针来表示下一个结构体，从而实现邻接表的存储。

Dijkstra算法：

（1）初始化：将起点到各个节点的距离设为无穷大，将起点到自身的距离设为0。

（2）遍历：从起点开始，依次遍历所有与其相邻的节点，更新其到起点的距离。如果更新后的距离比原先的距离小，则更新该节点的距离，并将该节点加入到待遍历的集合中。

（3）重复：重复上述步骤，直到所有节点都被遍历过。

主程序：

（1）创建图，实现邻接矩阵和邻接表两种存储方式。

（2）输入起点和终点。

（3）调用Dijkstra算法，求解最短路径及其长度。

（4）输出最短路径和长度。

代码实现：

图的存储：

（1）邻接矩阵实现：

typedef struct{ int vexnum;//顶点数 int edgenum;//边数 int matrix[MAXVEX][MAXVEX];//邻接矩阵 }MGraph;

（2）邻接表实现：

typedef struct ArcNode{ int adjvex;//该弧所指向的顶点的位置 int weight;//弧的权值 struct ArcNode *next;//指向下一条弧的指针 }ArcNode;

typedef struct VertexNode{ char data;//顶点信息 ArcNode *firstarc;//指向第一条依附该顶点的弧的指针 }VertexNode,AdjList[MAXVEX];

typedef struct{ AdjList vertices;//邻接表 int vexnum;//图的当前顶点数 int edgenum;//图的当前边数 }ALGraph;

Dijkstra算法实现：

void Dijkstra(MGraph G, int v0, int *dist, int *prev){ int i,j,k; int min; int tmp; int flag[MAXVEX];//flag[i]表示顶点i是否已经在S集合中 for (i=0;i<G.vexnum;i++){ flag[i]=0;//初始化 dist[i]=G.matrix[v0][i];//初始化起点到各个顶点的距离 prev[i]=0;//初始化前驱顶点 } flag[v0]=1;//将起点加入到S集合中 dist[v0]=0;//起点到自身的距离为0 for (i=1;i<G.vexnum;i++){ min=INFINITY;//初始化最小值为无穷大 for (j=0;j<G.vexnum;j++){ if (!flag[j]&&dist[j]<min){//寻找距离最小的顶点 min=dist[j]; k=j; } } flag[k]=1;//将距离最小的顶点加入到S集合中 for (j=0;j<G.vexnum;j++){ tmp=(G.matrix[k][j]==INFINITY?INFINITY:(min+G.matrix[k][j]));//更新距离 if (!flag[j]&&tmp<dist[j]){ dist[j]=tmp; prev[j]=k;//更新前驱顶点 } } } }

主程序：

int main(){ int i,j; int v0,v1; int dist[MAXVEX]; int prev[MAXVEX]; MGraph MG; ALGraph AG; //创建邻接矩阵 CreateMGraph(&MG); //创建邻接表 CreateALGraph(&AG); //输入起点和终点 printf("请输入起点和终点：\n"); scanf("%d%d",&v0,&v1); //求解最短路径及其长度 Dijkstra(MG,v0,dist,prev); printf("起点到终点的最短路径为："); i=v1; printf("%d<-",i); while (prev[i]!=v0){ printf("%d<-",prev[i]); i=prev[i]; } printf("%d\n",v0); printf("最短路径的长度为：%d\n",dist[v1]); return 0;