数据结构课件图培训课件.ppt

1、数据结构课件图 哥尼斯堡七桥问题哥尼斯堡七桥问题 德国古城德国古城哥尼斯堡哥尼斯堡普雷格尔河普雷格尔河七七 桥问题：从任一桥头出发，依次走过每桥问题：从任一桥头出发，依次走过每座座 桥，每座桥只走一次，最后回到出发点。桥，每座桥只走一次，最后回到出发点。一笔画问一笔画问题题 其中：其中：V V 是是G G 的顶点集合，是有穷非空集；的顶点集合，是有穷非空集；E E 是是G G 的边集合，是有穷集。的边集合，是有穷集。问：当问：当E(G)E(G)为空时，图为空时，图G G存在否？存在否？答：还存在！但此时图答：还存在！但此时图G G只有顶点而没有边。只有顶点而没有边。有向图：有向图：无向图：无向

2、图：完全图：完全图：图图G G中的每条边都是有方向的；中的每条边都是有方向的；图图G G中的每条边都是无方向的；中的每条边都是无方向的；图图G G任意两个顶点都有一条边相连接；任意两个顶点都有一条边相连接；v若若 n 个顶点的无向图有个顶点的无向图有 n(n-1)/2 条边条边,称为无向完全图称为无向完全图v若若 n 个顶点的有向图有个顶点的有向图有n(n-1)条边条边,称为有向完全图称为有向完全图V=vertex E=edge图：记为图：记为 G(V,E)v1v2v3v5v4v4v1v2v3v4有向边有向边(u,v)称为称为弧，边的始点弧，边的始点u 叫叫弧尾，终点弧尾，终点v 叫弧叫弧头。

3、头。例：判断下列例：判断下列4种图形各属什么类型？种图形各属什么类型？无向无向无向图无向图(树树)有向图有向图有向有向G1G1的顶点集合为的顶点集合为V(G1)=0,1,2,3V(G1)=0,1,2,3边集合为边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)完全图完全图完全图完全图证明：证明：证明：若是完全有向图，则证明：若是完全有向图，则n个顶点中个顶点中的每个顶点都有一条弧指向其它的每个顶点都有一条弧指向其它n-1个个顶点顶点,因此总边数因此总边数=n(n-1)证明：

4、从证明：从可以直接推论出无向完全图的可以直接推论出无向完全图的边数边数因为无方向，两弧合并为一边，因为无方向，两弧合并为一边，所以边数减半，总边数为所以边数减半，总边数为n(n-1)/2。12341234稀疏图：稀疏图：稠密图：稠密图：设有两个图设有两个图 G(V,E)和和 G(V,E)。若。若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。子子 图：图：边较少的图。通常边数远少于边较少的图。通常边数远少于边很多的图。边很多的图。无向图中，边数接近无向图中，边数接近有向图中，边数接近有向图中，边数接近带权图：带权图：即边上带权的图。其中权是指每条边即边上带权的图。其中权

5、是指每条边可以标上具有某种含义的数值（即与可以标上具有某种含义的数值（即与边相关的数）。边相关的数）。连通图：连通图：在无向图中在无向图中,若从顶点若从顶点v v1 1到顶点到顶点v v2 2有路径有路径,则称顶点则称顶点v v1 1与与v v2 2是连通的。是连通的。如果图中任意一对顶点都是连通的如果图中任意一对顶点都是连通的,则称此图是连通图。则称此图是连通图。非连通图的极大连通子图叫做连通非连通图的极大连通子图叫做连通分量。分量。带权图带权图在有向图中在有向图中,若对于每一对顶点若对于每一对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径,则称此图是

6、强连通图。则称此图是强连通图。强连通图：强连通图：网网 ：DEABCFJLMGHIK非强连通图的极大强连通子图叫做强连通分量。非强连通图的极大强连通子图叫做强连通分量。生成树：生成树：有两类图形不在有两类图形不在本章讨论之列：本章讨论之列：v1v2v3v4v如果在生成树上添加如果在生成树上添加1条边，必定构成一个环。条边，必定构成一个环。v若图中有若图中有n个顶点，却少于个顶点，却少于n-1条边，必为非连通图。条边，必为非连通图。生成生成森林：森林：邻接点：邻接点：有向边有向边(u,v)称为弧，边的始点称为弧，边的始点u 叫弧尾，叫弧尾，终点终点v 叫弧头。叫弧头。顶点顶点 v 的入度是以的入

7、度是以 v 为终点的有向边的条数为终点的有向边的条数,记作记作 ID(v);顶点顶点 v 的出度是以的出度是以 v 为始点的有向边的条数为始点的有向边的条数,记作记作 OD(v)。若若(u,v)是是 E(G)中的一条边，则中的一条边，则称称 u 与与 v 互为邻接顶点。互为邻接顶点。弧头和弧头和弧尾：弧尾：入度和入度和出度：出度：问：当有向图中仅问：当有向图中仅1 1个顶点的入度为个顶点的入度为0,0,其余顶点的入度均为其余顶点的入度均为1 1，此时是何形状？此时是何形状？uv度：度：顶点顶点v 的度是与它相关联的边的条数。记作的度是与它相关联的边的条数。记作TD(v)。在有向图中在有向图中,

8、顶点的度等于该顶点的入度与出度之和。顶点的度等于该顶点的入度与出度之和。答：是树！而且是一答：是树！而且是一棵有向树！棵有向树！简单路径：简单路径：路径上各顶点路径上各顶点 v v1 1,v,v2 2,.,v,.,vm m 均不互相重复。均不互相重复。回路：回路：若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点v vm m 重合，重合，则称这样的路径为回路或环。则称这样的路径为回路或环。路径：路径：路径长路径长度：度：图的术语（续）图的术语（续）【案例】一种产品不能满足所有的需求，一种服务标准不能满足所有的顾客，这就是区隔化贴心服务的理论基础。企业在服务过程中要

9、注意因人而异的服务技巧，即了解顾客的不同需求，针对每个顾客要求和标准为其提供差异化的服务。因人而异的服务是企业吸引客户尤其是重要客户的必要策略。企业在实际的服务规划中要对此加以重视。迎宾的服务礼仪22.4 仲裁费用除仲裁机关另有裁决外，应由败诉方负担。1.7加气站员工必须持操作证，穿戴劳动保护服装上岗。坚持岗位练兵制度，积极参加各项安全生产活动，主动向领导或有关部门提出合理化建议和意见。35.4 如果确定该投标人无能力圆满履行合同，招标人将对下一个中标候选人作类似的审查。台积电的企业文化（2）由卖方委托经买方认可的法定质量检测机构进行验收，验收合格后由法定质量检测机构出具验收报告。验收费用应包

10、含在合同价中，买方不再另行支付。善用会议与激励2、对用户进行多种形式的培训第5条 考核ADT Graph 数据对象数据对象V：数据关系数据关系 R：基本操作基本操作P：ADT Graph V V是具有相同特性的数据元素的集合，称为顶点集。是具有相同特性的数据元素的集合，称为顶点集。R=VRR=VR；VR=|v,wV VR=|v,wV 且且 P(v,w),P(v,w),表示从表示从v v到到w w的弧，的弧，谓词谓词P(v,w)P(v,w)定义了弧定义了弧的意义或信息的意义或信息 CreatGraph(&G,V,VR);初始条件：初始条件：V V是图的顶点集，是图的顶点集，VRVR是图中弧的集合

11、。是图中弧的集合。操作结果：按操作结果：按V V和和VRVR的定义构造图的定义构造图G G。注意：注意：V V 的大小的大小写含义不同！写含义不同！InsertVex(&G,v);初始条件：图初始条件：图G G存在，存在，v v 和图中顶点有相同特征。和图中顶点有相同特征。操作结果：在图操作结果：在图G G中添加新顶点。中添加新顶点。（参见教材（参见教材P156-257P156-257）图的特点：图的特点：链式存储结构：链式存储结构：顺序存储结构：顺序存储结构：难！难！（多个顶点，无序可言，无法仅以顶点坐（多个顶点，无序可言，无法仅以顶点坐标表达相互关系）标表达相互关系）可用多重链表可用多重链

12、表但可但可用数组描述元素间关系。用数组描述元素间关系。非线性结构（非线性结构（m:nm:n）邻接矩阵邻接矩阵邻接表邻接表十字链表十字链表邻接多重表邻接多重表各种表示法成立的原则：各种表示法成立的原则：存入电脑后能惟一复原存入电脑后能惟一复原 ,),(,.否否则则或或者者如如果果01AEjiEjijiEdge邻接矩阵：邻接矩阵：A.Edge=（v1 v2 v3 v4 v5 ）v1v2v3v4v50 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0顶点表：顶点表：无向图的邻接矩阵如何表示？无向图的邻接矩阵如何表示？v1v2v3v5v4v4记录各个顶点信息记录各

13、个顶点信息表示各个顶点之间关系表示各个顶点之间关系0 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0例例2：有向图的邻接矩阵如何表示？：有向图的邻接矩阵如何表示？有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。顶点顶点v vi i的出度的出度=第第i i行元素之和，行元素之和，OD(v vi i)=A.Edge i j 顶点顶点v vi i的入度的入度=第第i i列元素之和。列元素之和。ID(v vi i)=A.Edge j i 顶点的度顶点的度=第

14、第i i行元素之和行元素之和+第第i i列元素之和列元素之和,即：即：TD(v vi i)=OD(vi)+ID(vi)v1v2v3v4邻接矩阵：邻接矩阵：A.Edge=(v1 v2 v3 v4)v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 在有向图的邻接矩阵中，在有向图的邻接矩阵中，第第i i行含义：以结点行含义：以结点v vi i为尾的弧为尾的弧(即出度边）；即出度边）；第第i i列含义：以结点列含义：以结点v vi i为头的弧为头的弧(即入度边）。即入度边）。顶点表：顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0

15、0 0 0 0 0 1 1 0 0 0 容易实现图的操作，如：求某顶点的度、判断顶容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。点之间是否有边（弧）、找顶点的邻接点等等。n n个顶点需要个顶点需要个单元存储边个单元存储边(弧弧););空间效率为空间效率为O(nO(n)。例例3：有权图（即网络）的邻接矩阵如何表示？有权图（即网络）的邻接矩阵如何表示？定义：定义：A.Edge i j=Wij 或（或（vi,vj）VR 无边（弧）无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：以有向网为例：邻接矩阵：邻接矩阵：N.Edge=(v1 v2 v

16、3 v4 v5 v6 )邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：顶点表：顶点表：5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 v1v2v3v4v5v6对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。注：注：用两个数组分别存储顶点表和邻接矩阵用两个数组分别存储顶点表和邻接矩阵#define INFINITY INT_MAX /最大值最大值#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数Typedef enum DG,DN,AG,AN GraphKind;/有向有向/无向图，有向无向图，有向/无向网

17、无向网图的邻接矩阵在机内如何表示？图的邻接矩阵在机内如何表示？（参见教材（参见教材P161P161）对于对于n n个顶点的图或网，空间效率个顶点的图或网，空间效率=O(n=O(n2 2)Typedef struct ArcCell /弧（边）结点的定义弧（边）结点的定义 VRType adj;/顶点间关系，无权图取顶点间关系，无权图取1 1或或0 0；有权图取权值类型；有权图取权值类型 InfoType *info;/该弧相关信息的指针该弧相关信息的指针ArcCell,AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM;Typedef struct /图的定义图的定

18、义VertexType vexs MAX_VERTEX_NUM ;/顶点表，用一维向量即可顶点表，用一维向量即可(n)(n)AdjMatrix arcs;/邻接矩阵邻接矩阵n n*n nInt Vernum,arcnum;/顶点总数顶点总数n n，弧（边）总数，弧（边）总数e eGraphKind kind;/图的种类标志图的种类标志Mgraph;Status CreateUDN(Mgraph&G)/无向网的构造，用邻接矩阵表示无向网的构造，用邻接矩阵表示scanf(&G.vexnum,&G.arcnum,&IncInfo);/输入总顶点数输入总顶点数n n、总弧数、总弧数e e和信息和信息f

19、or(i=0;iG.vexnum,;+i)scanf(&G.vexsi);/输入输入n n个顶点值，存入一维向量个顶点值，存入一维向量例：用邻接矩阵生成无向网的算法例：用邻接矩阵生成无向网的算法（参见教材（参见教材P162P162）对于对于n n个顶点个顶点e e条弧的网，条弧的网，建网时间效率建网时间效率 =O(n+n=O(n+n2 2+e+e*n)n)for(i=0;iG.vexnum;+i)/对邻接矩阵对邻接矩阵n n*n n个单元初始化，个单元初始化，adj=,info=NULLfor(j=0;jG.vexnum;+j)G.arcsij=INFINITY,NULL;for(k=0;kG

20、.arcnum;+k)/给邻接矩阵有关单元赋初值给邻接矩阵有关单元赋初值(循环次数弧数循环次数弧数e e scanf(&v1,&v2,&w);/输入弧的两顶点以及对应权值输入弧的两顶点以及对应权值 i=LocateVex(G,v1);j=LocateVex(G,v2);/找到两顶点在矩阵中的位置找到两顶点在矩阵中的位置(n(n次次)G.arcsij.adj=w;/输入对应权值输入对应权值 If(IncInfo)Input(*G.arcsij.info);/如果弧有信息则填入如果弧有信息则填入 G.arcsij=G.arcs j i；/无向网是对称矩阵无向网是对称矩阵 return OK;/Cr

21、eate/CreateUDN adjvex nextarcinfodatafirstarc邻接点域，邻接点域，表表示示v vi i 邻接点邻接点的位置的位置链域，链域，指向指向下一个边或下一个边或弧的结点弧的结点数据域，数据域，与与边有关信息边有关信息（如权值）（如权值）数据域，存数据域，存储顶点储顶点vi 信信息息链域，链域，指向指向单链表的第单链表的第一个结点一个结点例例1 1：无向图的邻接表如何表示？：无向图的邻接表如何表示？v1v2v3v5v4v4邻邻接接表表0123413341420例例2 2：有向图的邻接表如何表示？：有向图的邻接表如何表示？v1v2v3v4V4V3V2V12301

22、邻接表邻接表(出边出边)V4V3V2V13020逆邻接表逆邻接表(入边入边)请注意：邻接表不惟一！因各个边结点的链入顺序是任意的。请注意：邻接表不惟一！因各个边结点的链入顺序是任意的。v1v2v3v4v5231420v v1 1邻接点邻接点v v4 4的位置的位置此无权图未开第此无权图未开第3 3分量分量例例3 3：已知某网的邻接（出边）表，请画出该网络。：已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的存储当邻接表的存储结构形成后，图结构形成后，图便唯一确定！便唯一确定！分析分析1:对于对于n n个顶点个顶点e e条边的无向图，邻接表中除了条边的无向图，邻接表中除了n n个头

23、结点个头结点外，只有外，只有2e2e个表结点个表结点,空间效率为空间效率为O(n+2e)O(n+2e)。若是稀疏图若是稀疏图(en(en2 2)，则比邻接矩阵表示法，则比邻接矩阵表示法O(nO(n2 2)省空间。省空间。邻接表存储法的特点：邻接表存储法的特点：分析分析2:在有向图中，邻接表中除了在有向图中，邻接表中除了n n个头结点外，只有个头结点外，只有e e个表结点个表结点,空间效率为空间效率为O(n+e)O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。若是稀疏图，则比邻接矩阵表示法合适。它其实是对邻接矩阵法的一种改进它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？怎样计算无向图顶

24、点的度？邻接表的邻接表的缺点：缺点：怎样计算有向图顶点的出度？怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点的入度？怎样计算有向图顶点怎样计算有向图顶点Vi的度：的度：需遍历全表需遍历全表邻接表的邻接表的优点：优点：TD(Vi)TD(Vi)=单链表中链接的结点个数单链表中链接的结点个数OD(Vi)单链出边表中链接的结点数单链出边表中链接的结点数I D(Vi)邻接点为邻接点为ViVi的弧个数的弧个数TD(Vi)=OD(Vi)+I D(Vi)空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两判断两顶点间是否有边或弧，需搜索

25、两结点对应的单链表，没有邻接矩阵方便。结点对应的单链表，没有邻接矩阵方便。1.1.联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2.2.区别：区别：对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。与顶点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为

26、O(n+e)O(n+e)。3.3.用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-1)/2)n(n-1)/2)；而邻接表多用于稀疏图的存储（而邻接表多用于稀疏图的存储（enen2 2)【本讲小结】31.2 资格性检查是依据法律法规和招标文件的规定，对投标文件中资格证明、投标保证金等进行审查，以确定投标人是否具备投标资格。10.1 卖方应保证合同项下所供货物是全新的、未使用过的，技术水平是先进的、成熟的，并完全符合合同规定的数量、质量、工艺、设计、型式、规格和技术性能，满足合同技术规范的要求。卖方还须保证，合同项下提供的全部货物不存在设计、材料或工艺上的

27、缺陷。货物在其正确安装、正常使用和保养条件下，在其使用寿命期内应具有满意的性能。1、经济利益促动自我约束机制，充分利用经济措施去诱发管理对象利益铭感的动机，由这种动机去对行为自我约束。2.3 分析统计方法：在叙述统计方法的基础上，采用分析与解释这两种技术剖析事物的状况或决定趋势以及可能发展的情况。40.招标代理机构接受或拒绝任何投标的权力(三)热爱共青团工作，有较强的责任心和奉献精神，有愿望在团的岗位上进一步锻炼成长。14.2 在不改变合同其他条款的前提下，如果由于上述变更引起卖方履行合同义务的费用或时间增减，将以补充合同的形式对合同价或交货时间或两者进行合理的调整。卖方根据本条款进行调整的要

28、求，必须在收到买方的变更通知后十(10)天内提出。否则，买方的通知和规定是最终的。（2）投标人之间约定中标人；（1）如果单价乘数量不等于总价，应以单价为准，并修正总价；24.2 招标代理机构可以根据本须知第9条规定，通过修改招标文件适当推迟投标截止时间。在这种情况下，招标代理机构和投标人受投标截止时间约束的所有权利和义务将延长至新的截止期。a.客观性原则是统计方法的选用必须和客观实际相结合，统计资料的收集方式，统计调查和分析都必须尊重客观实际，各种数据资料要实事求是，严禁弄虚作假；图的邻接表在机内如何表示？图的邻接表在机内如何表示？（参见教材（参见教材P163P163）#define MAX_

29、VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数空间效率为空间效率为O(n+2e)O(n+2e)或或O(n+e)O(n+e)时间效率为时间效率为O(n+eO(n+e*n)n)Typedef struct VNode /顶点结构顶点结构 VertexType data;/顶点信息顶点信息 ArcNode *firstarc;/指向依附该顶点的第一条弧的指针指向依附该顶点的第一条弧的指针VNode,AdjList MAX_VERTEX_NUM;Typedef struct /图结构图结构 AdjList vertics;/应包含邻接表应包含邻接表 int vexnum,arcnum;

30、/应包含顶点总数和弧总数应包含顶点总数和弧总数 int kind;/还应说明图的种类（用标志）还应说明图的种类（用标志）ALGraph;Typedef struct ArcNode /弧结构弧结构 int adjvex;/该弧所指向的顶点位置该弧所指向的顶点位置 struct ArcNode*nextarcs;/指向下一条弧的指针指向下一条弧的指针 InfoArc *info;/该弧相关信息的指针该弧相关信息的指针 ArcNode；图的邻接表图的邻接表生成算法作生成算法作为自测题为自测题 它是有向图的另一种链式结构。它是有向图的另一种链式结构。思路：思路：将邻接矩阵用链表存储，是邻接表、逆邻接

31、表的结合。将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。1、开设弧结点，设弧结点，设5 5个域个域（每段弧是一个数据元素）（每段弧是一个数据元素）2 2、开设顶点结点，设、开设顶点结点，设3 3个域个域（每个顶点也是一个数据元素）（每个顶点也是一个数据元素）tailvexheadvexhlinktlinkinfo data :顶点信息Firstin :以顶点为弧头的第一条弧结点Firstout:以顶点为弧尾的第一条弧结点dataFirstinFirstout顶点结点顶点结点弧结点弧结点tailvex:tailvex:弧尾顶点位置 headvex:headvex:弧头顶点位置hlink:hli

32、nk:弧头相同的下一弧位置tlink:tlink:弧尾相同的下一弧位置info:info:弧信息n个顶点的集合怎样储存？个顶点的集合怎样储存？仍用顺序存储结构仍用顺序存储结构v1v2v3v42 0233031例：画出有向图的十字链表。例：画出有向图的十字链表。十字链表优点：容易操作，如求顶点的入度、出度等。十字链表优点：容易操作，如求顶点的入度、出度等。FirstoutFirstindata顶点结点顶点结点infotlinkhlinkheadvextailvex弧结点弧结点0v11v22v33v401230 102此无权图未开第此无权图未开第4 4分量分量空间复杂度和建表的时间复杂度都与邻接表

33、相同。空间复杂度和建表的时间复杂度都与邻接表相同。#define MAX_VERTEX_NUM 20十字链表存储结构描述：十字链表存储结构描述：Typedef struct ArcBox /弧结点结构，弧结点结构，5 5分量分量 int tailvex,headvex;struct ArcBox*hlink,tlink;InfoType *info;ArcBox;Typedef struct VexNode /顶点结构顶点结构,3,3分量分量 VertexType data;ArcBox *firstin,*firstout;VexNode;Typedef struct /图结构图结构,整体概

34、念整体概念 VexNode xlist MAX_VERTEX_NUM;/表头向量表头向量 int vexnum,arcnum;OLGraph;这是无向图的另一种存储结构，当对边操作时建议采用此种结构存储。这是无向图的另一种存储结构，当对边操作时建议采用此种结构存储。1、设立边结点，、设立边结点，6个域个域（每条边是一个数据元素）（每条边是一个数据元素）2、设立顶点结点，、设立顶点结点，2个域个域（每个顶点也是一个数据元素）（每个顶点也是一个数据元素）markivexilinkjvexjlinkinfo边结点边结点 data :存储顶点信息存储顶点信息Firstedge:依附顶点的第一依附顶点的

35、第一条边结点条边结点dataFirstedge顶点结点顶点结点mark：标志域：标志域ivex，jvex:边依附的两个顶点位置边依附的两个顶点位置 ilink:指向下一条依附顶点指向下一条依附顶点 i 的边位置的边位置jlink;指向下一条依附顶点指向下一条依附顶点 j 的边位置的边位置info:边信息边信息n个顶点的集合怎样储存？个顶点的集合怎样储存？仍用顺序存储结构仍用顺序存储结构121 4232 43 4 v1v2v3v5v4v4例：画出无向图的邻接多重表例：画出无向图的邻接多重表邻接多重表优点：邻接多重表优点：容易操作，如求顶点的度等。容易操作，如求顶点的度等。0v11v22v33v4

36、4v501234Firstedgedata顶点结点顶点结点markinfojlinkjvexilinkivex边结点边结点空间复杂度和建表的时间复杂度都与邻接表相同。空间复杂度和建表的时间复杂度都与邻接表相同。0103此无权此无权图未开图未开第第6 6分量分量一、深度优先搜索二、广度优先搜索 7.3 图的遍历图的遍历遍历定义：遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做它是它是图的基本运算。图的基本运算。遍历实质：遍历实质：找每个顶点的邻接点

37、的过程。找每个顶点的邻接点的过程。图的特点：图的特点：图中可能存在回路，且图的任一顶点都可能与其它图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点到了曾经访问过的顶点解决思路：解决思路：可设置一个辅助数组可设置一个辅助数组 visited n，用来标记每个被，用来标记每个被访问过的顶点。它的初始状态为访问过的顶点。它的初始状态为0 0，在图的遍历过程中，在图的遍历过程中，一旦某一个顶点一旦某一个顶点i 被访问，就立即改被访问，就立即改 visited i为为1 1，防止，防止它被

38、多次访问。它被多次访问。图常用的遍历：图常用的遍历：怎样避免重复访问？怎样避免重复访问？基本思想：基本思想：仿树的先序遍历过程。仿树的先序遍历过程。Depth_First Searchv1v2v3v8v7v6v4v5起点起点起点起点遍历步骤遍历步骤应退回到应退回到V8V8，因为，因为V2V2已有标记已有标记深度优先搜索（遍历）步骤：深度优先搜索（遍历）步骤：详细归纳：详细归纳：E在访问图中某一起始顶点在访问图中某一起始顶点 v 后，由后，由 v 出发，访问它的任一邻接出发，访问它的任一邻接顶点顶点 w1；E再从再从 w1 出发，访问与出发，访问与 w1邻接但还未被访问过的顶点邻接但还未被访问过

39、的顶点 w2；E然后再从然后再从 w2 出发，进行类似的访问，出发，进行类似的访问，E如此进行下去，直至到达所有的邻接顶点都被访问过的顶点如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。为止。E接着，退回一步，接着，退回一步，退到前一次刚访问过的顶点退到前一次刚访问过的顶点，看是否还有，看是否还有其它未被访问的邻接顶点。其它未被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；类似的访问；如果没有，就如果没有，就再退回一步再退回一步进行搜索。重复上述过程，直到连进行搜索。重复上述过程，直到连通图中

40、所有顶点都被访问过为止。通图中所有顶点都被访问过为止。简单归纳：简单归纳：访问起始点访问起始点 v;若若v的第的第1个邻接点没访问过，深度遍历此邻接点；个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找若当前邻接点已访问过，再找v的第的第2个邻接点重新遍历。个邻接点重新遍历。1 2345610 000000 0000030 0000040 0000050 0000060 00000000000123456010000100001000010101邻邻接接矩矩阵阵A辅助数组辅助数组 visited n 起点起点开辅助数组开辅助数组 visited n！例：例：1 23 4561000

41、00 00300 00400 005000060 0000请注意逐级回退是递归概念请注意逐级回退是递归概念for(j=1;jlink)while(p-link)/当存在起点的第一个邻接点时当存在起点的第一个邻接点时 p=p-link;p=p-link;v=p-data;v=p-data;if(!visitedv)DFS(List,v,p);if(!visitedv)DFS(List,v,p);/进行递归进行递归 return;return;9.4.3 成交供应商无正当理由不与采购人签订政府采购合同的；18.1 如果卖方没有按照合同规定的时间交货和提供服务，买方应在不影响合同项下的其它补救措施的

42、情况下，从合同价中扣除误期赔偿费。每延误一周（一周按七天计算，不足七天按一周计算）的赔偿费按迟交货物价或未提供服务价的千分之五（0.5%）计收，直至交货或提供服务为止。一旦误期赔偿费的最高额达到迟交货物价或未提供服务价的百分之五（5%），买方可考虑部分或全部终止合同。5.9按时完成领导安排的其它工作。3.2负责全站生产过程的技术指导，质量把关。24.投标截止时间2导购的服务礼仪、会计帐薄及辅助报表的自动生成：包括记证凭证查找、会计账册、损益表、资产负债表、会计明细科目汇总表及会计科目试算平衡表。图32 培养服务人才的步骤小型、微型企业提供中型企业制造的货物的，视同为中型企业。8、施工时应自觉接

43、受监督。3、权利链条相关制约机制，建立管理对象之间相互制约的权利链条，造成相关机构、相关员工相互的自我约束机制。市场部监察人员要根据对各中心药店检查情况，对各县区负责人有款不回现象，及时汇报给市场部及财务部，严肃处理。（）n如果用邻接矩阵来表示图，遍历图中每一个顶点如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为所需的时间为O(n2)。n如果用邻接表来表示图，虽然有如果用邻接表来表示图，虽然有 2e 个表结点，个表结点，但只需扫描但只需扫描 e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n

44、个头结点的时间，因此遍历图的时间复杂度为个头结点的时间，因此遍历图的时间复杂度为O(n+e)。结结 论：论：稠密图适于在邻接矩阵上进行深度遍历；稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。稀疏图适于在邻接表上进行深度遍历。基本思想：基本思想：仿树的层次遍历过程。仿树的层次遍历过程。Breadth_First Searchv1v2v3v8v7v6v4v5起点起点遍历步骤遍历步骤起点起点广度优先搜索（遍历）步骤：广度优先搜索（遍历）步骤：简单归纳：简单归纳：在访问了起始点在访问了起始点v之后，依次访问之后，依次访问 v的邻接点；的邻接点；然后再依次然后再依次（顺序）（顺序

45、）访问这些点访问这些点（下一层）（下一层）中未被中未被访问过的邻接点；访问过的邻接点；直到所有顶点都被访问过为止。直到所有顶点都被访问过为止。广度优先搜索是一种分层的搜索过程，每向前走一广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回步可能访问一批顶点，不像深度优先搜索那样有回退的情况。退的情况。因此，广度优先搜索不是一个递归的过程，其算法因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。也不是递归的。讨论讨论1：计算机如何实现：计算机如何实现BFS？邻接表邻接表宽度优先搜索要借助队列！宽度优先搜索要借助队列！例：例：起点起点辅助队列辅助队列v2

46、已访问过了已访问过了V2入队入队visited n 仍需要仍需要while(rear!=front)/队不空时队不空时 front=(front+1)%n;v=qfront;/访问过的顶点出队访问过的顶点出队 p=Listv.firstarc;/P/P指向第指向第1 1个邻接点个邻接点 while(!p)if(!Visitedadjvex(p)/未到表尾，且邻接域未访问过，未到表尾，且邻接域未访问过，Visit(adjvex(p);Visitedadjvex(p)=1;/则先输出再改标记，则先输出再改标记，rear=(rear+1)%n;qrear=adjvex(p)/最后再入队最后再入队 p

47、=nextarc(p);/指向单链表中下一个邻接点指向单链表中下一个邻接点 return /BFS1/BFS1讨论讨论2：BFS算法如何编程？算法如何编程？BFS1(List,n,v)/List/List为邻接表，为邻接表，v v为起点，为起点，QnQn为辅助队列为辅助队列 Visit(v);Visitedv=1;/访问（例如打印）顶点访问（例如打印）顶点v v并修改标志并修改标志 层次遍历应当用队列！层次遍历应当用队列！（教材上（教材上BFSBFS算法见算法见P170P170）front=n-1;rear=0;/队列指针初始化队列指针初始化qrear=v;/起始点入队起始点入队 空间复杂度相

48、同，都是空间复杂度相同，都是O(n)O(n)(借用堆栈或队列装借用堆栈或队列装n n个顶点）；个顶点）；时间复杂度只与存储结构时间复杂度只与存储结构（邻接矩阵或邻接表）（邻接矩阵或邻接表）有关，而有关，而与搜索路径无关。与搜索路径无关。如果使用邻接表来表示图，则如果使用邻接表来表示图，则BFS循环的总时间代价为循环的总时间代价为 d0+d1+dn-1=O(e)，其中的其中的 di 是顶点是顶点 i 的度的度。如果使用邻接矩阵，则如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（都要循环检测矩阵中的整整一行（n 个元素），总的个元素），总

49、的时间代价为时间代价为O(n2)。（）7.4 7.4 图的连通性问题图的连通性问题1.求图的生成树求图的生成树2.求最小生成树求最小生成树生成树：是一个极小连通子图，它含有图中全部顶点，但只有生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1n-1条边。条边。生成森林：由若干棵生成树组成，含全部顶点，但构成这些树生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。的边是最少的。思考1：若对连通图进行遍历，得到的是什么？得到的将是一个极小连通子图，即图的生成树！得到的将是一个极小连通子图，即图的生成树！由深度优先搜索得到的生成树，称为深度优先搜索生成树。由深度优先搜索得

50、到的生成树，称为深度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成树。思考2：若对非连通图进行遍历，得到的是什么？得到的将是各连通分量的生成树，即图的生成森林！得到的将是各连通分量的生成树，即图的生成森林！例例1：画出下图的生成树：画出下图的生成树DFS生生成成树树v0v1v2v4v4v3邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成树树v0v1v3v2v4无向连通图无向连通图其实由邻接矩阵或邻接表其实由邻接矩阵或邻接表也能直接画出生成森林也能直接画出生成森林DEABCFJ