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

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date数据结构课程设计最短路径_x0001_数据结构课程设计题目名称：最短路径 计算机科学与技术学院一、 需求分析 (1)题目：最短路径实现图的输入，选择合适的结构表示图，在此基础上实现求解最短路径的算法，可以从任意一点求最短路径，学生必须准备多组测试数据，并设计清晰易懂的输入输出界面，要求：如何用多种数据结构来求解问题。同时要求实现对应数据结构的所有基本操作。（2） 程序的输入与输出:要求用多种数据结构求解问题，也就是要用邻接表与邻接矩阵实现最短路径的算法，需要有多组输入输出，(a) 输入的形式和输入值的范围：输入的形式为整型1. 先输入共需要创建几次图2. 再分别输入边数和顶点数（范围：1100）3. 输入1和2选择是否为有向图图（1为有向，2为无向）4. 对应每条边输入起点和终点下标，以及对这条边的权值（最大的权值为100）。5. 输入在邻接表的基础上输入深度与广度优先搜索的起点6. 我们输入求各种最短路径起点和终点(b) 输出的形式；1. 输出所建立的邻接表（表结点后面的括号是头结点与表结点的权值）2. 输出DFS和BFS的结果3. 输出该图不带权值的最短路径与路径4. 接下来输入起点和终点，求带权值的最短路径也就是Dijstra算法，输出长度并给出路径5. 前面都是用邻接表实现的各种算法，接下来的Floyd算法就用矩阵实现，于是直接邻接表转矩阵输出6. 用Floyd算法求出图的多源最短路径，给出起点终点输出最短路径长度，接着便到了第二次创建图，直至循环结束。（3） 程序的功能:求给出带权图的任意两点，输出最短路径长度并给出其最短路径所经过的顶点。在实际应用中可以将交通网络化成带权的图，图中顶点表示城市，边代表城市之间的公路，边上的权值表示公路的长度。这样可以发现两个地方之间有无公路可连，在几条公路可通的情况下，可以找到那条路径最短。也就是现在地图app中的功能。（4）测试数据:包括正确的输入及其输出结果和含有错误的输入及其输出结果。 在有向图中输入错误的数据（顶点与顶点方向相反），会输出逆向信息。二、 概要设计1.主程序流程（a） 主程序首先多组输入一个n，在n不为0的前提下循环执行（b） 调用 BuildGraph()函数，创建一个图并以邻接表的形式存储（c） BuildGraph()函数输入顶点、边数调用CreateGraph(Nv）函数，初始化一个有Nv个顶点但没有边的图，再根据结构体Edge输入每个边的信息，调用InsertEdge( Graph, E ,c );函数将每条边插入到仅仅初始化的图中，完成一个图的建立，并返回一个邻接表类型的结构体（d） 主函数接到返回来的邻接表结构体,调用outL()函数，输出这个邻接表（e） 输入起点，调用DFS(Graph,v1,1);函数进行递归求解深度优先搜索并直接输出（f） 输入起点，调用BFS(Graph,v1);函数，求解广度优先搜索并直接输出（g） 输入起点、终点，调用Unweighted ( Graph, v1 );函数求得起点到每个点的最短路径，再用distv2输出。（h） 如果distv2大于0证明v1可以到达v2，调用outpath(v2)输出路径（i） 输入起点、终点，调用Dijkstra(Graph,v1);函数求得起点到每个点的最短路径，再用distv2输出。（j） 如果distv2小于定义的INF，证明v1可以到达v2，再次调用outpath(v2)输出路径（k） 用MGraph gra;创建一个邻接矩阵之后，调用transform(Graph);进行邻接表与邻接矩阵的转换（l） outM(gra);函数，以二维数组的形式输出邻接矩阵（m） 调用Floyd(gra,D,pa);函数求得多源最短路径，存储在D这个二维数组中，给出起点，终点直接输出。2.所有用到的抽象数据类型（1）边的定义 （a）表示边的起点和终点 （b）边的权重 （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.设计程序的各个模块（即函数）功能及设计思想（1） CreateGraph( int VertexNum )函数功能：初始化一个有VertexNum个顶点但没有边的图 设计思想：（a）根据邻接表结构体分配一块空间（b）初始化图的顶点数和边数（c）初始化邻接表头指针（d）注意：这里默认顶点编号从1开始，到Graph->Nv（e）初始化dist与path数组（2） InsertEdge( LGraph Graph, Edge E, int c )函数功能：在建立的图中插入边设计思想：（a）输入v1，v2，建立一个v2的新的邻接点（b）将V2插入V1的表头，用c做标志位，在调用函数时输入（c）若c=2，表示图为无向图，还要插入边 <V2, V1>（d）接着为V1建立新的邻接点，将V1插入V2的表头 （3） BuildGraph()函数功能：输入顶点和边数，定义有向图和无向图，建立图，并返回邻接表类型的指针设计思想：（a）读入顶点个数，调用CreateGraph(Nv)初始化有Nv个顶点但没有边的图（b）读入边数，定义有向、无向，如果有边，建立边结点，读入边，格式为"起点 终点 权重"，插入邻接表（c）注意：如果权重不是整型，Weight的读入格式要改（4） clrv(LGraph g)函数功能：初始化图的访问数组Visited为0设计思想：重置被DFS和BFS修改过的visited数组（5） DFS( LGraph Graph, Vertex V ,int x)函数功能： 以V为出发点对邻接表存储的图Graph进行DFS搜索设计思想:（a）首先访问出发点v，并将其标记为已访问过；（b）然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。（c）若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。（d）也就是访问顶点v，从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历，重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。（6） CreateQueue()函数功能：初始化一个队列设计思想：（a）队列的front与rear分别置-1（b）为数组分配空间（7）AddQ(Queue Q, Vertex S)函数功能：向队列中添加元素设计思想：（a）将rear位置挪一位（b）在rear这位加入一个数（8） DeleteQ(Queue Q)函数功能：队列中删除一个元素，并返回设计思想：（a）从队列的头出队（b）也就是front位置加一（c）将front 这位的数据弹出（9）IsEmpty(Queue Q)函数功能：判断队列是否为空设计思想：（a）判断front的位置与rear是否相等（10）Unweighted ( LGraph Graph, Vertex S )函数功能：输入两点，求对应不带权值的图的最短路径设计思想：（a）按照递增（非递减）的顺序找出各个顶点的最短路，类似于BFS（b）先创建空队列, MaxSize为外部定义的常数（c）初始化源点.distS = 0（d）对V的每个邻接点W->AdjV（e）若W->AdjV未被访问过, W->AdjV到S的距离更新（f）将V记录在S到W->AdjV的路径上 （11）BFS( LGraph Graph, Vertex V)函数功能：向队列中添加元素设计思想：（a）顶点v入队列。（b）当队列非空时则继续执行，否则算法结束。（c）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。（d）查找顶点v的第一个邻接顶点first。（e）若v的邻接顶点first未被访问过的，则first入队列。（f）继续查找顶点v的另一个新的邻接顶点first，转到步骤（e）。（g）直到顶点v的所有未被访问过的邻接点处理完。转到步骤（f）。（12） clr(LGraph Graph)函数功能：重置dist数组与path数组设计思想：（a）重置最短路径的举例与路径（13）FindMinDist( LGraph Graph, int collected )函数功能：传入一个dist中没有被收录(collected对应为-1)的数设计思想：（a）V从1到顶点最大的下标（b）若V未被收录，且distV更小 （c）更新最小距离更新对应顶点 （d） 若找到最小dist，返回对应的顶点下标（e）若这样的顶点不存在，返回错误标记（14）Dijkstra( LGraph Graph, Vertex S )函数功能：求出输入Vertex S的单源最短路径设计思想：（a）Dijkstra算法开始采用的是一种贪心的策略，声明一个数组dist来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T（b）初始时，原点 s 的路径权重被赋为 0 （diss = 0）（c）若对于顶点 s 存在能直接到达的边（s,m），则把dism设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大（d）初始时，集合T只有顶点s。（e）从dis数组选择最小值（贪心），则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，（f）我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。 （g）然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。（15）transform(LGraph a)函数功能：邻接矩阵与邻接表转换设计思想：（a）分析邻接矩阵与邻接表的异同（b）邻接表有一个头结点数组，每一个对应一串链表，跟着的是每一个顶点与邻接点相连（c）邻接矩阵则是一个二维数组，两点有边值为权重，没有则初始化为无穷（d）先初始化一个空的二维数组（e）再对应邻接表每个头结点遍历其链表，将其值对应的加入到邻接矩阵中（16）outM(MGraph gra)函数功能：传入邻接矩阵结构体，输出邻接矩阵设计思想：（a）相当于输出一个二维数组（17）outL(LGraph Graph)函数功能：传入邻接表结构体，输出邻接表设计思想：（a）第一个循环遍历每个头结点（b）在第一个循环中表结点的地址不为空则输出（还要输出权值）（18）Floyd( MGraph Graph, WeightType DmaxVnum, Vertex pathmaxVnum )函数功能：Floyd算法求出多源最短路径设计思想：（a）通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入两个矩阵，矩阵S中的元素aij表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P中的元素bij，表示顶点i到顶点j经过了bij记录的值所表示的顶点。（b）假设图G中顶点个数为N，则需要对矩阵D和矩阵P进行N次更新。（c）初始时，矩阵D中顶点aij的距离为顶点i到顶点j的权值（d）如果i和j不相邻，则aij=，矩阵P的值为顶点bij的j的值（e），对矩阵D进行N次更新（f）第1次更新时，如果”aij的距离” > “ai0+a0j”(ai0+a0j表示”i与j之间经过第1个顶点的距离”)，则更新aij为”ai0+a0j”,更新bij=bi0。（g）同理，第k次更新时，如果”aij的距离” > “aik-1+ak-1j”，则更新aij为”aik-1+ak-1j”,bij=bik-1。更新N次之后，求出最短路径（19）Strack createStr()函数功能：创建一个栈设计思想：（a）分配空间，top = -1（20）push(Strack ptr,int v)函数功能：向栈中添加元素设计思想：（a）top加一（b）对应位置存为v（21）pop(Strack ptr)函数功能：出栈设计思想：（a）先将栈顶元素弹出，top减一（22）sIsEmpty(Strack ptr)函数功能：判断栈是否为空设计思想：（a）若果top=-1，为空，否则返回0（23）outpath(int v)函数功能：输出最短路径设计思想：（a）由于存最短路径的path数组每位存的只是上一个顶点，所以每次查找都会不断地找到每个顶点的上级，直至pathv=-1，会形成一个方向的路径，就要利用堆栈后进先出的特点输出。（b）在path存的数据不为-1时，将他们全部压入栈中，再将他们全部输出三、 详细设计1. 程序流程图建立图插入边初始化图BFSDFS创建邻接表D无权图最短路径转邻接矩阵Dijkstra算法求最小值Floyd算法2. 数据类型的实现（1）边的定义 typedef struct ENode *PtrToENode;struct ENode Vertex V1, V2; /* 有向边<V1, V2> */ WeightType Weight; /* 权重 */;typedef PtrToENode Edge;（2） 邻接表的表结点的定义 typedef struct AdjVNode *PtrToAdjVNode;struct AdjVNode Vertex AdjV; /* 邻接点下标 */ WeightType Weight; /* 边权重 */ PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */;typedef PtrToAdjVNode ANode;（3）邻接表的顶点表头结点的定义 typedef struct Vnode PtrToAdjVNode FirstEdge;/* 边表头指针 */ DataType Data; /* 存顶点的数据 */ /* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */ AdjListmaxVnum; /* AdjList是邻接表类型 */（4） 邻接表对应图结点的定义 typedef struct GNode *PtrToGNode;struct GNode int Nv; /* 顶点数 */ int Ne; /* 边数 */ AdjList G; /* 邻接表 */;typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */（5）邻接矩阵的定义typedef struct MNode *PtrToMNode;struct MNode int Nv; /* 顶点数 */ int Ne; /* 边数 */ WeightType GmaxVnummaxVnum; /* 邻接矩阵 */;typedef PtrToMNode MGraph; /* 以邻接矩阵存储的图类型 */（6） BFS存数据的队列typedef struct Que *Queue;struct Que int front; int rear; int datalistmaxVnum;（7）用于输出最短路径的栈typedef struct Str *Strack;struct Str int top; int StrlistmaxVnum;3. 重要函数的伪代码（1） 无权图的单源最短路径void Unweighted(Vertex s) Enqueue (s,q); while(队列不空) v = Deququ(q); for(v的每个邻接点w) if(w没被访问过) 更新w的距离； pathw=v; Enqueue(w,q); (2) 有权图的单源最短路径void Dijkstra(Vertex s)while(1) v = 未收录顶点中的dist最小者； if(这样的v不存在) break; collectedv = true; for(v的每个邻接点w) if(w没被收录) if(distv + v到w的权值 < distw) 更新w的最短距离； pathw = v; （3）Depth-first search访问顶点v；visitedv=1；/算法执行前visitedn=0w=顶点v的第一个邻接点；while（w存在）if（w未被访问）从顶点w出发递归执行该算法；w=顶点v的下一个邻接点；（4）BFS广度优先搜索初始化队列Q；visitedn=0；访问顶点v；visitedv=1；顶点v入队列Q； while（队列Q非空） v=队列Q的对头元素出队； w=顶点v的第一个邻接点； while（w存在） 如果w未访问，则访问顶点w； visitedw=1； 顶点w入队列Q； w=顶点v的下一个邻接点。四、 调试分析（1） 调试过程中遇到的问题是如何解决的。我是将每一个部分分开设计，运行成功再将他们整合到一起，不免会出现各种各样的问题，单独拿出去就可以运行，但放在一起没有报错，可就是做不对。而且后来我发现早成这种现象的不是因为程序有大问题，是一些根本就没有注意的小点造成的，例如定义的i加入到程序中就会被其中的i覆盖，结构体定义的不同等等，让我明白以后需要注重整体，在意细节，才能快速的完成任务。（2）算法的时空分析和改进设想；首先，利用邻接矩阵一定是稠密图才合算，对DFS时间复杂度为O（n2），广度优先搜索相同。而利用邻接表存储稀疏图合算。对DFS时间复杂度为O(n+e)，广度优先搜索相同Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。Dijkstra：O(n2)使用与权值为非负的图的单源最短路径。（2） 经验和体会通过这次设计我得到很深的体会，要好好的利用所学的知识，遇到难题要尽快查阅资料，已得到解决。五、 用户使用说明1. 先输入共要创建几个图（多组输入）2. 输入创建图的顶点数3. 输入创建图的边数4. 定义图有无方向(1为有向图，2为无向图)5. 根据边数输入起点、终点、和权值6. 输入DFS与BFS的起点7. 输入两个点求最短路径六、 测试结果建立图： 1 2 125 46 8 334 1顶点数：6边长：6深度搜索起始顶点：1结果：1 5 6 4 3 2广度搜索起始顶点：1结果：1 5 2 6 4 3输入1,4,不带权值的最短路径：1 5 4长度为：2输入1,4,不带权值的最短路径：1 2 3 4长度为：6开始测试：七、 测试情况测试成功，程序正常进行结果正确。1.对于第一次循环（无向图）：DFS：1 5 4 2 3BFS：1 5 2 6 4 3不带权的1到4最短路径为：1 5 4长度为：2带权的1到4最短路径为：1 2 3 4长度为：6Floyd算法中求最短路径也为62. 对于第二次循环（有向图）：由于V6与其他顶点反向，所以DFS：1 5 4 3 2 正确BFS：1 5 2 4 3 正确不带权的1到6最短路径为：无因为1到6逆向带权的1到4最短路径为：无因为1到6逆向而在Floyd算法中求1到4最短路径长度还是：6 正确附录（源代码）：#include<iostream>#include<stdio.h>#include<stdlib.h>#define INF 100#define ERROR 200#define flase 0#define true 1#define maxVnum 100 /* 最大顶点数设为100 */typedef int Vertex; /* 用顶点下标表示顶点,为整型 */ /* 图的邻接表表示法 */typedef int WeightType; /* 边的权值设为整型 */typedef char DataType; /* 顶点存储的数据类型设为字符型 */ using namespace std; int distmaxVnum; int pathmaxVnum; int collectmaxVnum; /BFS存数据的队列typedef struct Que *Queue;struct Que int front; int rear; int datalistmaxVnum;/输出路径的栈typedef struct Str *Strack;struct Str int top; int StrlistmaxVnum;/* 边的定义 */typedef struct ENode *PtrToENode;struct ENode Vertex V1, V2; /* 有向边<V1, V2> */ WeightType Weight; /* 权重 */;typedef PtrToENode Edge;/* 邻接点的定义 */typedef struct AdjVNode *PtrToAdjVNode;struct AdjVNode Vertex AdjV; /* 邻接点下标 */ WeightType Weight; /* 边权重 */ PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */;typedef PtrToAdjVNode ANode;/* 顶点表头结点的定义 */typedef struct Vnode PtrToAdjVNode FirstEdge;/* 边表头指针 */ DataType Data; /* 存顶点的数据 */ /* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */ AdjListmaxVnum; /* AdjList是邻接表类型 */* 图结点的定义 */typedef struct GNode *PtrToGNode;struct GNode int Nv; /* 顶点数 */ int Ne; /* 边数 */ AdjList G; /* 邻接表 */;typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */typedef struct MNode *PtrToMNode;struct MNode int Nv; /* 顶点数 */ int Ne; /* 边数 */ WeightType GmaxVnummaxVnum; /* 邻接矩阵 */;typedef PtrToMNode MGraph; /* 以邻接矩阵存储的图类型 */LGraph CreateGraph( int VertexNum ) /* 初始化一个有VertexNum个顶点但没有边的图 */ Vertex V; LGraph Graph; Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立图 */ Graph->Nv = VertexNum; Graph->Ne = 0; /* 初始化邻接表头指针 */ /* 注意：这里默认顶点编号从1开始，到Graph->Nv */ for (V = 1; V <= Graph->Nv; V+) Graph->GV.FirstEdge = NULL; distV = -1; pathV = -1; return Graph;void InsertEdge( LGraph Graph, Edge E, int c ) PtrToAdjVNode NewNode; /* 插入边 <V1, V2> */ /* 为V2建立新的邻接点 */ NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode); NewNode->AdjV = E->V2; NewNode->Weight = E->Weight; /* 将V2插入V1的表头 */ NewNode->Next = Graph->GE->V1.FirstEdge; Graph->GE->V1.FirstEdge = NewNode; if(c = 2) /* 若是无向图，还要插入边 <V2, V1> */ /* 为V1建立新的邻接点 */ NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode); NewNode->AdjV = E->V1; NewNode->Weight = E->Weight; /* 将V1插入V2的表头 */ NewNode->Next = Graph->GE->V2.FirstEdge; Graph->GE->V2.FirstEdge = NewNode; LGraph BuildGraph() LGraph Graph; Edge E; Vertex V; int Nv, i; cout<<"输入图的顶点个数:" scanf("%d", &Nv); /* 读入顶点个数 */ Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ cout<<"输入图的边数:" scanf("%d", &(Graph->Ne); /* 读入边数 */ int c; cout<<"定义图为(1.有向)(2.无向):" cin>>c; if ( Graph->Ne != 0 ) /* 如果有边 */ E = (Edge)malloc( sizeof(struct ENode) ); /* 建立边结点 */ /* 读入边，格式为"起点 终点 权重" */ for (i=0; i<Graph->Ne; i+) printf("v1,v2,weight:"); scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); /* 注意：如果权重不是整型，Weight的读入格式要改 */ InsertEdge( Graph, E ,c ); return Graph;int VisitedmaxVnum;void clrv(LGraph g) int i; for(i = 1; i <= g->Nv; i+ ) Visitedi = 0;void DFS( LGraph Graph, Vertex V ,int x) /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */ PtrToAdjVNode W; if(x = 1) clrv(Graph); x+; cout<<V<<" " VisitedV = true; /* 标记V已访问 */ for( W=Graph->GV.FirstEdge; W != NULL; W=W->Next ) /* 对V的每个邻接点W->AdjV */ if ( !VisitedW->AdjV ) /* 若W->AdjV未被访问 */ DFS( Graph, W->AdjV,x); /* 则递归访问之 */* 邻接表存储 - 无权图的单源最短路算法 */Queue CreateQueue() Queue Q; Q = (Queue)malloc(sizeof(struct Que); Q->front = -1; Q->rear = -1; return (Q);void AddQ(Queue Q, Vertex S) Q->rear+; Q->datalistQ->rear = S;int DeleteQ(Queue Q) Q->front+; return (Q->datalistQ->front);int IsEmpty(Queue Q) if(Q->front = Q->rear) return 1; else return 0;/* dist和path全部初始化为-1 */void Unweighted ( LGraph Graph, Vertex S ) Queue Q; Vertex V; PtrToAdjVNode W; Q = CreateQueue(); /* 创建空队列, MaxSize为外部