数据结构图资料.pptx

《数据结构图资料.pptx》由会员分享，可在线阅读，更多相关《数据结构图资料.pptx（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、17.1 图的基本概念7.1.1图的定义图中的数据元素称为顶点。在顶点集合V中，第i个顶点记作vi图中两个顶点vi和vj之间有关联关系，称作顶点vi和vj之间有一条边。在边集合E中，第k条边记作ek=。图是由顶点的非空有限集合与顶点间关系集合构成的数据结构。记作G=(V,E)。其中，V为顶点集合，E为顶点间关系边的集合。无向图：由没有方向的边构成的图称为无向图。无向图中的边由顶点的无序偶对组成，因此，在无向图中，顶点偶对与顶点偶对表示同一条边，记作(vi,vj)。第1页/共50页27.1.1图的定义 有向图：由有方向的边构成的图称为有向图。弧：有向图中的边由顶点的有序偶对组成。顶点偶对表示从顶

2、点vi指向顶点vj的一条有向边，也称为弧。顶点vi是有向边的始点，也称为弧尾。顶点vj是有向边的终点，也称为弧头。第2页/共50页37.1.1图的定义 完全图：含有n个顶点和条边的无向图称为完全图。在完全图中，任意两个顶点之间均有边相连推论1：具有n个顶点的无向图最多有条边。有向完全图：含有n个顶点和n(n-1)条弧的有向图称为有向完全图。在有向完全图中，任意两个顶点之间均有两条方向相反的弧。推论2：具有n个顶点的有向图最多有n(n-1)条弧。第3页/共50页47.1.1图的定义邻接点：在无向图中，若存在一条边(vi,vj)，则称vi和vj互为邻接点。称边(vi,vj)依附于顶点vi和vj或称

3、边(vi,vj)与顶点vi和vj相关联。顶点的度：在无向图中，与顶点v相关联的边数称为顶点v的度，记作TD(v)。在有向图中，顶点的度又分为顶点的入度和顶点的出度。顶点的入度是指以顶点v为弧头的弧的数目，记作ID(v)；顶点的出度是指以顶点v为弧尾的弧的数目，记作OD(v)。顶点v的度等于顶点v的入度和出度之和，即TD(v)=ID(v)+OD(v)。推论3：对于无向图，其总度数是总边数的两倍。推论4：对于有向图，其总入度、总出度和总边数相等。第4页/共50页57.1.1图的定义路径：在图G中，从顶点vi出发，经过一系列的边或弧能够到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点

4、vj的路径。该路径上所包含的边的数目称为路径长度简单路径：若路径上各顶点互不重复，则称这样的路径为简单路径。环或回路：若路径上第一个顶点和最后一个顶点相同，则称这样的路径为环或回路。子图：对于图G=V,E和图G=V,E，若存在V V且E E，则称图G是图G的子图。第5页/共50页67.1.1图的定义连通图：在无向图中，若从顶点vi到顶点vj有路径存在，则称vi和vj是连通的。如果无向图中任意两个顶点都是连通的，则称该无向图为连通图。否则，就是非连通图。无向图中的极大连通子图称为该图的连通分量。推论5：连通图的连通分量就是它本身。强连通图：在有向图中，若一对顶点vi和vj（vivj）存在从vi到

5、vj和从vj到vi的有向路径，则称vi和vj是连通的。若有向图中任意两个顶点vi和vj（vivj）之间都是连通的，则称该有向图为强连通图。有向图中的极大强连通子图称为强连通分量。第6页/共50页77.1.1图的定义权：图中边或弧上附带的数据称为权。网：带权的图称为网。生成树：包含连通图全部顶点的极小连通子图称作该图的生成树。即以最少的边连接连通图中所有顶点。推论6：有n个顶点的连通图，它的生成树一定包含n个顶点和n-1条边。若加上一条边则构成环，若减去一条边则是非连通图。第7页/共50页87.1.2 图的抽象数据类型 ADT Graph数据元素集合：具有相同性质的称为顶点的有限数据元素集合，以

6、及称为弧或边的有限集合。基本操作：创建图(CreateGraph)：按顶点和弧的定义构造图 查找顶点(LocateVex)：返回指定顶点在图中的位置取顶点值(GetVex)：返回指定顶点的值给顶点赋值(PetVex)：给指定顶点赋值 取第一个邻接点(FirstAdjVex)：取顶点的第一个邻接点取下一个邻接点(NextAdjVex)：取顶点的下一个邻接点插入顶点(InsertVex)：在图中插入新顶点 删除顶点(DeleteVex)：在图中删除指定顶点及相关的弧插入弧(InsertArc)：在图中插入一条新弧删除弧(DeleteArc)：在图中删除指定的弧深度优先遍历(DFSTraverse)

7、：对图进行深度优先遍历广度优先遍历(BFSTraverse)：对图进行广度优先遍历第8页/共50页97.2 图的存储结构 7.2.1 邻接矩阵 邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个具有n个顶点的图。它的顶点集合V=v0,v1,vn-1，则顶点间的关系E可用如下形式的矩阵A描述。对于A中的每一个元素aij满足：第9页/共50页107.2.1 邻接矩阵【例7-2】对于图7-2（a）所示的无向图，请给出它的邻接矩阵，并根据邻接矩阵计算顶点v2的度。第10页/共50页117.2.1 邻接矩阵 对于带权图（网），邻接矩阵A中的元素定义为：【例7-4】对于图7-5（b）所示的网，请

8、给出它的邻接矩阵。第11页/共50页127.2.1 邻接矩阵 用C语言描述的邻接矩阵：#define MAXVEX 50/*最大顶点个数*/typedef int weight;/*权值*/typedef structweight arcsMAXVEXMAXVEX;/*邻接矩阵*/DataType dataMAXVEX;/*顶点信息*int vexs;/*顶点数*/MGraph,*AdjMetrix;第12页/共50页137.2.1 邻接矩阵 2.邻接矩阵的操作（1）创建邻接矩阵 void CreateGraph(AdjMetrix g,int mMAXVEX,DataType d,int n

9、)int i,j;g-vexs=n;for(i=0;idatai=di;for(j=0;jarcsi j=mi j;第13页/共50页147.2.1 邻接矩阵（3）取第一个邻接点int GetFirst(AdjMetrix g,int k)int i;if(kg-vexs)printf(参数k超出范围！n);return-1;for(i=0;ivexs;i+)if(g-arcski=1)return i;return-1;第14页/共50页157.2.1 邻接矩阵（4）取下一个邻接点 int GetNext(AdjMetrix g,int k,int t)int i;if(kg-vexs|tg

10、-vexs)printf(参数k或t超出范围！n);return NULL;for(i=t+1;ivexs;i+)if(g-arcski=1)return i;return-1;第15页/共50页167.2.1 邻接矩阵（7）插入边 void InsertArc(AdjMetrix g,int u,int v,weight w)if(ug-vexs|vg-vexs)printf(参数u或v超出范围！n);return;g-arcsuv=w;（8）删除边 void DeleteArc(AdjMetrix g,int u,int v)if(ug-vexs|vg-vexs)printf(参数u或v超

11、出范围！n);return;g-arcsuv=0;第16页/共50页177.2.2 邻接表 邻接表是图的链式存储结构。邻接表由边表和顶点表组成边表：对图中的每个顶点建立的单链表，单链表中存放与同一个顶点相邻接的邻接点，相当于邻接矩阵中的一行顶点表：存放图中每个顶点的信息以及指向该顶点边表的头指针。顶点表通常采用顺序存储结构。边表的结点结构：adjvex为邻接点在顶点表中的序号，next指向下一个邻接点的指针。顶点表的结点结构：data存放顶点信息，head为边表头指针 逆邻接表：结构与邻接表完全相同，只是边表中每个结点存放的是每条弧的弧尾顶点。第17页/共50页187.2.2 邻接表 C语言描

12、述的邻接表：#define MAXVEX 50typedef struct arc/*边表结点类型*int adjvex;/*顶点序号*struct arc*next;/*指向下一个邻接点*/ArcNode,*PArcNode;typedef struct/*顶点表结点类型*DataType data;/*顶点信息*ArcNode*head;/*边表头指针*/VexNode;typedef struct/*邻接表类型*VexNode listsMAXVEX;/*顶点表*int edges,vexs;/*边数，顶点数*/VGraph,*AdjList;第18页/共50页197.2.2 邻接表【例

13、7-6】为图7-2（b）所示的图G1建立邻接表和逆邻接表。第19页/共50页207.2.2 邻接表 2.邻接表的操作（1）创建邻接表 void CreateGraph(AdjList*g,int mMAXVEX,int n)/*n为顶点总数*/int i,j;PArcNode p;*g=(AdjList)malloc(sizeof(VGraph);/*初始化邻接表*/(*g)-edges=0;(*g)-vexs=n;for(i=0;ilistsi.head=NULL;/*边表头指针初始化*/for(j=n-1;j=0;j-)if(mij!=0)/*矩阵元素不为0，则在边表中生成一个结点*/p=

14、(PArcNode)malloc(sizeof(ArcNode);p-adjvex=j;p-next=(*g)-listsi.head;/*从链表头部插入新结点*/(*g)-listsi.head=p;(*g)-edges+;第20页/共50页217.2.2 邻接表（3）寻找第一个邻接点 int GetFirst(AdjList g,int k)if(kg-vexs)printf(参数k超出范围！n);return-1;if(g-listsk.head=NULL)return-1;elsereturn g-listsk.head-adjvex;第21页/共50页227.2.2 邻接表（4）寻找

15、下一个邻接点 int GetNext(AdjList g,int k,int u)PArcNode p;if(kg-vexs|ug-vexs)printf(参数k或u超出范围！n);return-1;p=g-listsk.head;/*寻找u*/while(p-next!=NULL&p-adjvex!=u)p=p-next;if(p-next=NULL)return-1;else return p-next-adjvex;/*u的next指针域指向下一个邻接点*/第22页/共50页237.3 图的遍历 7.3.1 深度优先搜索1.连通图的深度优先搜索遍历（1）遍历方法 从图中指定的顶点v出发，

16、先访问v，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到为止。【例7-10】从右图所示的无向图的顶点A出发，深度优先搜索遍历图，并写出遍历序列。遍历序列：ABCDEFGH。第23页/共50页247.3.1 深度优先搜索（2）具体实现 以邻接矩阵作为存储结构。建立一个标识数组visited，用于标识顶点是否被访问过。void DFSTraverse(AdjMetrix g)int i,visitedMAXVEX;for(i=0;ivexs;i+)/*初始化visited数组*/visitedi=0;for(i=0;ivexs;i+)if(visite

17、di=0)DFS(g,i,visited);第24页/共50页257.3.2 广度优先搜索1.连通图的广度优先搜索遍历（1）遍历方法 从图中指定的顶点v出发，先访问v，再依次访问v的未被访问的所有邻接点wi，然后分别从这些邻接点wi出发依次访问它们的未被访问的所有邻接点tj。依此类推，直至图中所有顶点均被访问过为止【例7-11】从右图所示的无向图的顶点A出发，广度优先搜索遍历图，并写出遍历序列。遍历序列：ABHCGDFE。第25页/共50页267.3.2 广度优先搜索（2）具体实现以邻接表作为存储结构。建立一个标识数组visited，用于标识顶点是否被访问过。设置一个队列queue，用于保存访

18、问邻接点的次序。void BFS(AdjList g,int v,int visited)int u,queueMAXVEX;/*循环队列*/int front=0,rear=0;/*队头、队尾指针，int w;/*v的邻接点*/printf(%d,g-listsv.data);/*访问顶点v*/visitedv=1;queuerear=v;/*v已被访问过,且入队*/第26页/共50页277.3.2 广度优先搜索rear=(rear+1)%MAXVEX;while(frontlistsw.data);visitedw=1;queuerear=w;rear=(rear+1)%MAXVEX;w=

19、GetNext(g,u,w);/*取下一个邻接点*/第27页/共50页287.3.2 广度优先搜索2.非连通图的广度优先搜索遍历 void BFSTraverse(AdjList g)int i;int visitedMAXVEX;for(i=0;ivexs;i+)visitedi=0;for(i=0;ivexs;i+)if(visitedi=0)BFS(g,i,visited);第28页/共50页297.3.2 广度优先搜索【例7-12】对于下图所示的无向图，求：（1）邻接表。（2）按照邻接表，给出从顶点A出发深度优先搜索遍历序列（3）按照邻接表，给出从顶点C出发广度优先搜索遍历序列 深度优

20、先搜索遍历序列：ABCDE。广度优先搜索遍历序列：CABDE。第29页/共50页307.4 最小生成树 带权图的生成树的边也带权。在这些带权的生成树中必有一颗边的权值之和最小的生成树，这颗生成树就是最小（代价）生成树。7.4.1 普里姆算法 算法的基本思想：设G=(V,E)是连通网，V是连通网中顶点集合，E是连通网中边的集合。T=(U,D)是正在构造的最小生成树，U是最小生成树的顶点的集合，D是最小生成树的边的集合。V-U表示属于集合V，但不属于集合U的顶点集合。第30页/共50页317.4.1 普里姆算法（1）若从顶点v0开始构造最小生成树，则从集合V中取出顶点v0放入集合U中。此时，集合U

21、=v0，集合V-U=除v0以外的所有顶点，集合D为空。（2）若在集合U中的顶点vi和集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不构成回路。将顶点vj加入集合U中，将边(vi,vj)加入集合D中。（3）重复步骤（2），直至U与V相等为止。此时，D中必有n-1条边，则T=(U,D)即是最小生成树。【例7-15】已知一个如图所示的带权图，请给出根据普里姆算法构造的一颗最小生成树（假设从顶点1开始构造）。第31页/共50页327.4.1 普里姆算法 第32页/共50页337.4.1 普里姆算法 2.具体实现 设置两个数组lowcost和uset。lowcostv存放集合U中的顶点

22、u和集合V-U中的顶点v构成的权值最小的边(v,u)的权值；uset数组存放U集合中的顶点和V-U集合中的顶点，当usetu=0时，表示顶点u在集合U中，当usetu=1时，表示顶点u在集合V-U中。每次从lowcost数组中寻找权值最小的边。若找到，则把顶点v加入到集合U中，即置usetv为0。当顶点v从集合V-U加入到集合U后，更新lowcostv的权值。若存在一条边(v,u)，它的权值比原先lowcostv的权值小，则用新的权值更新lowcostv。第33页/共50页347.4.1 普里姆算法 void Prim(AdjMetrix g,int v)weight lowcostMAXVE

23、X;int usetMAXVEX;int i,j,MinEdge,MinWeight,k;for(i=0;ivexs;i+)/*初始化lowcost和uset数组*/lowcosti=g-arcsvi;useti=1;usetv=0;/*把起始点放到最小生成树中*/printf(起始点%cn,g-datav);for(i=1;ivexs;i+)第34页/共50页357.4.1 普里姆算法MinWeight=MAXWEIGHT;/*初始化最小权值*/for(j=0;jvexs;j+)if(usetj&lowcostjMinWeight)/*寻找权值最小的边*/MinWeight=lowcostj

24、;MinEdge=j;/*权值最小边的弧尾顶点*/for(j=0;jvexs;j+)/*寻找权值最小边的弧头顶点*/if(g-arcsjMinEdge=MinWeight)k=j;printf(边(%c,%c)t权值%dn,g-datak,g-dataMinEdge,MinWeight);usetMinEdge=0;v=MinEdge;/*权值最小的边加入最小生成树*/for(j=0;jvexs;j+)/*更新最小权值*/if(usetj&g-arcsvjarcsvj;第35页/共50页367.4.2 克鲁斯卡尔算法算法思想：1.设G=(V,E)是一个具有n个顶点的带权连通图，T=(U,D)是

25、G的最小生成树。2.初始时，U中包含G的全部n个顶点，D为空。3.从E中选择一条以前未选择过的、边上的权值最小的边加入D中。若加入后，并未使T形成回路，则继续选择下一条边；若加入后，使T形成回路，则放弃选择的边。4.重复以上过程，直至D中包含了n-1条边为止。此时，T即为G的最小生成树。第36页/共50页377.4.2 克鲁斯卡尔算法【例7-17】已知一个带权图如图7-14（a）所示，请给出根据克鲁斯卡尔算法构造的一颗最小生成树 第37页/共50页387.5 最短路径 7.5.1 从某个顶点到其余顶点的最短路径 带权图的路径长度是指路径所经过的所有边上的权值之和。图的顶点间可能存在多条路径，其

26、中路径长度最短的路径称为最短路径。最短路径分为两种情况：从图中某个顶点到其余顶点间的最短路径 图中每对顶点之间的最短路径。第38页/共50页397.5.1 从某个顶点到其余顶点的最短路径1.迪杰斯特拉算法（1）初始时，集合V中仅包含源点v，集合W中包含除源点v以外的所有顶点，v到W中各顶点的路径长度或为边的权值（有边相连），或为（没边相连）。（2）按最短路径长度递增的次序，从集合W中选出到顶点v路径长度最短的顶点w，把它加入到集合V中。（3）加入w后，为了寻找下一个最短路径，必须修改从v到集合W中剩余顶点vi的最短路径长度值。若在路径上加入顶点w后，使v到vi的路径长度比原来没有加入v时的路径

27、长度短，则修正v到vi的路径长度为较短者。（4）重复以上过程，直至集合W中的顶点全部加入到集合V中为止。第39页/共50页407.5.1 从某个顶点到其余顶点的最短路径【例7-18】已知一个带权图如图所示，请给出从顶点A到图中其余顶点的最短路径。第40页/共50页417.6 拓扑排序和关键路径7.6.1拓扑排序 在有向图中，如果用图中的顶点表示活动（事件、任务），用弧（有向边）表示活动间的先后关系，则称这样的有向图为顶点活动网（Activity On Vertex Network），简称AOV网。对于一个AOV网，若存在满足以下性质的一个线性序列：网中的所有顶点都在该序列中。在AOV网中，从顶

28、点vi到顶点vj存在一条路径，则在线性序列中，vi一定排在vj的前面。则这个线性序列称为拓扑序列。构造拓扑序列的操作称为拓扑排序。第41页/共50页427.6.1拓扑排序 拓扑排序的方法：（1）在有向图中，选择一个入度为0的顶点并输出它。（2）在图中，把该顶点连同它发出的全部有向边一并删除。（3）重复（1）和（2）步骤，直至图中不再有入度为0的顶点为止。【例7-20】已知一个带权图如图所示，请给出图的拓扑有序序列。第42页/共50页437.6.2关键路径 在带权有向图中，如果用顶点表示事件，用有向边表示活动，边上的权值表示活动持续的时间，则称这样的有向图为边表示活动的网（Activity On

29、 Edge Network），简称AOE网。对一个只有开始点和一个完成点的工程，可用AOE网来表示。网中仅有一个入度为0的顶点称作源点，它表示工程的开始点。同时，网中也仅有一个出度为0的顶点称为汇点，它表示工程的完成点。在AOE网中，从源点到汇点之间可能有多条路径，这些路径中具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动。第43页/共50页447.6.2关键路径（1）事件的最早发生时间 vk的最早发生时间se(k)是从源点到顶点vk的最大路径长度。计算事件vk最早发生时间的递推公式：（2）事件的最迟发生时间 vk的最迟发生时间le(k)是在不推迟整个工程工期的前提下，该事件最

30、迟发生的时间。递推公式：第44页/共50页457.6.2关键路径（3）活动的最早开始时间 若用弧表示活动ai，则根据AOE网的性质，只有事件vk发生了，活动ai才能开始，即活动ai的最早开始时间e(i)等于事件vk的最早发生时间：e(i)=se(k)。（4）活动的最迟开始时间 活动ai的最迟开始时间l(i)是在整个工期按期完工的前提下，ai必须开始的最迟时间。若用有向边表示活动ai，则活动ai最迟开始时间：第45页/共50页467.6.2关键路径（5）活动的时间余量 活动ai的最迟开始时间l(i)与最早开始时间e(i)之差定义为活动ai的时间余量sp(i)。它表示在不影响整个工程工期的前提下，

31、活动ai可以拖延的时间。确定关键路径的方法：求出所有事件的最早发生时间和最迟发生时间；利用它们再求出所有活动的最早开始时间和最迟开始时间；根据活动的时间余量是否为零确定关键活动。关键活动所在的路径就是关键路径。第46页/共50页477.7 综合实例故宫导游咨询 游客游览某一景点时，对景点都不熟悉。特别是对于象故宫这样的大型景点，如果随便参观的话，可能会错过一些景点，也可能走许多冤枉路。为了方便游客，需要一套软件系统，能够为游客提供以下功能：查询景点信息；给出到某个景点的最佳路线；给出到所有景点的最佳路线。为系统管理员提供以下功能：添加和撤销景点；添加和撤销旅游线路；修改景点信息。第47页/共50页487.7 综合实例故宫导游咨询 分析：景点和旅游线路可以构成图状结构，景点作为图的顶点，旅游线路作为图的边，边上的权值作为景点间的距离。查询景点信息就是输出相应顶点的信息；给出到景点的最佳线路就是求最短路径问题；添加和撤销景点、旅游线路就是添加和删除顶点、边；修改景点信息就是修改顶点信息。第48页/共50页497.7 综合实例故宫导游咨询1.数据结构 2.操作实现（1）根据景点名称查询景点信息（2）根据景点名称查找景点序号（3）显示最短路径（4）求最短路径 3.主函数 第49页/共50页50感谢您的观看。第50页/共50页