数据结构之-图的基本运算方法

1、数据结构A：实验一图的基本运算方法一、实验目的和要求掌握在图的邻接矩阵和邻接表存储结构实现图的基本运算的算法。学习使用图算法解决应用问题的方法。（1）.验证教材中关于在邻接矩阵和邻接表两种不同存储结构上实现图的基本运算的算法（2）在邻接矩阵和邻接表存储结构上实现图的深度和宽度优先遍历算法。（3）在两种储存结构上面分别实现Dijkstra、prim、Floyd算法飞机最少换乘次数问题。二、实验环境（实验设备）PC计算机，Windows7操作系统,IDE:Codeblocks16.01编译器:GNUGCCCompiler、实验原理及内容程序一：邻接矩阵表示的图的运算本程序包含邻接矩阵表示的图的基本

2、运算，包括插入边，移除边，判断边是否存在，深度优先遍历DFS,宽度优先遍历BFS,单源最短路Dijkstra算法，多源最短路Floyd算法，以及最小生成树prim算法。程序定义了一个图类包含三个数据成员，分别是指向二维数据的指针T*a，记录顶点数的n和记录边数量的e。构造函数负责申请二维数组动态空间，析构函数负责释放空间。类的声明：templateclassMGraphpublic:MGraph(intmSize);MGraph();boolInsert(intu,intv,intw);boolRemove(intu,intv);boolExist(intu,intv)const;voidDF

3、S();voidBFS();voidDijkstra(intv,T*d,int*path);voidFloyd(intdSize,intpathSize);voidprim(intk,int*nearest,T*lowcost);protected:intChoose(int*d,bool*s);voidDFS(intv,bool*visited);voidBFS(intv,bool*visited);T*a;intn,e;(1)深度优先遍历DFS算法图的深度优先遍历重载了两个DFS函数，分别是面向用户的DFS()和私有成员DFS(intv,bool*visited)。面向用户的不带参数版本，

4、首先定义一个一位数组visited来标记当前已经访问过的结点，并初始化为false。为了防止图不是一个连通图，在外层DFS中，要通过一个循环一遍一遍的调用带参数版本的DFS(i,visited),如果图是一个连通图，那么在第一次调用之后，所以的visited都变成true，后续就不再调用，如果图不是一个连通图，那么还要多次调用带参数版本DFS(i,visited)通过这个方法，也可以用来判断图是不是一个连通图。代码：templatevoidMGraph:DFS()inti;bool*visited=newbooln;for(i=0;in;i+)visitedi=false;for(i=0;in

5、;i+)if(visitedi=false)DFS(i,visited);coutendl;deletevisited;templatevoidMGraph:DFS(intv,bool*visited)visitedv=true;printf(%d,v);for(intu=0;un;u+)false)if(avu!=INF&visitedu=DFS(u,visited);算法分析：深度优先遍历，没嵌套调用一次，实际是对一个顶点V查看所有的邻接点,设图有n个顶点，时间复杂度是O(2)空间复杂度：由于要定义一个临时数组标记访问过的顶点，所以空间复杂度是O(n)。(2)宽度优先遍历BFS图的宽度优先

6、遍历BFS重载了两个版本，一个是面向用户的不带参数版本，一个是带参数版本。不带参数版本的作用主要是为了防止图不是一个连通图，导致不能访问所有顶点，所有通过一个循环来一遍一遍调用带参数版本BFS，与DFS类似，如果图是一个连通图，那么第一次调用就能访问所有顶点，如果不是连通图，得多次调用，通过此方法也可以判断是不是连通图。带参数版本BFS通过队列来实现宽度优先遍历，首先将第一个顶点加入队列，然后，每次从队列取出一个顶点，并将与之相邻并且还没有访问过的顶点加入到队列，直到队列为空停止。为了代码简洁，队列使用了STL库的queue头文件。代码：templatevoidMGraph:BFS()inti

7、;bool*visited=newbooln;for(i=0;in;i+)visitedi=false;for(i=0;in;i+)if(visitedi=false)BFS(i,visited);coutendl;deletevisited;templatevoidMGraph:BFS(intv,bool*visited)queueQ;visitedv=true;Q.push(v);while(!Q.empty()v=Q.front();Q.pop();coutv;for(inti=0;in;i+)if(visitedi=false&avi!=INF)visitedi=true;Q.push

8、(i);算法分析：每个顶点只进入一次队列，对于每个从队列取走的点，都查看其所有的邻接点，设顶点数是n,边数是e,时间复杂度是O(2)空间复杂度：同样需要定义临时数组标记访问过的顶点,队列中元素个数不超过n个，所以空间复杂度是O(n)。(3)prim最小生成树算法prim算法的整体思路为，首先加入一个顶点到生成树中,然后，每次加入一条代价最小的边，边的一个顶点已被加入生成树，一个顶点未被加入生成树，然后标记这个边的顶点，表示将这个顶点也加入，加入之后更新其lowcost数组，然后继续选边，直到所有顶点都被标记。定义三个临时数组，mark数组来实现上述标记，lowcostj记录与顶点j相接的边中最

9、小的权值（边的另一个顶点未被标记)，nearestj表示顶点j上述最小权值边的另一个顶点。主函数打印最小生成树的边集(nearestj,j,lowcostj)代码：templatevoidMGraph:prim(intk,int*nearest,T*lowcost)bool*mark=newbooln;if(kn-1)printf(outofboundsn);return;for(inti=0;in;i+)nearesti=-1;lowcosti=INF;marki=false;lowcostk=0;nearestk=k;markk=true;intcnt=n-1;while(cnt-)for

10、(inti=0;iaki)lowcosti=aki;nearesti=k;Tminn=INF;for(intj=0;jn;j+)if(!markj)&(lowcostjminn)minn=lowcostj;k=j;markk=true;算法分析：由于要加入n个顶点，每次加入都要找最小边和更新lowcost,所以时间复杂度是O(nA2)o空间复杂度：定义两个一维数组，空间复杂度是O(n)Dijkstra单源最短路算法Dijkstra的整体思路是，首先加入起点到s集合中，然后更新与之相邻的顶点的数组d的值，然后每次选择不在s中并且dj最小的顶点，将顶点加入到s集合，并更新与这个顶点相邻的顶点dj的

11、值，然后再选择不在s中并且dj最小的顶点，如此重复n-1次，将所有顶点都加入s中。利用s数组来标记是不是在集合s中，调用choose函数来选择不在s中且d最小的顶点，每次更新d的时候也要更新path数组来记录路径。代码：templatevoidMGraph:Dijkstra(intv,T*d,int*path)inti,k,w;if(vn-1)coutoutofbounds!endl;return;bool*s=newbooln;for(i=0;in;i+)si=false;di=avi;if(i!=v&diINF)pathi=v;elsepathi=-1;sv=true;dv=0;for(i

12、=1;in;i+)k=Choose(d,s);sk=true;for(w=0;wn;w+)if(!sw&dk+akwdw)dw=dk+akw;pathw=k;算法复杂度：要加入n-1个顶点，每次加入都要调用choose函数,choose函数时间复杂度是O(n),综上,时间复杂度是0(22)。空间复杂度：定义path数组，d数组，和s数组，都是一维数组，空间复杂度是O(n)。(5)Floyd多源最短路算法Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法其状态转移方程如下：mapi,j:=minmapi,k+mapk,j,mapi,j；mapi,j表示

13、i到j的最短距离，K是穷举i,j的断点，mapn,n初值应该为0，或者按照题目意思来做。算法过程为，首先，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。然后，对于每一对顶点u和v,看看是否存在一个顶点w使得从u到w再到v比已知的路径更短。如果存在则更新它。代码：templatevoidMGraph:Floyd(intdSize,intpathSize)inti,j,k;for(inti=0;in;i+)for(intj=0;jn;j+)dij=aij;if(i!=j&aijINF)pathij=i;elsepathij=-1;for(k=0;kn;k

14、+)for(i=0;in;i+)for(j=0;jn;j+)if(dik+dkjdij)dij=dik+dkj;pathij=pathkj;算法分析：时间复杂度是O(3)，用二维数组保存结果，空间复杂度是O(2)。程序测试：输入课本179页下方图结果正确程序测试:176页上方图结果正确。程序二：邻接表表示的图的基本运算本程序包含邻接表表示的图的基本运算，包括插入边，移除边，判断边是否存在，深度优先遍历DFS,宽度优先遍历BFS，单源最短路Dijkstra算法，多源最短路Floyd算法，以及最小生成树prim算法。程序定义了一个图类包含三个数据成员，分别是指向vector的数组的指针,记录顶点数

15、的n和记录边数量的e。构造函数负责申请n个vector数组，Mi为一个vector数组，存放顶点i相接的边，相当于链表，为了代码的简洁，程序用STL库的vector代替了链表。析构函数负责释放空间。Vector的元素类型为定义的结构体表示的边，边上有两个属性，分别是边的另一侧的顶点值，和边的权值。表示边的结构体：structedgeintto;intcost;edge(intx,inty)to=x;cost=y;表示边的图例说明：类的声明：templateclassLGraphprivate:vector*M;intn;inte;voidDFS(intu,bool*vis);voidBFS(i

16、ntv,bool*vis);public:LGraph(intmSize);LGraph();boolInsert(intu,intv,intw);boolExist(intu,intv);boolRemove(intu,intv);voidDijkstra(intv,T*d,int*path);voidprim(intk,int*nearest,T*lowcost);voidFloyd(intdSize,intpathSize);voidDFS();voidBFS();类的图例说明:(1)构造函数负责申请n个vector数组，用来存放邻接边代码：templateLGraph:LGraph(i

17、ntmSize)M=newvectormSize;n=mSize;e=0;(2)插入函数InsertInsert函数首先判断插入的边是否存在，如果存在返回false不存在则插入边，插入的时候首先构造一个边，然后调用vector的push_back函数插入。代码：templateboolLGraph:Insert(intu,intv,intw)inti;if(u0|un-1|un-1)returnfalse;for(i=0;iboolLGraph:Remove(intu,intv)inti;if(u0|vn-1|vn-1)returnfalse;for(i=0;iMu.size();i+)if(

18、Mui.to=v)Mu.erase(Mu.begin()+i);returntrue;returnfalse;(4)深度优先遍历DFS与上面邻接矩阵的DFS类似，邻接表由于直接记录与当前顶点相邻的顶点，所有循环的时候不需要遍历所有顶点判断INF,循环的时间复杂度更加低。思路与邻接矩阵类似，但是由于邻接表在插入的时候没有考虑顺序，导致每个顶点后面接的顶点不一定按照从小到大的顺序排列，而邻接矩阵循环是从0到n-1按照从小到大的顺序来的，所以为了保持和邻接矩阵的一致性，在DFS的时候第一步首先将每个vector进行排序，将vector中元素按照边的另一头顶点从小到大的顺序排列，调用STL中的头文件中

19、的sort传入函数参数cmpcmp定义：intcmp(edgea,edgeb)returna.tob.to;DFS代码：templatevoidLGraph:DFS()for(inti=0;in;i+)sort(Mi.begin(),Mi.end(),cmp);inti;bool*vis=newbooln+1;for(i=0;in;i+)visi=false;for(i=0;in;i+)if(visi=false)DFS(i,vis);deletevis;coutendl;templatevoidLGraph:DFS(intv,bool*vis)visv=true;printf(%d,v);i

20、nti;for(i=0;iMv.size();i+)intt=Mvi.to;if(vist=false)DFS(t,vis);算法分析：深度优先遍历，没嵌套调用一次，实际是对一个顶点v查看所有的邻接点，设图有n个顶点，时间复杂度是O(n+e)。空间复杂度是O(n)。(5)宽度优先遍历BFSBFS与邻接矩阵类似，重载了两个版本，一个是面向用户的不带参数版本，一个是带参数版本。不带参数版本的作用主要是为了防止图不是一个连通图，导致不能访问所有顶点，所有通过一个循环来一遍一遍调用带参数版本BFS,与DFS类似，如果图是一个连通图，那么第一次调用就能访问所有顶点，如果不是连通图，得多次调用，通过此方法

21、也可以判断是不是连通图。带参数版本BFS通过队列来实现宽度优先遍历，首先将第一个顶点加入队列，然后，每次从队列取出一个顶点，并将与之相邻并且还没有访问过的顶点加入到队列，直到队列为空停止。为了代码简洁，队列使用了STL库的queue头文件。代码：templatevoidLGraph:BFS()inti;bool*vi=newbooln;for(i=0;in;i+)vii=false;for(i=0;in;i+)if(vii=false)BFS(i,vi);coutendl;deletevi;templatevoidLGraph:BFS(intv,bool*vi)inti;viv=true;qu

22、eueQ;Q.push(v);while(!Q.empty()v=Q.front();printf(%d,v);Q.pop();for(i=0;iMv.size();i+)intt=Mvi.to;if(vit=false)Q.push(t);vit=true;算法分析：每个顶点只进入一次队列，对于每个从队列取走的点，都查看其所有的邻接点，设顶点数是n,边数是e,时间复杂度是O(n+e)。空间复杂度：队列中元素个数不超过n个，同时需要定义数组标记已访问过的顶点，所以空间复杂度是O(n)。(6)prim最小生成树算法邻接表的prim算法与邻接矩阵类似，只是在循环的时候稍有不同，要注意邻接点是edg

23、e中的to元素。算法的整体思路为，首先加入一个顶点到生成树中，然后，每次加入一条代价最小的边，边的一个顶点已被加入生成树，一个顶点未被加入生成树，然后标记这个边的顶点，表示将这个顶点也加入，加入之后更新其lowcost数组，然后继续选边，直到所有顶点都被标记。定义三个临时数组，mark数组来实现上述标记，lowcostj记录与顶点j相接的边中最小的权值(边的另一个顶点未被标记)，nearestj表示顶点j上述最小权值边的另一个顶点。主函数打印最小生成树的边集(nearestj,j,lowcostj)代码：templatevoidLGraph:prim(intk,int*nearest,T*lo

24、wcost)bool*mark=newbooln+1;for(inti=0;in;i+)nearesti=-1;marki=false;lowcosti=INF;markk=true;lowcostk=0;nearestk=k;for(inti=1;in;i+)for(intj=0;jMkj.cost&!(markt)lowcostt=Mkj.cost;nearestt=k;intmin=INF;for(intj=0;jn;j+)if(!markj&lowcostjmin)min=lowcostj;k=j;markk=true;deletemark;算法分析：由于要加入n个顶点，每次加入都要找

25、最小边和更新lowcost，所以时间复杂度是O(2)。空间复杂度：定义两个一维数组，空间复杂度是O(n)(7)Dijkstra单源最短路算法算法思路与邻接矩阵类似，不同的地方是开始的时候要将d数组和path数组分别赋值为INF何-1,将s数组赋值为false,然后将图中与参数v相邻的顶点的d赋值为边的权值。整体思路是，首先加入起点到s集合中，然后更新与之相邻的顶点的数组d的值，然后每次选择不在s中并且dj最小的顶点，将顶点加入到s集合，并更新与这个顶点相邻的顶点dj的值，然后再选择不在s中并且dj最小的顶点，如此重复n-1次，将所有顶点都加入s中。利用s数组来标记是不是在集合s中，调用choo

26、se函数来选择不在s中且d最小的顶点，每次更新d的时候也要更新path数组来记录路径。代码：templatevoidLGraph:Dijkstra(intv,T*d,int*path)inti;bool*s=newbooln;for(i=0;in;i+)di=INF;pathi=-1;si=false;for(i=0;iMv.size();i+)intt=Mvi.to;dt=Mvi.cost;patht=v;sv=true;dv=0;for(i=1;in;i+)intindex=-1;intmin=INF;for(intj=0;jn;j+)if(sj=false&dj=min)min=dj;i

27、ndex=j;sindex=true;for(intk=0;kMindex.size();k+)intt=Mindexk.to;if(dindex+Mindexk.costdt&st=false)dt=dindex+Mindexk.cost;patht=index;deletes;算法复杂度：要加入n-1个顶点，每次加入都要调用choose函数，choose函数时间复杂度是O(n),综上，时间复杂度是O(nA2)o空间复杂度：定义path数组，d数组，和s数组，都是一维数组，空间复杂度是O(n)。(8)Floyd多源最短路算法算法与邻接矩阵类似，要做稍微改动，首先要将d和path数组分别赋值为

28、INF和-1,然后根据邻接表在赋值d和path，这样才能保证，边不存在的情况下dij=INF，pathij=-1。整体是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，其状态转移方程为mapi,j:=minmapi,k+mapk,j,mapi,j。mapi,j表示i至Uj的最短距离，K是穷举i,j的断点，mapn,n初值应该为0。算法过程为，首先，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。然后，对于每一对顶点u和v,看看是否存在一个顶点w使得从u至w再至v比已知的路径更短。如果存在则更新它。代码：templatevoidLGra

29、ph:Floyd(intdSizeSize,intpathSizeSize)for(inti=0;iSize;i+)for(intj=0;jSize;j+)dij=INF;pathij=-1;for(inti=0;in;i+)for(intj=0;jMi.size();j+)intt=Mij.to;dit=Mij.cost;pathit=i;for(intk=0;kn;k+)for(inti=0;in;i+)for(intj=0;jn;j+)if(dik+dkjdij)dij=dik+dkj;pathij=pathkj;程序测试：课本179页下方图C:Use5ZLDesktopXexercis

30、:邹摆表binDebug圄请靛6悟输入枸垄有问至込是无向團？1，无冇囹2.苣向艮请输入有巨边门个频11请输入&条有向边015041Up70b210(20H21Ri3_202315bJJk330Fi)FLuytl请端/、起屯和终点02-3-1-MFLuyd请绻人起巨和终点.F.最短路长克足：煮路径为:FLuyd请绻人起巨和终点.2最毎路匚麦足：4路径为:2-3-1-4FLoyd请绻/、起巨f口餐点、000000停止:停止:停止:停止:输入2愉入2愉入结果正确程序测试:课本176页上方图匚:UsersZLDesktapexercise圏迪觀耘JbinDebug刮，”一请输入顶佢数:6帯鉞杓茬有冃至

31、込是无向罰1无冇團-有问屋1谓输入无向边的个数1J请输入2GEGGC0条兀向边n-.只035021TOC o 1-5 h z1b3512ini254pHEZ-5hoyd请编人起点和终点，输入00停止:1尉亘路匸走足:蹈径再:1-/4FLoyd请献起点和终点，输入00停止:4u尉亘路氏袞是：7臨铮:4：2：0结果正确程序三：飞机换乘问题1)设有n个城市，编号为0n-1,m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。(2)参考：可以使用有向图表示城市间的航线；只要两城市间有航班，则图中这两点间存在一条权值为1的边；可以使用Dijkstra算法实现。问题分析:可以直接使用上面的

32、邻接矩阵或者邻接表的图来解决这个问题，由于求的是最小换乘次数，所以如果两个顶点存在航线，只要将边的权值赋值为1，不存在航线则为INF。在Insert函数做下修改，然后直接调用Dijkstra函数即可。如果dxy=INF说明不存在换乘方案。代码：templateclassMGraphpublic:MGraph(intmSize);MGraph();boolInsert(intu,intv);voidDijkstra(intv,T*d,int*path);protected:intChoose(int*d,bool*s);T*a;intn,e;templateMGraph:MGraph(intmSize)n=mSize;e=0;a=newT*n;for(inti=0;in;i+)ai=newTn;for(intj=0;jn;j+)aij=INF;aii=0;MGraph:MGraph()for(inti=0;in;i+)deleteai;deletea;templateboolMGraph:Insert(intu,intv)if(u0|vn-1|vn-1|u=v)returnfalse;if(auv!=INF)returnfalse