数据结构图资料学习教案.pptx

《数据结构图资料学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构图资料学习教案.pptx（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构(sh j ji u)图资料图资料第一页，共50页。2 27.1 图的基本概念图的基本概念7.1.1图的定义图的定义图中的数据元素称为顶点。在顶点集合图中的数据元素称为顶点。在顶点集合V中，中，第第i个顶点记作个顶点记作vi图中两个顶点图中两个顶点vi和和vj之间有关联关系，称作顶之间有关联关系，称作顶点点vi和和vj之间有一条边。在边集合之间有一条边。在边集合E中，第中，第k条边记作条边记作ek=。图是由顶点的非空有限集合与顶点间关系集图是由顶点的非空有限集合与顶点间关系集合构成的数据结构。记作合构成的数据结构。记作G=(V,E)。其中，。其中，V为顶点集合，为顶点集合，E为

2、顶点间关系为顶点间关系边的集边的集合。合。无向图：由没有方向的边构成的图称为无向无向图：由没有方向的边构成的图称为无向图。图。无向图中的边由顶点的无序无向图中的边由顶点的无序(w x)偶对组偶对组成，因此，在无向图中，顶点偶对成，因此，在无向图中，顶点偶对与顶点偶对与顶点偶对表示同一条边，记作表示同一条边，记作(vi,vj)。第1页/共50页第二页，共50页。3 37.1.1图的定义(dngy)有向图：由有方向的边构成的图称为有向图。有向图：由有方向的边构成的图称为有向图。弧：有向图中的边由顶点的有序偶对组成。弧：有向图中的边由顶点的有序偶对组成。顶点偶对顶点偶对表示从顶点表示从顶点vi指向指

3、向(zh xin)顶点顶点vj的一条有向边，也称为弧。顶的一条有向边，也称为弧。顶点点vi是有向边的始点，也称为弧尾。顶点是有向边的始点，也称为弧尾。顶点vj是有向边的终点，也称为弧头。是有向边的终点，也称为弧头。第2页/共50页第三页，共50页。4 47.1.1图的定义(dngy)完全图：含有完全图：含有n个顶点和条边的无向图称为个顶点和条边的无向图称为完全图。在完全图中，任意完全图。在完全图中，任意(rny)两个顶两个顶点之间均有边相连点之间均有边相连推论推论1：具有：具有n个顶点的无向图最多有条边。个顶点的无向图最多有条边。有向完全图：含有有向完全图：含有n个顶点和个顶点和n(n-1)条

4、弧的条弧的有向图称为有向完全图。在有向完全图中，有向图称为有向完全图。在有向完全图中，任意任意(rny)两个顶点之间均有两条方向相两个顶点之间均有两条方向相反的弧。反的弧。推论推论2：具有：具有n个顶点的有向图最多有个顶点的有向图最多有n(n-1)条弧。条弧。第3页/共50页第四页，共50页。5 57.1.17.1.1图的定义图的定义(dngy)(dngy)邻接点：在无向图中，若存在一条边邻接点：在无向图中，若存在一条边邻接点：在无向图中，若存在一条边邻接点：在无向图中，若存在一条边(vi,vj)(vi,vj)，则称，则称，则称，则称vivi和和和和vjvj互为邻接点。称边互为邻接点。称边互为

5、邻接点。称边互为邻接点。称边(vi,vj)(vi,vj)依依依依附于顶点附于顶点附于顶点附于顶点vivi和和和和vjvj或称边或称边或称边或称边(vi,vj)(vi,vj)与顶点与顶点与顶点与顶点vivi和和和和vjvj相关联。相关联。相关联。相关联。顶点的度：在无向图中，与顶点顶点的度：在无向图中，与顶点顶点的度：在无向图中，与顶点顶点的度：在无向图中，与顶点v v相关联的边数称为顶点相关联的边数称为顶点相关联的边数称为顶点相关联的边数称为顶点v v的度，记作的度，记作的度，记作的度，记作TD(v)TD(v)。在有向图中，顶点的度又分为顶点的入度和顶点的出度。顶点的入度是指以顶点在有向图中，

6、顶点的度又分为顶点的入度和顶点的出度。顶点的入度是指以顶点在有向图中，顶点的度又分为顶点的入度和顶点的出度。顶点的入度是指以顶点在有向图中，顶点的度又分为顶点的入度和顶点的出度。顶点的入度是指以顶点v v为弧为弧为弧为弧头的弧的数目头的弧的数目头的弧的数目头的弧的数目(shm)(shm)，记作，记作，记作，记作ID(v)ID(v)；顶点的出度是指以顶点；顶点的出度是指以顶点；顶点的出度是指以顶点；顶点的出度是指以顶点v v为弧尾的弧的数目为弧尾的弧的数目为弧尾的弧的数目为弧尾的弧的数目(shm)(shm)，记作，记作，记作，记作OD(v)OD(v)。顶点。顶点。顶点。顶点v v的度等于顶点的度

7、等于顶点的度等于顶点的度等于顶点v v的入度和出度之和，即的入度和出度之和，即的入度和出度之和，即的入度和出度之和，即TD(v)=ID(v)+OD(v)TD(v)=ID(v)+OD(v)。推论推论推论推论3 3：对于无向图，其总度数是总边数的两倍。：对于无向图，其总度数是总边数的两倍。：对于无向图，其总度数是总边数的两倍。：对于无向图，其总度数是总边数的两倍。推论推论推论推论4 4：对于有向图，其总入度、总出度和总边数相等。：对于有向图，其总入度、总出度和总边数相等。：对于有向图，其总入度、总出度和总边数相等。：对于有向图，其总入度、总出度和总边数相等。第4页/共50页第五页，共50页。6 6

8、7.1.1图的定义(dngy)路径路径路径路径(ljng)(ljng)：在图：在图：在图：在图GG中，从顶点中，从顶点中，从顶点中，从顶点vivi出发，经过一系列的边或弧能够到达顶点出发，经过一系列的边或弧能够到达顶点出发，经过一系列的边或弧能够到达顶点出发，经过一系列的边或弧能够到达顶点vjvj，则称顶点，则称顶点，则称顶点，则称顶点vivi到顶点到顶点到顶点到顶点vjvj的顶点序列为从顶点的顶点序列为从顶点的顶点序列为从顶点的顶点序列为从顶点vivi到顶点到顶点到顶点到顶点vjvj的路径的路径的路径的路径(ljng)(ljng)。该。该。该。该路径路径路径路径(ljng)(ljng)上所包

9、含的边的数目称为路径上所包含的边的数目称为路径上所包含的边的数目称为路径上所包含的边的数目称为路径(ljng)(ljng)长度长度长度长度简单路径简单路径简单路径简单路径(ljng)(ljng)：若路径：若路径：若路径：若路径(ljng)(ljng)上各顶点互不重复，则称这样的路径上各顶点互不重复，则称这样的路径上各顶点互不重复，则称这样的路径上各顶点互不重复，则称这样的路径(ljng)(ljng)为简单路径为简单路径为简单路径为简单路径(ljng)(ljng)。环或回路：若路径环或回路：若路径环或回路：若路径环或回路：若路径(ljng)(ljng)上第一个顶点和最后一个顶点相同，则称这样的上

10、第一个顶点和最后一个顶点相同，则称这样的上第一个顶点和最后一个顶点相同，则称这样的上第一个顶点和最后一个顶点相同，则称这样的路径路径路径路径(ljng)(ljng)为环或回路。为环或回路。为环或回路。为环或回路。子图：对于图子图：对于图子图：对于图子图：对于图G=V,EG=V,E和图和图和图和图G=V,EG=V,E，若存在，若存在，若存在，若存在V VV V且且且且E EE E，则称图，则称图，则称图，则称图GG是是是是图图图图GG的子图。的子图。的子图。的子图。第5页/共50页第六页，共50页。7 77.1.1图的定义(dngy)连通图：在无向图中，若从顶点连通图：在无向图中，若从顶点连通图

11、：在无向图中，若从顶点连通图：在无向图中，若从顶点vivi到顶点到顶点到顶点到顶点vjvj有路径存在，则称有路径存在，则称有路径存在，则称有路径存在，则称vivi和和和和vjvj是连通的。如果是连通的。如果是连通的。如果是连通的。如果(rgu)(rgu)无向图中任意两个顶点都是连通的，则称该无向图为连通图。否则，就是非连通图。无向图无向图中任意两个顶点都是连通的，则称该无向图为连通图。否则，就是非连通图。无向图无向图中任意两个顶点都是连通的，则称该无向图为连通图。否则，就是非连通图。无向图无向图中任意两个顶点都是连通的，则称该无向图为连通图。否则，就是非连通图。无向图中的极大连通子图称为该图的

12、连通分量。中的极大连通子图称为该图的连通分量。中的极大连通子图称为该图的连通分量。中的极大连通子图称为该图的连通分量。推论推论推论推论5 5：连通图的连通分量就是它本身。：连通图的连通分量就是它本身。：连通图的连通分量就是它本身。：连通图的连通分量就是它本身。强连通图：在有向图中，若一对顶点强连通图：在有向图中，若一对顶点强连通图：在有向图中，若一对顶点强连通图：在有向图中，若一对顶点vivi和和和和vjvj（vivjvivj）存在从）存在从）存在从）存在从vivi到到到到vjvj和从和从和从和从vjvj到到到到vivi的有向路径，的有向路径，的有向路径，的有向路径，则称则称则称则称vivi和

13、和和和vjvj是连通的。若有向图中任意两个顶点是连通的。若有向图中任意两个顶点是连通的。若有向图中任意两个顶点是连通的。若有向图中任意两个顶点vivi和和和和vjvj（vivjvivj）之间都是连通的，则称该有）之间都是连通的，则称该有）之间都是连通的，则称该有）之间都是连通的，则称该有向图为强连通图。有向图中的极大强连通子图称为强连通分量。向图为强连通图。有向图中的极大强连通子图称为强连通分量。向图为强连通图。有向图中的极大强连通子图称为强连通分量。向图为强连通图。有向图中的极大强连通子图称为强连通分量。第6页/共50页第七页，共50页。8 87.1.1图的定义(dngy)权：图中边或弧上附

14、带的数据称为权：图中边或弧上附带的数据称为权：图中边或弧上附带的数据称为权：图中边或弧上附带的数据称为(chn wi)(chn wi)权。权。权。权。网：带权的图称为网：带权的图称为网：带权的图称为网：带权的图称为(chn wi)(chn wi)网。网。网。网。生成树：包含连通图全部顶点的极小连通子图称作该图的生成树。即以最少的边连接生成树：包含连通图全部顶点的极小连通子图称作该图的生成树。即以最少的边连接生成树：包含连通图全部顶点的极小连通子图称作该图的生成树。即以最少的边连接生成树：包含连通图全部顶点的极小连通子图称作该图的生成树。即以最少的边连接连通图中所有顶点。连通图中所有顶点。连通图

15、中所有顶点。连通图中所有顶点。推论推论推论推论6 6：有：有：有：有n n个顶点的连通图，它的生成树一定包含个顶点的连通图，它的生成树一定包含个顶点的连通图，它的生成树一定包含个顶点的连通图，它的生成树一定包含n n个顶点和个顶点和个顶点和个顶点和n-1n-1条边。若加上一条边条边。若加上一条边条边。若加上一条边条边。若加上一条边则构成环，若减去一条边则是非连通图。则构成环，若减去一条边则是非连通图。则构成环，若减去一条边则是非连通图。则构成环，若减去一条边则是非连通图。第7页/共50页第八页，共50页。9 97.1.2 图的抽象数据类型 ADT Graph数据元素集合：具有相同性质的称为顶点

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

17、FSTraverse)：对图进行深度优先遍历广度优先遍历(BFSTraverse)：对图进行广度优先遍历第8页/共50页第九页，共50页。10107.2 图的存储(cn ch)结构 7.2.1 邻接矩阵邻接矩阵 邻接矩阵是表示邻接矩阵是表示(biosh)顶点之间相邻关系顶点之间相邻关系的矩阵。的矩阵。设设G=(V,E)是一个具有是一个具有n个顶点的图。它的顶个顶点的图。它的顶点集合点集合V=v0,v1,vn-1，则顶点间的关，则顶点间的关系系E可用如下形式的矩阵可用如下形式的矩阵A描述。描述。对于对于A中的每一个元素中的每一个元素aij满足：满足：第9页/共50页第十页，共50页。11117.

18、2.1 邻接矩阵【例7-2】对于图7-2（a）所示的无向图，请给出它的邻接矩阵，并根据邻接矩阵计算(j sun)顶点v2的度。第10页/共50页第十一页，共50页。12127.2.1 邻接矩阵 对于(duy)带权图（网），邻接矩阵A中的元素定义为：【例7-4】对于(duy)图7-5（b）所示的网，请给出它的邻接矩阵。第11页/共50页第十二页，共50页。13137.2.1 邻接矩阵 用用C语言描述的邻接矩阵：语言描述的邻接矩阵：#define MAXVEX 50/*最大顶点最大顶点(dngdin)个数个数*/typedef int weight;/*权值权值*/typedef structwe

19、ight arcsMAXVEXMAXVEX;/*邻接邻接矩阵矩阵*/DataType dataMAXVEX;/*顶点顶点(dngdin)信息信息*int vexs;/*顶点顶点(dngdin)数数*/MGraph,*AdjMetrix;第12页/共50页第十三页，共50页。14147.2.1 邻接矩阵 2.邻接矩阵的操作邻接矩阵的操作(cozu)（1）创建邻接矩阵）创建邻接矩阵 void CreateGraph(AdjMetrix g,int mMAXVEX,DataType d,int n)int i,j;g-vexs=n;for(i=0;idatai=di;for(j=0;jarcsij=

20、mij;第13页/共50页第十四页，共50页。15157.2.1 7.2.1 邻接矩阵（3）取第一个邻接）取第一个邻接(ln ji)点点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页第十五页，共50页。16167.2.1 邻接矩阵（4）取下一个）取下一个(y)邻接点邻接点 int GetNext(AdjMetrix g,int k,int t)int i;if(k

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

22、(AdjMetrix g,int u,int v)if(ug-vexs|vg-vexs)printf(参数参数(cnsh)u或或v超出范围！超出范围！n);return;g-arcsuv=0;第16页/共50页第十七页，共50页。18187.2.2 邻接(ln ji)表 邻接表是图的链式存储结构。邻接表由边表和顶点表组成邻接表是图的链式存储结构。邻接表由边表和顶点表组成邻接表是图的链式存储结构。邻接表由边表和顶点表组成邻接表是图的链式存储结构。邻接表由边表和顶点表组成边表：对图中的每个顶点建立的单链表，单链表中存放与同一个顶点相邻接的邻边表：对图中的每个顶点建立的单链表，单链表中存放与同一个顶

23、点相邻接的邻边表：对图中的每个顶点建立的单链表，单链表中存放与同一个顶点相邻接的邻边表：对图中的每个顶点建立的单链表，单链表中存放与同一个顶点相邻接的邻接点，相当于邻接矩阵中的一行接点，相当于邻接矩阵中的一行接点，相当于邻接矩阵中的一行接点，相当于邻接矩阵中的一行顶点表：存放图中每个顶点的信息以及指向该顶点边表的头指针顶点表：存放图中每个顶点的信息以及指向该顶点边表的头指针顶点表：存放图中每个顶点的信息以及指向该顶点边表的头指针顶点表：存放图中每个顶点的信息以及指向该顶点边表的头指针(zhzhn)(zhzhn)。顶点。顶点。顶点。顶点表通常采用顺序存储结构。表通常采用顺序存储结构。表通常采用顺

24、序存储结构。表通常采用顺序存储结构。边表的结点结构：边表的结点结构：边表的结点结构：边表的结点结构：adjvexadjvex为邻接点在顶点表中的序号，为邻接点在顶点表中的序号，为邻接点在顶点表中的序号，为邻接点在顶点表中的序号，nextnext指向下一个邻接点的指针指向下一个邻接点的指针指向下一个邻接点的指针指向下一个邻接点的指针(zhzhn)(zhzhn)。顶点表的结点结构：顶点表的结点结构：顶点表的结点结构：顶点表的结点结构：datadata存放顶点信息，存放顶点信息，存放顶点信息，存放顶点信息，headhead为边表头指针为边表头指针为边表头指针为边表头指针(zhzhn)(zhzhn)逆

25、邻接表：结构与邻接表完全相同，只是边表中每个结点存放的是每条弧的弧尾逆邻接表：结构与邻接表完全相同，只是边表中每个结点存放的是每条弧的弧尾逆邻接表：结构与邻接表完全相同，只是边表中每个结点存放的是每条弧的弧尾逆邻接表：结构与邻接表完全相同，只是边表中每个结点存放的是每条弧的弧尾顶点。顶点。顶点。顶点。第17页/共50页第十八页，共50页。19197.2.2 邻接(ln ji)表 C C语言描述的邻接表：语言描述的邻接表：语言描述的邻接表：语言描述的邻接表：#define MAXVEX 50#define MAXVEX 50typedef struct arc/*typedef struct a

26、rc/*边表结点类型边表结点类型边表结点类型边表结点类型(lixng)*(lixng)*int adjvex;/*int adjvex;/*顶点序号顶点序号顶点序号顶点序号*struct arc*next;/*struct arc*next;/*指向下一个邻接点指向下一个邻接点指向下一个邻接点指向下一个邻接点*/*/ArcNode,*PArcNode;ArcNode,*PArcNode;typedef struct/*typedef struct/*顶点表结点类型顶点表结点类型顶点表结点类型顶点表结点类型(lixng)*(lixng)*DataType data;/*DataType data

27、;/*顶点信息顶点信息顶点信息顶点信息*ArcNode*head;/*ArcNode*head;/*边表头指针边表头指针边表头指针边表头指针*/*/VexNode;VexNode;typedef struct/*typedef struct/*邻接表类型邻接表类型邻接表类型邻接表类型(lixng)*(lixng)*VexNode listsMAXVEX;/*VexNode listsMAXVEX;/*顶点表顶点表顶点表顶点表*int edges,vexs;/*int edges,vexs;/*边数，顶点数边数，顶点数边数，顶点数边数，顶点数*/*/VGraph,*AdjList;VGraph,

28、*AdjList;第18页/共50页第十九页，共50页。20207.2.2 7.2.2 邻接邻接(ln ji)(ln ji)表表 【例7-6】为图7-2（b）所示的图G1建立(jinl)邻接表和逆邻接表。第19页/共50页第二十页，共50页。21217.2.2 7.2.2 邻接邻接(ln ji)(ln ji)表表 2.邻接表的操作邻接表的操作（1）创建邻接表）创建邻接表 void CreateGraph(AdjList*g,int mMAXVEX,int n)/*n为顶点总数为顶点总数*/int i,j;PArcNode p;*g=(AdjList)malloc(sizeof(VGraph);

29、/*初初始化邻接表始化邻接表*/(*g)-edges=0;(*g)-vexs=n;for(i=0;ilistsi.head=NULL;/*边表头边表头指针初始化指针初始化*/for(j=n-1;j=0;j-)if(mij!=0)/*矩阵元素不为矩阵元素不为0，则，则在边表中生成一个结点在边表中生成一个结点(ji din)*/p=(PArcNode)malloc(sizeof(ArcNode);p-adjvex=j;p-next=(*g)-listsi.head;/*从链从链表头部插入新结点表头部插入新结点(ji din)*/(*g)-listsi.head=p;(*g)-edges+;第20页

30、/共50页第二十一页，共50页。22227.2.2 邻接(ln ji)表（3）寻找）寻找(xnzho)第一个邻接点第一个邻接点 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页第二十二页，共50页。23237.2.2 邻接(ln ji)表（4）寻找下一个邻接点）寻找下一个邻接点 int GetNext(AdjList g,int k,int u)PArc

31、Node p;if(kg-vexs|ug-vexs)printf(参数参数(cnsh)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页第二十三页，共50页。24247.3 7.3 图的遍历图的遍历(bin l)(bin l)7.3.1 深度深度(shnd)优先搜索优先搜索1.连通图

32、的深度连通图的深度(shnd)优先搜索遍历优先搜索遍历（1）遍历方法）遍历方法 从图中指定的顶点从图中指定的顶点v出发，先访问出发，先访问v，然后，然后依次从依次从v的未被访问的邻接点出发深度的未被访问的邻接点出发深度(shnd)优先遍历图，直至图中所有和优先遍历图，直至图中所有和v有有路径相通的顶点都被访问到为止。路径相通的顶点都被访问到为止。【例【例7-10】从右图所示的无向图】从右图所示的无向图的顶点的顶点A出发，深度出发，深度(shnd)优先搜索遍优先搜索遍历图，并写出遍历序列。历图，并写出遍历序列。遍历序列：遍历序列：ABCDEFGH。第23页/共50页第二十四页，共50页。2525

33、7.3.1 7.3.1 深度优先深度优先(yuxin)(yuxin)搜索搜索 （2）具体实现）具体实现 以邻接矩阵作为存储以邻接矩阵作为存储(cn ch)结构。建立结构。建立一个标识数组一个标识数组visited，用于标识顶点是否，用于标识顶点是否被访问过。被访问过。void DFSTraverse(AdjMetrix g)int i,visitedMAXVEX;for(i=0;ivexs;i+)/*初始化初始化visited数组数组*/visitedi=0;for(i=0;ivexs;i+)if(visitedi=0)DFS(g,i,visited);第24页/共50页第二十五页，共50页。

34、26267.3.2 广度广度(gungd)优先搜索优先搜索1.连通图的广度优先搜索遍历连通图的广度优先搜索遍历（1）遍历方法）遍历方法 从图中指定的顶点从图中指定的顶点v出发，先访问出发，先访问v，再依，再依次访问次访问v的未被访问的所有邻接点的未被访问的所有邻接点wi，然后，然后分别从这些邻接点分别从这些邻接点wi出发依次访问它们出发依次访问它们(t men)的未被访问的所有邻接点的未被访问的所有邻接点tj。依此类推。依此类推，直至图中所有顶点均被访问过为止，直至图中所有顶点均被访问过为止【例【例7-11】从右图所示的无向图】从右图所示的无向图的顶点的顶点A出发，广度优先搜索遍出发，广度优先

35、搜索遍历图，并写出遍历序列。历图，并写出遍历序列。遍历序列：遍历序列：ABHCGDFE。第25页/共50页第二十六页，共50页。27277.3.2 广度优先广度优先(yuxin)搜索搜索（2）具体实现）具体实现以邻接表作为存储结构。以邻接表作为存储结构。建立一个标识数组建立一个标识数组visited，用于标识顶点，用于标识顶点(dngdin)是否被访问过。是否被访问过。设置一个队列设置一个队列queue，用于保存访问邻接点，用于保存访问邻接点的次序。的次序。void BFS(AdjList g,int v,int visited)int u,queueMAXVEX;/*循环队列循环队列*/in

36、t front=0,rear=0;/*队头、队尾指针，队头、队尾指针，int w;/*v的邻接点的邻接点*/printf(%d,g-listsv.data);/*访问顶点访问顶点(dngdin)v*/visitedv=1;queuerear=v;/*v已被访已被访问过问过,且入队且入队*/第26页/共50页第二十七页，共50页。28287.3.2 7.3.2 广度优先广度优先广度优先广度优先(yuxin)(yuxin)搜索搜索搜索搜索rear=(rear+1)%MAXVEX;while(frontlistsw.data);visitedw=1;queuerear=w;rear=(rear+1)

37、%MAXVEX;w=GetNext(g,u,w);/*取下一个邻接点*/第27页/共50页第二十八页，共50页。29297.3.2 7.3.2 广度优先广度优先广度优先广度优先(yuxin)(yuxin)搜索搜索搜索搜索2.非连通图的广度优先搜索非连通图的广度优先搜索(su su)遍历遍历 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页第二十九页，共50页。30307.3

38、.2 7.3.2 广度广度广度广度(gungd)(gungd)优先搜索优先搜索优先搜索优先搜索【例【例7-127-12】对于下图所示的无向图，求：】对于下图所示的无向图，求：（1 1）邻接表。）邻接表。（2 2）按照邻接表，给出从顶点）按照邻接表，给出从顶点(dngdin)A(dngdin)A出发深度优先搜索遍历序列出发深度优先搜索遍历序列（3 3）按照邻接表，给出从顶点）按照邻接表，给出从顶点(dngdin)C(dngdin)C出发广度优先搜索遍历序列出发广度优先搜索遍历序列 深度优先搜索遍历序列：深度优先搜索遍历序列：ABCDEABCDE。广度优先搜索遍历序列：广度优先搜索遍历序列：CAB

39、DECABDE。第29页/共50页第三十页，共50页。31317.4 最小生成最小生成(shn chn)树树 带权图的生成树的边也带权。在这些带权的生成树中必有一颗边的权值之和最小的生成树，这颗生成树就是最小（代价）生成树。7.4.1 普里姆算法 算法的基本思想：设G=(V,E)是连通网，V是连通网中顶点集合，E是连通网中边的集合。T=(U,D)是正在构造的最小生成树，U是最小生成树的顶点的集合，D是最小生成树的边的集合。V-U表示(biosh)属于集合V，但不属于集合U的顶点集合。第30页/共50页第三十一页，共50页。32327.4.1 7.4.1 普里姆算法普里姆算法(sun f)(su

40、n f)（1 1）若从顶点）若从顶点v0v0开始构造最小生成树，则从集合开始构造最小生成树，则从集合V V中取出顶点中取出顶点v0v0放入集合放入集合U U中。中。此时，集合此时，集合U=v0U=v0，集合，集合V-U=V-U=除除v0v0以外的所有顶点以外的所有顶点，集合，集合D D为空。为空。（2 2）若在集合）若在集合U U中的顶点中的顶点vi vi和集合和集合V-UV-U中的顶点中的顶点vj vj之间存在边，则寻找这些边中之间存在边，则寻找这些边中权值最小的边，但不构成回路。将顶点权值最小的边，但不构成回路。将顶点vj vj加入集合加入集合U U中，将边中，将边(vi,vj)(vi,v

41、j)加入集加入集合合D D中。中。（3 3）重复）重复(chngf)(chngf)步骤（步骤（2 2），直至），直至U U与与V V相等为止。此时，相等为止。此时，D D中必有中必有n-1n-1条边，条边，则则T=(U,D)T=(U,D)即是最小生成树。即是最小生成树。【例【例7-157-15】已知一个如图所示的带权图，】已知一个如图所示的带权图，请给出根据普里姆算法构造的一颗最小请给出根据普里姆算法构造的一颗最小生成树（假设从顶点生成树（假设从顶点1 1开始构造）。开始构造）。第31页/共50页第三十二页，共50页。33337.4.1 普里姆算法(sun f)第32页/共50页第三十三页，共

42、50页。34347.4.1 7.4.1 普里姆算法普里姆算法(sun f)(sun f)2.具体实现具体实现(shxin)设置两个数组设置两个数组lowcost和和uset。lowcostv存放集合存放集合U中的顶点中的顶点u和集合和集合V-U中的顶点中的顶点v构成的权值最小的边构成的权值最小的边(v,u)的权值；的权值；uset数组存放数组存放U集合中的顶点和集合中的顶点和V-U集合中的集合中的顶点，当顶点，当usetu=0时，表示顶点时，表示顶点u在集合在集合U中，当中，当usetu=1时，表示顶点时，表示顶点u在集合在集合V-U中。中。每次从每次从lowcost数组中寻找权值最小的边。若

43、数组中寻找权值最小的边。若找到，则把顶点找到，则把顶点v加入到集合加入到集合U中，即置中，即置usetv为为0。当顶点当顶点v从集合从集合V-U加入到集合加入到集合U后，更新后，更新lowcostv的权值。若存在一条边的权值。若存在一条边(v,u)，它，它的权值比原先的权值比原先lowcostv的权值小，则用新的权值小，则用新的权值更新的权值更新lowcostv。第33页/共50页第三十四页，共50页。35357.4.1 7.4.1 普里姆算法普里姆算法(sun f)(sun f)void Prim(AdjMetrix g,int v)weight lowcostMAXVEX;int uset

44、MAXVEX;int i,j,MinEdge,MinWeight,k;for(i=0;ivexs;i+)/*初始化lowcost和uset数组*/lowcosti=g-arcsvi;useti=1;usetv=0;/*把起始(q sh)点放到最小生成树中*/printf(起始(q sh)点%cn,g-datav);for(i=1;ivexs;i+)第34页/共50页第三十五页，共50页。36367.4.1 7.4.1 普里姆算法普里姆算法(sun f)(sun f)MinWeight=MAXWEIGHT;MinWeight=MAXWEIGHT;/*/*初始化最小权值初始化最小权值*/*/for

45、(j=0;jvexs;j+)for(j=0;jvexs;j+)if(usetj&lowcostjMinWeight)/*if(usetj&lowcostjMinWeight)/*寻找权值最小的边寻找权值最小的边*/*/MinWeight=lowcostj;MinWeight=lowcostj;MinEdge=j;/*MinEdge=j;/*权值最小边的弧尾顶点权值最小边的弧尾顶点*/*/for(j=0;jvexs;j+)for(j=0;jvexs;j+)/*/*寻找权值最小边的弧头顶点寻找权值最小边的弧头顶点*/*/if(g-arcsjMinEdge=MinWeight)k=j;if(g-ar

46、csjMinEdge=MinWeight)k=j;printf(printf(边边(%c,%c)t(%c,%c)t权值权值%dn%dn,g-datak,g-dataMinEdge,MinWeight);,g-datak,g-dataMinEdge,MinWeight);usetMinEdge=0;v=MinEdge;/*usetMinEdge=0;v=MinEdge;/*权值最小的边加入最小生成权值最小的边加入最小生成(shn chn)(shn chn)树树*/*/for(j=0;jvexs;j+)for(j=0;jvexs;j+)/*/*更新最小权值更新最小权值*/*/if(usetj&g-

47、arcsvjarcsvjarcsvj;lowcostj=g-arcsvj;第35页/共50页第三十六页，共50页。37377.4.2 克鲁斯卡尔算法(sun f)算法思想：算法思想：设设G=(V,E)是一个具有是一个具有n个顶点的带权连通图，个顶点的带权连通图，T=(U,D)是是G的最小生成树。的最小生成树。初始时，初始时，U中包含中包含G的全部的全部n个顶点，个顶点，D为空。为空。从从E中选择一条以前中选择一条以前(yqin)未选择过的、边未选择过的、边上的权值最小的边加入上的权值最小的边加入D中。中。若加入后，并未使若加入后，并未使T形成回路，则继续选择下形成回路，则继续选择下一条边；一条

48、边；若加入后，使若加入后，使T形成回路，则放弃选择的边。形成回路，则放弃选择的边。重复以上过程，直至重复以上过程，直至D中包含了中包含了n-1条边为止。条边为止。此时，此时，T即为即为G的最小生成树。的最小生成树。第36页/共50页第三十七页，共50页。38387.4.2 克鲁斯卡尔算法(sun f)【例7-17】已知一个带权图如图7-14（a）所示，请给出根据克鲁斯卡尔算法构造(guzo)的一颗最小生成树 第37页/共50页第三十八页，共50页。39397.5 最短路径(ljng)7.5.1 从某个顶点到其余顶点的最短路径从某个顶点到其余顶点的最短路径 带权图的路径长度是指路径所经过的所有带

49、权图的路径长度是指路径所经过的所有边上边上(bin shn)的权值之和。的权值之和。图的顶点间可能存在多条路径，其中路径图的顶点间可能存在多条路径，其中路径长度最短的路径称为最短路径。长度最短的路径称为最短路径。最短路径分为两种情况：最短路径分为两种情况：从图中某个顶点到其余顶点间的最短路径从图中某个顶点到其余顶点间的最短路径 图中每对顶点之间的最短路径。图中每对顶点之间的最短路径。第38页/共50页第三十九页，共50页。40407.5.1 7.5.1 从某个从某个从某个从某个(mu)(mu)顶点到其余顶点的最短路径顶点到其余顶点的最短路径顶点到其余顶点的最短路径顶点到其余顶点的最短路径1.迪

50、杰斯特拉算法迪杰斯特拉算法（1）初始时，集合）初始时，集合(jh)V中仅包含源点中仅包含源点v，集合集合(jh)W中包含除源点中包含除源点v以外的所有顶点，以外的所有顶点，v到到W中各顶点的路径长度或为边的权值中各顶点的路径长度或为边的权值（有边相连），或为（有边相连），或为（没边相连）。（没边相连）。（2）按最短路径长度递增的次序，从集合）按最短路径长度递增的次序，从集合(jh)W中选出到顶点中选出到顶点v路径长度最短的顶点路径长度最短的顶点w，把它加入到集合，把它加入到集合(jh)V中。中。（3）加入）加入w后，为了寻找下一个最短路径，后，为了寻找下一个最短路径，必须修改从必须修改从v到集