大数据结构课程设计最短路径

《大数据结构课程设计最短路径》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、标准文案数据结构课程设计大全标准文案题目名称：最短路径计算机科学与技术学院一、需求分析(1)题目：最短路径实现图的输入，选择合适的结构表示图，在此基础上实现求解最短路径的算法，可以从任意一点求最短路径，学生必须准备多组测试数据，并设计清晰易懂的输入输出界面，要求：如何用多种数据结构来求解问题。同时要求实现对应数据结构的所有基本操作。（2）程序的输入与输出:要求用多种数据结构求解问题，也就是要用邻接表与邻接矩阵实现最短路径的算法，需要有多组输入输出，(a)输入的形式和输入值的范围：输入的形式为整型1.先输入共需要创建几次图2.再分别输

2、入边数和顶点数（范围：1~100）3.输入1和2选择是否为有向图图（1为有向，2为无向）4.对应每条边输入起点和终点下标，以及对这条边的权值（最大的权值为100）。5.输入在邻接表的基础上输入深度与广度优先搜索的起点大全标准文案1.我们输入求各种最短路径起点和终点(a)输出的形式；1.输出所建立的邻接表（表结点后面的括号是头结点与表结点的权值）2.输出DFS和BFS的结果3.输出该图不带权值的最短路径与路径4.接下来输入起点和终点，求带权值的最短路径也就是Dijstra算法，输出长度并给出路径5.前面都是用邻接表实现的各种算法，接下

3、来的Floyd算法就用矩阵实现，于是直接邻接表转矩阵输出6.用Floyd算法求出图的多源最短路径，给出起点终点输出最短路径长度，接着便到了第二次创建图，直至循环结束。（2）程序的功能:求给出带权图的任意两点，输出最短路径长度并给出其最短路径所经过的顶点。在实际应用中可以将交通网络化成带权的图，图中顶点表示城市，边代表城市之间的公路，边上的权值表示公路的长度。这样可以发现两个地方之间有无公路可连，在几条公路可通的情况下，可以找到那条路径最短。也就是现在地图app中的功能。（4）测试数据:包括正确的输入及其输出结果和含有错误的输入及其输

4、出结果。大全标准文案大全标准文案在有向图中输入错误的数据（顶点与顶点方向相反），会输出逆向信息。大全标准文案一、概要设计1.主程序流程（a）主程序首先多组输入一个n，在n不为0的前提下循环执行（b）调用BuildGraph()函数，创建一个图并以邻接表的形式存储（c）BuildGraph()函数输入顶点、边数调用CreateGraph(Nv）函数，初始化一个有Nv个顶点但没有边的图，再根据结构体Edge输入每个边的信息，调用InsertEdge(Graph,E,c);函数将每条边插入到仅仅初始化的图中，完成一个图的建立，并返回一个邻

5、接表类型的结构体（d）主函数接到返回来的邻接表结构体,调用outL()函数，输出这个邻接表（e）输入起点，调用DFS(Graph,v1,1);函数进行递归求解深度优先搜索并直接输出（f）输入起点，调用BFS(Graph,v1);函数，求解广度优先搜索并直接输出大全标准文案（a）输入起点、终点，调用Unweighted(Graph,v1);函数求得起点到每个点的最短路径，再用dist[v2]输出。（b）如果dist[v2]大于0证明v1可以到达v2，调用outpath(v2)输出路径（c）输入起点、终点，调用Dijkstra(Grap

6、h,v1);函数求得起点到每个点的最短路径，再用dist[v2]输出。（d）如果dist[v2]小于定义的INF，证明v1可以到达v2，再次调用outpath(v2)输出路径（e）用MGraphgra;创建一个邻接矩阵之后，调用transform(Graph);进行邻接表与邻接矩阵的转换（f）outM(gra);函数，以二维数组的形式输出邻接矩阵（g）调用Floyd(gra,D,pa);函数求得多源最短路径，存储在D这个二维数组中，给出起点，终点直接输出。2.所有用到的抽象数据类型（1）边的定义（a）表示边的起点和终点（b）边的权重

7、（2）邻接表的表结点的定义（a）邻接点下标（b）边权重（c）指向下一个邻接点的指针大全标准文案（3）邻接表的顶点表头结点的定义（a）边表头指针（b）存顶点的数据（c）邻接表类型的AdjList存储邻接表的头结点（4）邻接表对应图结点的定义（a）顶点数（b）边数（c）邻接表（5）邻接矩阵的定义（a）顶点数（b）边数（c）二维数组形式的邻接矩阵（6）BFS存数据的队列（a）队头front标记（b）队头rear标记（c）存数据的数组（7）用于输出最短路径的栈（a）栈顶top标记（b）存数据的数组3.设计程序的各个模块（即函数）功能及设计思

8、想（1）CreateGraph(intVertexNum)函数大全标准文案功能：初始化一个有VertexNum个顶点但没有边的图设计思想：（a）根据邻接表结构体分配一块空间（b）初始化图的顶点数和边数（c）初始化邻接表头指针（d）注意