数据结构第7章图课件

第七章第七章 图图教学时间教学时间：6学时教学目的教学目的：1、理解图的基本概念和基本术语；2、掌握图的存储结构，图的遍历及其最小生成树；3、理解最短路径的求解，AOV网的应用。4、了解关键路径教学内容教学内容：图的基本概念和基本术语、图的存储结构，图的遍历及其最小生成树、最短路径的求解，AOV网的应用、求解关键路径第七章第七章 图图课题15：图的定义及其存储结构教学时间教学时间：2学时教学目的教学目的：1、理解图的基本概念和基本术语；2、掌握图的存储结构教学内容教学内容：图的基本概念和基本术语、图的邻接矩阵和邻接表的存储教学重点教学重点：图的存储结构教学教学难点难点：图的存储结构教学方法教学方法：讲授，投影教学过程教学过程:内容：7.1图的定义和术语 抽象数据类型图的定义 生成树、生成森林7.2图的存储结构7.2.1数组表示法 图的邻接矩阵7.2.2邻接表 邻接表 逆邻接表7.2.3十字链表7.2.4邻接多重表课堂练习课题课题1515 ：图的定义及其存储结构：图的定义及其存储结构第七章 图型结构图状结构是一种比树形结构更复杂的非线性结构。在树状结构中，结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图状结构被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。7.1 7.1 图的定义和术语图的定义和术语1.1.基本术语基本术语(1)(1)顶点顶点 图中的数据元素通常称为顶点。图中的数据元素通常称为顶点。V V是顶点的有是顶点的有穷非空集合；穷非空集合；VRVR是两个顶点之间的关系的集合。是两个顶点之间的关系的集合。(2)(2)有向图有向图 若称若称 VRVR表示从表示从v v到到w w的一条的一条弧，弧，且称且称v v为弧尾或初始点，称为弧尾或初始点，称w w为弧头或终端结点，则该图为弧头或终端结点，则该图称为有向图。称为有向图。(3)(3)无向图无向图 若若VRVR，必有，必有VRVR，即，即VRVR是对称是对称的，则以无序对的，则以无序对（v,wv,w)代替这两个有序对，表示代替这两个有序对，表示v v和和w w之间的一条之间的一条边边，则该图称为无向图。，则该图称为无向图。(4)(4)权权/网网 有时图的边或弧具有与它相关的数，这些数有时图的边或弧具有与它相关的数，这些数称为权值（通常表示顶点间的距离或耗费），则称为权值（通常表示顶点间的距离或耗费），则带权值的图称为网。带权值的图称为网。(5)(5)子图子图 假设有两个图假设有两个图 G=G=（V V，VR VR）和）和 G G=（V V，VR VR ），若），若 V V 是是 V V 的子集，的子集，且且 VRVR 是是 VR VR 的子集，则称的子集，则称 G G 为为 G G 的子图。的子图。G1的子图G2的子图(6)(6)完全图完全图 假设用假设用 n n 表示图中顶点的数目，用表示图中顶点的数目，用 e e 表示表示边或弧的数目。忽略自身弧边或弧的数目。忽略自身弧/边，即若边，即若v vi i,v,vj j VRVR，则，则 v vi ivvj j。对于无向图，有对于无向图，有 (n(n-1)/2(n(n-1)/2 条边的无向图条边的无向图称为完全图。对于有向图，有称为完全图。对于有向图，有 n(n-1)n(n-1)条弧的有条弧的有向图称为有向完全图。向图称为有向完全图。(7)(7)稀疏图稀疏图/稠密图稠密图 边或弧很少（如边或弧很少（如e enlognnlogn）的图称稀疏图，）的图称稀疏图，反之称稠密图。反之称稠密图。(8)(8)邻接点邻接点 对于对于无向图无向图G=(V,E)G=(V,E)，若边，若边(v,v(v,v)E)E，则，则称顶点称顶点 v v 和和 v v 互为互为邻接点邻接点，即，即 v v 和和 v v 相邻相邻接。或称边（接。或称边（v,vv,v）依附于依附于顶点顶点v v 和和 v v，或称，或称（v,vv,v）和顶点）和顶点 v v 和和 v v 相关联相关联。对于对于有向图有向图G=(VG=(V，E)E)，若弧，若弧v E E，则称顶点则称顶点 v v 邻接邻接到到顶点顶点 v v，或称顶点，或称顶点 v v 邻接邻接自自顶点顶点 v v，或弧，或弧v 和顶点和顶点 v v，v v 相关联相关联。(a)(b)顶点的入度顶点的入度/出度出度 以顶点以顶点 v v 为头的弧的数目称为头的弧的数目称 v v 的入度，记为的入度，记为ID(v)ID(v)；以顶点；以顶点 v v 为尾的弧的数目称为尾的弧的数目称 v v 的出度，的出度，记为记为 OD(v)OD(v)。顶点顶点 v v 的度的度 TDTD（v v）=ID=ID（v v）ODOD（v v）(9)顶点v的度(Degree)是和v相关联的边的数目，记为 TD（v）。(a)(b)(10)(10)路径路径(Path)(Path)无向图无向图G=G=(V,E)V,E)中，从顶点中，从顶点v v到到v v的路径是顶的路径是顶点序列点序列(v=v(v=vi i0 0,v,vi i1 1,v,vi im m=v=v)，其中，其中(v(vi ij-1 j-1,v,vi ij j)E)E，1jm1jm。若若G G是有向图，则路径也是有向的，顶点序列应是有向图，则路径也是有向的，顶点序列应满足：满足：vE E，1jm1jm。路径的长度是路径上的边或弧的数目。(11)(11)回路回路/环环/简单路径简单路径 第一个顶点和最后一个顶点相同的路径称为第一个顶点和最后一个顶点相同的路径称为回路回路/环环。序列中顶点不重复出现的路径称为序列中顶点不重复出现的路径称为简单路径简单路径。除了第一个顶点和最后一个顶点之外，其余顶点除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为不重复出现的回路，称为简单回路或简单环简单回路或简单环。(12)(12)连通图连通图/连通分量连通分量 在在无向图无向图G G中，如果从顶点中，如果从顶点 V V 到顶点到顶点 V V 有有路径，则称路径，则称 V V 和和 V V 是连通的。是连通的。若图中任意两个顶点若图中任意两个顶点 v vi i、v vj jVV，v vi i 和和 v vj j 都都是连通的，则称是连通的，则称 G G 是是连通图连通图。无向图中的无向图中的极大连通子图极大连通子图称之为称之为连通分量连通分量。左图：连通图下图：非连通图，但有 三个连通分量(13)(13)强连通图强连通图/强连通分量强连通分量 在在有向图有向图 G G 中，若对于每一对中，若对于每一对v vi i、v vj jVV，v vi ivvj j，从，从 v vi i 到到 v vj j 和从和从 v vj j 到到 v vi i 都存在路径，都存在路径，则称则称 G G 是是强连通图强连通图。有向图中的有向图中的极大强连通子图极大强连通子图称作称作有向图的强有向图的强连通分量连通分量。非强连通图 两个强连通分量 一个连通图的生成树是一个极小连通子图，一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的它含有图中全部顶点，但只有足以构成一棵树的n-1n-1条边。条边。如果在一棵生成树上添加一条边，必定构成如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。间有了第二条路径。(14)生成树 如果一个有向图恰有一个顶点的入度为如果一个有向图恰有一个顶点的入度为 0 0，其余顶点的入度均为其余顶点的入度均为 1 1，则是一棵有向树。一个，则是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有中全部顶点，但只有足以构成若干棵不相交的有向树的弧。向树的弧。(15)生成森林2.图的抽象类型定义ADT Graph 数据对象V：V是具有相同特性的数据元素的集 合，称为顶点集。数据关系R：R=VR VR=|v,wV且P(v,w)，表示从v到w的弧，谓词P(v,w)定义了 弧的意义或信息 基本操作P：ADT Graph基本操作基本操作CreateGraph(&G,V,VR);/CreateGraph(&G,V,VR);/按按V V和和VRVR的定义构造图的定义构造图G GDestroyGraph(&G);/DestroyGraph(&G);/销毁图销毁图G GLocateVex(G,u);/LocateVex(G,u);/若若G G中存在顶点中存在顶点u u，则返回该顶点，则返回该顶点 /在图中位置；否则返回其它信息在图中位置；否则返回其它信息GetVex(G,v);/GetVex(G,v);/返回返回 v v 的值的值PutVex(&G,v,value);/PutVex(&G,v,value);/对对 v v 赋值赋值valuevalueFirstAdjVex(G,v);/FirstAdjVex(G,v);/返回返回v v的第一个邻接点。的第一个邻接点。/若若v v在在G G中没有邻接点，则返回中没有邻接点，则返回“空空”NextAdjVex(G,v,w);/NextAdjVex(G,v,w);/返回返回v v的的(相对于相对于w w的的)下一下一 /个邻接点。若个邻接点。若w w是是v v的最后一个邻接点，则的最后一个邻接点，则“空空”InsertVex(&G,v);/InsertVex(&G,v);/在图在图G G中增添新顶点中增添新顶点v v。DeleteVex(&G,v);/DeleteVex(&G,v);/删除删除G G中顶点中顶点v v及其相关的弧及其相关的弧InsertArc(&G,v,w);/InsertArc(&G,v,w);/在在G G中增添弧中增添弧，若，若G G /是无向的，则还增添对称弧是无向的，则还增添对称弧DeleteArc(&G,v,w);/DeleteArc(&G,v,w);/在在G G中删除弧中删除弧，若，若G G /是无向的，则还删除对称弧是无向的，则还删除对称弧DFSTraverse(G,v,Visit();DFSTraverse(G,v,Visit();/从顶点从顶点v v起深度优先遍历图起深度优先遍历图G G，并对每个顶点调用，并对每个顶点调用/函数函数 VisitVisit一次且仅一次。一次且仅一次。BFSTraverse(G,v,Visit();BFSTraverse(G,v,Visit();/从顶点从顶点v v起广度优先遍历图起广度优先遍历图G G，并对每个顶点调用，并对每个顶点调用/函数函数 VisitVisit一次且仅一次。一次且仅一次。第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径7.2 7.2 图的存储结构图的存储结构n图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示n图的邻接表存储表示图的邻接表存储表示n有向图的十字链表存储表示有向图的十字链表存储表示n无向图的邻接多重表存储表示无向图的邻接多重表存储表示1.1.图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示 邻接矩阵邻接矩阵是用于描述图中顶点之间关系是用于描述图中顶点之间关系(即弧即弧或边的权或边的权)的矩阵。的矩阵。假设图中顶点数为假设图中顶点数为n n，则邻接矩阵，则邻接矩阵A An nn n：1 1 若若ViVi和和VjVj之间有弧或边之间有弧或边 Aij=Aij=0 0 反之反之 CADB CABDCBAA=0111101111011110A B C DA B C CBAB=010100110注意：1)图中无邻接到自身的弧，因此邻接矩阵主对角线为全零。2)无向图的邻接矩阵必然是对称矩阵。3)无向图中，顶点的度是邻接矩阵对应行（或列）的非零元素之和；有向图中，对应行的非零元素之和是该顶点的出度；对应列的非零元素之和是该顶点的入度；则该顶点的度是对应行和对应列的非零元素之和。V1V2V3V4V5V65485931567网的邻接矩阵网的邻接矩阵 反之权值 若Vi和Vj之间有弧或边Aij=图的数组（邻接矩阵）存储表示#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /最大顶点个数typedef enum DG,DN,UDG,UDN GraphKind;/图类型（有向图/网,无向图/网）typedef struct ArcCell VRType adj;/VRType是顶点关系类型。对无权图，用1或0 表示相邻否；对带权图，则为权值类型。InfoType*info;/指向该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;/描述顶点的数组 AdjMatrix arcs;/邻接矩阵 int vexnum,arcnum;/图的当前顶点数和弧(边)数 GraphKind kind;/图的种类标志 MGraph;构造图的算法构造图的算法 Status CreateGraph(Mgraph&G)Status CreateGraph(Mgraph&G)/采用数组采用数组(邻接矩阵邻接矩阵)表示法，构造图表示法，构造图G G。scanf(&G.kind)scanf(&G.kind)；switch(G.kind)switch(G.kind)case DGcase DG：return CreateDG(G)return CreateDG(G)；/构造有向图构造有向图G G case DNcase DN：return CreateDN(G)return CreateDN(G)；/构造有向网构造有向网G G case UDGcase UDG：return CreateUDG(G)return CreateUDG(G)；/构造无向图构造无向图G Gcase UDNcase UDN：return CreateUDN(G)return CreateUDN(G)；/构造无向网构造无向网G Gdefaultdefault：return ERRORreturn ERROR；/CreateGraph/CreateGraph采用数组表示法，构造无向网采用数组表示法，构造无向网G GStatus CreateUDN(MGraph&G)Status CreateUDN(MGraph&G)sacnf(&G.vexnum,&G.arcnum,&IncInfo);sacnf(&G.vexnum,&G.arcnum,&IncInfo);for(i=0;iG.vexnum;+i)scanf(&G.vexsi);for(i=0;iG.vexnum;+i)scanf(&G.vexsi);/构造顶点向量构造顶点向量for(i=0for(i=0；iG.vexnumiG.vexnum；+i)+i)/初始化邻接矩阵初始化邻接矩阵 for(j=0;jG.vexnum;+j)G.arcsij=INFINITY,NULL;for(j=0;jG.vexnum;+j)G.arcsij=INFINITY,NULL;/adj,info /adj,infofor(k=0for(k=0；kG.arcnumkG.arcnum；+k)+k)/构造邻接矩阵构造邻接矩阵 scanf(&v1scanf(&v1，&v2&v2，&w)&w)；/输入一条边依附的顶点及权值输入一条边依附的顶点及权值 i=LocateVex(G,v1);j=LocateVex(G,v2);i=LocateVex(G,v1);j=LocateVex(G,v2);/v1/v1和和v2v2在在G G中位置中位置 G.arcsij.adj=wG.arcsij.adj=w；/弧弧v1v2的权值的权值 if(IncInfo)Input(*G.arcsij.info);if(IncInfo)Input(*G.arcsij.info);G.arcsji=G.arcsij;G.arcsji=G.arcsij;/置置的对称弧的对称弧 return OK;return OK;/CreateUDN/CreateUDN 2.2.图的邻接表存储表示图的邻接表存储表示 类似树的孩子链表。即对图中的每个顶点vi建立一个单链表，表中结点表示依附于该顶点vi的边或弧。邻接点域邻接点域链域链域数据域数据域指示与顶点vi邻接的点在图中的位置指示下一条边或弧的结点存储和边或弧相关的信息数据域数据域链域链域指向链表第一个结点存储顶点vi和其他有关信息表结点表头结点V1V3V2V4V1V3V2V4例如：13443214432121113442注意：在无向图的邻接表中，1）第i个链表中结点数目为顶点i的度；2）所有链表中结点数目的一半为图中边数；3）占用的存储单元数目为n+2e。在有向图的邻接表中，1）第i个链表中结点数目为顶点i的出度；2）所有链表中结点数目为图中弧数；3）占用的存储单元数目为n+e。为求出每一个顶点的入度，必须另外建立有向图的逆邻接表。有向图的逆邻接表与邻接表类似，只是它是从入度考虑结点，而不是从出度考虑结点。2443211逆邻接表3V1V3V2V4图的邻接表图的邻接表图的邻接表图的邻接表图的逆邻接表图的逆邻接表图的逆邻接表图的逆邻接表1234512345V1V1V2V2V3V3V4V4V5V5图的邻接表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode*nextarc;/指向下一条弧的指针 InfoType*info;/该弧相关信息的指针 ArcNode;typedef struct VNode VertexType data;/顶点信息 ArcNode*firstarc;/指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数 int kind;/图的种类标志 ALGraph;3.3.有向图的十字链表存储表示有向图的十字链表存储表示 十字链表是有向图的另一种链式存储结构。可以理解成有向图的邻接表和逆邻接表的结合，在十字链表中，有两种结点结构：尾域尾域tailvextailvex头域头域headvexheadvex链域链域hlinkhlink链域链域tlinktlink信息域信息域infoinfo数据域数据域datadata链域链域firstinfirstin链域链域firstoutfirstout顶点结点弧结点尾域tv 指示弧尾顶点在图中的位置头域hv 指示弧头顶点在图中的位置链域h 指向弧头相同的下一条弧链域t 指向弧尾相同的下一条弧信息域 指向该弧的相关信息尾域尾域tailvextailvex头域头域headvexheadvex链域链域hlinkhlink链域链域tlinktlink信息域信息域infoinfo数据域数据域datadata链域链域firstinfirstin链域链域firstoutfirstout数据域 存储和顶点相关信息链域fin 指向以该顶点为弧头的第一个弧结点链域fout 指向以该顶点为弧尾的第一个弧结点v1v2v3v4 0 1 2 3 10/20v3v1v4v2/03/13/2302/32例：datadatafirstinfirstinfirstoutfirstouttailvexheadvexhlinktlink/A A0 0B B1 1C C2 2D D3 3E E4 4有向图的十字链表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcBox int tailvex,headvex;/该弧的尾和头顶点的位置 struct ArcBox*hlink,*tlink;/分别指向下一个弧头相同 和弧尾相同的弧的指针域 InfoType*info;/该弧相关信息的指针 ArcBox;typedef struct VexNode VertexType data;ArcBox*firstin,*firstout;/分别指向该顶点第一条入弧 和出弧 VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM;/表头向量 int vexnum,arcnum;/有向图的当前顶点数和弧数 OLGraph;4.4.无向图的邻接多重表存储表示无向图的邻接多重表存储表示 在无向图的邻接表中，每条边（Vi，Vj）由两个结点表示，一个结点在第 i 个链表中，另一个结点在第 j 个链表中，当需要对边进行操作时，就需找到表示同一条边的两个结点，这给操作带来不便，在这种情况下采用邻接多重表较方便。邻接多重表中结点分为：边结点和顶点结点标志域 用于标记该边是否被搜索过边顶点i 该边依附的顶点vi在图中的位置边顶点j 该边依附的顶点vj在图中的位置链域i 指向下一条依附于顶点vi的边链域j 指向下一条依附于顶点vj的边信息域指向和边相关的各种信息的指针域数据域 存储和该顶点相关的信息边链域指示第一条依附于该顶点的边标志域标志域边顶点边顶点i i边顶点边顶点j j链域链域i i 链域链域j j 信息域信息域数据域数据域边链域边链域1 3 4 2 例1234121324无向图的邻接多重表存储表示#define MAX_VERTEX_NUM 20typedef emnu unvisited,visited VisitIf;typedef struct Ebox VisitIf mark;/访问标记 int ivex,jvex;/该边依附的两个顶点的位置 struct EBox*ilink,*jlink;/分别指向依附这两个顶点的 下一条边 InfoType*info;/该边信息指针 EBox;typedef struct VexBox VertexType data;EBox*firstedge;/指向第一条依附该顶点的边VexBoxtypedef struct VexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;/无向图的当前顶点数和边数 AMLGraph;课题课题1616 ：图的遍历：图的遍历 最小生成树最小生成树教学时间教学时间：2学时教学目的教学目的：图的遍历及其应用教学内容教学内容：图的深度和广度遍历方法和算法教学重点教学重点：图的遍历方法教学教学难点难点：图的遍历算法教学方法教学方法：讲授，投影教学过程教学过程:内容：7.3图的遍历 图的遍历7.3.1深度优先搜索7.3.2广度优先搜索 算法及时间复杂度的分析7.4图的连通性问题7.4.1无向图的连通分量和生成树7.4.2有向图的强连通分量7.4.3最小生成树 普里姆算法 克鲁斯卡尔算法课题课题16：图的遍历：图的遍历最小生成树最小生成树7.3 7.3 图的遍历图的遍历 从图中某一顶点出发访遍图中其余顶点，且使从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做每一个顶点仅被访问一次。这一过程就叫做图的图的遍历遍历。通常有两条遍历图的路径：通常有两条遍历图的路径：n深度优先搜索深度优先搜索n广度优先搜索广度优先搜索1.1.深度优先搜索深度优先搜索(DFS)(DFS)基本思想：从图中某顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点；重复上述过程，直至图中所有顶点都被访问到为止。例：从顶点v1出发，DFS下图。顶点访问序列为：v1,v2,v4,v8,v5,v3,v6,v7或v1,v2,v5,v8,v4,v3,v6,v7或v1,v3,v7,v6,v2,v4,v8,v5v1v6v2v5v3v8v4v7图的DFS算法一般描述intvisitedMAXVEX;/访问标志数组voidDFSgraph(GraphG,Visit()/对图G作深度优先遍历for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化for(v=0;v=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w递归调用DFS用邻接表实现图的深度优先搜索v1v6v2v5v3v8v4v7v9v1012345678 2 8 2 8 3 7 3 6 4 5 2 3 2 3 1 6 7 1 4 5910 9/10/分析：分析：在遍历图时，对图中每个顶点至多调用一次在遍历图时，对图中每个顶点至多调用一次DFSDFS函数，因为一旦某个顶点被标志成已被访问，函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。用的存储结构。2.2.广度优先搜索广度优先搜索(BFS)(BFS)基本思想：从图中某个顶点V0出发，并在访问此顶点后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点；重复上述过程，直至图中所有顶点都被访问到为止。例：从顶点v1出发，BFS下图。顶点访问序列为：v1,v2,v3,v4,v5,v6,v7,v8或v1,v3,v2,v6,v7,v5,v4,v8v1v6v2v5v3v8v4v7用邻接表实现图的广度优先搜索12345678 2 8 2 8 3 7 3 6 4 5 2 3 2 3 1 6 7 1 4 5v1v6v2v5v3v8v4v7B BFSFS非递归非递归算法算法void BFSTraverse(Graph G,Status(*Visit)(int v)void BFSTraverse(Graph G,Status(*Visit)(int v)/使用辅助队列使用辅助队列Q Q和访问标志数组和访问标志数组visitedv visitedv for(v=0;vG.vexnum;+v)visitedv=FALSE;for(v=0;vG.vexnum;+v)visitedv=FALSE;InitQueue(Q);InitQueue(Q);/置空的辅助队列置空的辅助队列Q Q for(v=0;vG.vexnum;+v)for(v=0;v=0;w=NextAdjVex(G,u,w)for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)）if(!visitedw)if(!visitedw)/w/w为为u u的尚未访问的邻接顶点的尚未访问的邻接顶点 visitedw=TRUE;Visit(w);visitedw=TRUE;Visit(w);EnQueue(Q,w);EnQueue(Q,w);/if /if /while /while if if /BFSTraverse /BFSTraverse分析：分析：每个顶点至多进一次队列。遍历图的过程实质每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。两者不同之处仅仅在于对顶点访问的顺序不同。7.4 7.4 图的连通性问题图的连通性问题1 1）无向图的无向图的连通分量和连通分量和生成树生成树2 2）最小生成树最小生成树3 3）普里姆算法）普里姆算法4 4）克鲁斯卡尔算法）克鲁斯卡尔算法1.1.无向图的无向图的连通分量和连通分量和生成树生成树基本概念基本概念n连通分量的顶点集连通分量的顶点集：即从该连通分量的某一：即从该连通分量的某一顶点出发进行搜索所得到的顶点访问序列；顶点出发进行搜索所得到的顶点访问序列；n生成树生成树：某连通分量的极小连通子图某连通分量的极小连通子图；n生成森林生成森林：非连通图的各个连通分量的极小：非连通图的各个连通分量的极小连通子图构成的集合连通子图构成的集合。设设E(G)E(G)为连通子图为连通子图G G中所有边的集合，则从图中所有边的集合，则从图中任一顶点出发遍历图时，必定将中任一顶点出发遍历图时，必定将E(G)E(G)分成两个分成两个集合集合T(G)T(G)和和B(G)B(G)，其中，其中T(G)T(G)是遍历过程中历经的是遍历过程中历经的边的集合。显然，边的集合。显然，T(G)T(G)和图和图G G中所有顶点一起构成中所有顶点一起构成连通图连通图G G的极小连通子图，按照的极小连通子图，按照7.17.1节的定义，它节的定义，它是连通图的一棵生成树，并且称由深度优先搜索是连通图的一棵生成树，并且称由深度优先搜索得到的为得到的为深度优先生成树深度优先生成树；由广度优先搜索得到；由广度优先搜索得到的为的为广度优先生成树广度优先生成树。例：例：图及其生成树图及其生成树65665513420例：求下图的深度优先生成树和广度优先生成树。v1v6v2v5v3v8v4v7 对非连通图，每个连通分量中的顶点集和遍对非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树，这些连通历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的分量的生成树组成非连通图的生成森林生成森林。例：例：生成非连通图的深度优先生成森林的算法生成非连通图的深度优先生成森林的算法voidDFSForest(GraphG，CSTree&T)/建立无向图G的深度优先生成森林的(左)孩子(右)兄弟链表T。T=NULL；for(v=0；vG.vexnum；+v)visitedv=FALSE；for(v=0；vnextsibling=p;/是其它生成树的根(前一棵的根的“兄弟”)q=p;/q指示当前生成树的根DFSTree(G,v,p);/建立以p为根的生成树/DFSForestvoid DFSTree(Graph Gvoid DFSTree(Graph G，int vint v，CSTree&T)CSTree&T)/从第从第v v个顶点出发深度优先遍历图个顶点出发深度优先遍历图Q Q，建立以，建立以T T为根的生成树。为根的生成树。visitedv=TRUEvisitedv=TRUE；first=TRUEfirst=TRUE；for(w=FisrtAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)for(w=FisrtAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)if(!visitedw)p=(CSTree)malloc(sizeof(CSNode);p=(CSTree)malloc(sizeof(CSNode);/分配孩子结点分配孩子结点 *p=GetVex(G,w)p=GetVex(G,w)，NULLNULL，NULLNULL；if(first)if(first)/w/w是是v v的第一个未被访问的邻接顶点的第一个未被访问的邻接顶点 T Tlchild=plchild=p；first=FALSEfirst=FALSE；/是根的左孩子结点是根的左孩子结点 else else /w/w是是v v的其它未被访问的邻接顶点的其它未被访问的邻接顶点 q qnextsibling=pnextsibling=p；/是上一邻接顶点的右兄弟结点是上一邻接顶点的右兄弟结点 q=p q=p；DFSTree(G,w,q)DFSTree(G,w,q)；/从第从第w w个顶点出发深度优先遍历图个顶点出发深度优先遍历图G G，建立子生成树，建立子生成树q q /if/if /DFSTree/DFSTree 对于带权的连通图对于带权的连通图(连通网连通网)G G，其生成树也是，其生成树也是带权的，将权值之和最小的生成树称为带权的，将权值之和最小的生成树称为最小生成最小生成树树。连通网最小生成树的意义？连通网最小生成树的意义？如何构造最小生成树？如何构造最小生成树？2 2 最小生成树最小生成树最小生成树的最小生成树的MSTMST性质：性质：假设假设 N=N=（V,EV,E）是一个连通网，）是一个连通网，U U是顶点是顶点集集 V V 的一个非空子集。若（的一个非空子集。若（u,vu,v）是一条具有最）是一条具有最小权值（代价）的边，其中小权值（代价）的边，其中 u Uu U，vV-UvV-U，则，则必存在一棵包含边（必存在一棵包含边（u,vu,v）的最小生成树。）的最小生成树。656655134203.3.普里姆（普里姆（PrimPrim）算法）算法基本思想：基本思想：(1)(1)假设假设 G=(V,E)G=(V,E)是一个具有是一个具有 n n 个顶点的连通个顶点的连通网络，网络，T=(UT=(U，TE)TE)是是 G G 的最小生成树，其中的最小生成树，其中 U U 是是 T T 的顶点集，的顶点集，TE TE 是是 T T 的边集，的边集，U U 和和 TE TE 的初值均为空；的初值均为空；(2)(2)从从 V V 中任取一个顶点（假定为中任取一个顶点（假定为 V V1 1），将此顶），将此顶点并入点并入 U U中，此时最小生成树顶点集中，此时最小生成树顶点集 U=VU=V1 1；(3)(3)从那些其中一个端点已在从那些其中一个端点已在 U U 中，另一端点仍中，另一端点仍在在 U U 外的所有边中，找一条最短（即权值最外的所有边中，找一条最短（即权值最小）的边，设该边为小）的边，设该边为(V(Vi i,V,Vj j)，其中，其中 V Vi iUU，V Vj jV-UV-U，并把该边和顶点，并把该边和顶点 V Vj j分别并入分别并入 T T 的边的边集集 TE TE 和顶点集和顶点集 U U；(4)(4)如此进行下去，每次往生成树里并入一个顶点如此进行下去，每次往生成树里并入一个顶点和一条边，直到和一条边，直到 n-1 n-1 次后，把所有次后，把所有 n n 个顶点个顶点都并入生成树都并入生成树 T T 的顶点集的顶点集 U U 中，此时中，此时 U=VU=V，TETE中包含有（中包含有（n-1n-1）条边；这样，）条边；这样，T T 就是最后就是最后得到的最小生成树。得到的最小生成树。实现该算法需附设一个辅助数组实现该算法需附设一个辅助数组closedgeclosedge，以记录从以记录从 U U 到到 V-U V-U 具有最小代价的边。对每个具有最小代价的边。对每个顶点顶点 v vi iV-UV-U，在辅助数组中存在一个相应分量，在辅助数组中存在一个相应分量closedgei-1(closedgei-1(下标从下标从0 0开始开始)，它包括两个域。，它包括两个域。其中：其中：lowcostlowcost存储该边上的权。显然，存储该边上的权。显然，closedgei-1.lowcostclosedgei-1.lowcost =Mincost(u =Mincost(u，v vi i)|uU)|uU 即即v vi i到已生成子树的最短距离等于到到已生成子树的最短距离等于到U U中所有中所有顶点中的最小边的权值。顶点中的最小边的权值。vexvex域域存储该边依附的在存储该边依附的在U U中的顶点。中的顶点。利用普里姆算法从顶点利用普里姆算法从顶点v1开始构造连通网开始构造连通网G的最小生成树的过程。的最小生成树的过程。图7.11给出了从顶点V1出发算法实现过程中辅助数组中各分量的值。普里姆算法的时间复杂度是O（n2），它适用于求边稠密的网的最小生成树。例例：求下图最小生成树。假设开始顶点就选为顶点：求下图最小生成树。假设开始顶点就选为顶点1 1，故有故有U=1U=1，V-U=2V-U=2，3 3，4 4，5 5，66 (a)无向网无向网64V1V1V2V2V4V4V3V36213V5V55V6V6556(b)U=1 V-U=2,3,4,5,6(b)U=1 V-U=2,3,4,5,61 12 23 34 45 56 66 65 51 15 53 31 12 24 45 56 61 14 45 56 6(c)U=1,3 V-U=2,4,5,6(c)U=1,3 V-U=2,4,5,63 31 1 2 24 45 56 6 4 42 21 15 5 6 6(d)U=1,3,6 V-(d)U=1,3,6 V-U=2,4,5U=2,4,53 31 12 24 45 56 64 42 21 15 56 6(e)U=1,3,6,4 V-U=2,5(e)U=1,3,6,4 V-U=2,5(f)U=1,3,6,4,2 V-U=5(f)U=1,3,6,4,2 V-U=51 12 24 43 35 56 64 42 21 15 53 3(g)U=1,3,6,4,2,5 V-U=54213124356(a)无向网无向网64V1V1V2V2V4V4V3V36213V5V55V6V6556基于邻接矩阵的普里姆算法基于邻接矩阵的普里姆算法 struct struct VertexType adjvex;/VertexType adjvex;/顶点编号顶点编号 VRType lowcost;/=Mincost(u,vVRType lowcost;/=Mincost(u,vi i|uU)|uU)closedgeMAX_VERTEX_NUM;closedgeMAX_VERTEX_NUM;Void MiniSpanTree_PRIM(MGraph G,VertexType u)Void MiniSpanTree_PRIM(MGraph G,VertexType u)k=LocateVex(G,u);k=LocateVex(G,u);/顶点顶点u u为构造生成树的起始点为构造生成树的起始点,返回顶点返回顶点u u在图中的位置在图中的位置 for(j=0;jG.vexnum;+j)for(j=0;jG.vexnum;+j)/辅助数组初始化辅助数组初始化 if(j!=k)if(j!=k)closedgej=u,closedgej=u,G.arcskj.adjG.arcskj.adj;closedgek.lowcost=0;closedgek.lowcost=0;/初始，初始，U Uuu边边k，j的权值的权值 for(i=1;iG.vexnum;+i)for(i=1;iG.vexnum;+i)/在其余顶点中选择在其余顶点中选择 k=minimum(closedge);k=minimum(closedge);/求出求出T T的下一结点的下一结点(k)(k)printf(closedgek.adjvex,G.vexsk);printf(closedgek.adjvex,G.vexsk);/输出生成树的边输出生成树的边 closedgek.lowcost=0;closedgek.lowcost=0;/第第k k顶点并入顶点并入U U集集 for(j=0;jG.vexnum;+j)for(j=0;jG.vexnum;+j)if(G.arcskj.adj closedgej.lowcost)if(G.arcskj.adj closedgej.lowcost)/新顶点并入新顶点并入U U后重新选择最小边后重新选择最小边 closedgej=G.vexsk,G.arcskj.adj;closedgej=G.vexsk,G.arcskj.adj;/for/for /MiniSpanTree_PRIM/MiniSpanTree_PRIMT(n)=O(nT(n)=O(n2 2)4.4.克鲁斯卡尔（克鲁斯卡尔（KruskalKruskal）算法）算法基本思想基本思想 为使生成树上总的权值最小，应使每条边上为使生成树上总的权值最小，应使每条边上的权值尽可能小，自然应从权值最小的边选起，的权值尽可能小，自然应从权值最小的边选起，直至选出直至选出n-1n-1条权值最小的边为止，同时这条权值最小的边为止，同时这n-1n-1条条边必须不构成回路。因此，并非每一条当前权值边必须不构成回路。因此，并非每一条当前权值最小的边都可选。最小的边都可选。4.4.克鲁斯卡尔（克鲁斯卡尔（KruskalKruskal）算法）算法具体做法具体做法 先构造一个只含先构造一个只含 n n个顶点的森林，然后依权个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中去，值从小到大从连通网中选择边加入到森林中去，并使森林中不产生回路，直至森林变成一棵树为并使森林中不产生回路，直至森林变成一棵树为止。止。例例：对下图中无向网，用克鲁斯卡尔算法求最小：对下图中无向网，用克鲁斯卡尔算法求最小生成树的过程。生成树的过程。2 22 21 15 56 61 13 34 4 无向网无向网64621355564 46 65 53 31 12 2345一般来讲：一般来讲：普里姆算法的时间复杂度为普里姆算法的时间复杂度为 O(nO(n2 2)，适于稠，适于稠密图；密图；克鲁斯卡尔算法需对克鲁斯卡尔算法需对 e e 条边按权值进行排条边按权值进行排序，其时间复杂度为序，其时间复杂度为 O(eloge)O(eloge)，适于稀疏图。，适于稀疏图。课题课题1717 ：有向无环图及应用：有向无环图及应用教学时间教学时间：2学时教学目的教学目的：应用图的遍历算法求各种简单路径问题（最短路径、拓扑排序、关键路径）教学内容教学内容：拓扑排序 最短路径 关键路径教学重点教学重点：最短路径、简单路径教学教学难点难点：路径算法教学方法教学方法：讲授，投影教学过程教学过程:内容：7.5有向无环图及其应用7.5.1拓扑排序 拓扑有序 AOV-网 算法7.5.2关键路径 关键路径 算法7.6最短路径7.6.1从某个源点到其余各顶点的最短路径 迪杰斯特拉算法7.6.2每一对顶点之间的最短路径 课堂练习课题课题1717 ：有向无环图及应用：有向无环图及应用7.5 7.5 有向无环图及其应用有向无环图及其应用 有向无环图有向无环图(directed acycline graph)(directed acycline graph)简简称称DAGDAG图，是描述一项工程或系统的进行过程的图，是描述一项工程或系统的进行过程的有效工具。有效工具。对整个工程和系统，人们关心的是两个方面对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行；二是估算整个的问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间。工程完成所必须的最短时间。有向无环图的应用：有向无环图的应用：n拓扑排序拓扑排序n关键路径关键路径 在工程实践中，一个工程项目往往由若干个在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：子项目组成，这些子项目间往往有多种关系：先后关系，即必须在一子项目完成后，才先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；能开始实施另一个子项目；子项目之间无次序要求，即两个子项目可子项目之间无次序要求，即两个子项目可以同时进行，互不影响。以同时进行，互不影响。我们用一种有向图来表示上述问题。在这种有向图中，顶点表示活动顶点表示活动，有向边表示活动的优有向边表示活动的优先关系先关系，这种有向图叫做顶点表示活动的网络(Activity On Vertex Network)简称为AOV网。7.5.1 7.5.1 拓扑排序拓扑排序n 在在AOVAOV网络中，如果顶点网络中，如果顶点V Vi i的活动必须在顶点的活动必须在顶点V Vj j的活动以的活动以前进行，则称前进行，则称V Vi i为为V Vj j的前趋顶点，而称的前趋顶点，而称V Vj j为为V Vi i的后继顶点。的后继顶点。这种前趋后继关系有这种前趋后继关系有传递性传递性。此外，任何活动。此外，任何活动i i不能以它自不能以它自己作为自己的前驱或后继，这叫做己作为自己的前驱或后继，这叫做反自反性反自反性。n 从前驱和后继的传递性和反自反性来看，从前驱和后继的传递性和反自反性来看，AOVAOV网中不能网中不能出现回路出现回路(有向环有向环)，回路表示顶点之间的先后关系进入了，回路表示顶点之间的先后关系进入了死循环。死循环。n 判断判断AOVAOV网是否有有向环的方法是对该网是否有有向环的方法是对该AOVAOV网进行拓扑排网进行拓扑排序，将序，将AOVAOV网中顶点排列成一个线性有序序列，若该线性序网中顶点排列成一个线性有序序列，若该线性序列中包含列中包含AOVAOV网全部顶点，则网全部顶点，则AOVAOV网无环，否则，网无环，否则，AOVAOV网中存网中存在有向环，该在有向环，该AOVAOV网所代表的工程是不可行的。网所代表的工程是不可行的。何谓何谓“拓扑排序拓扑排序”？n拓扑序列：拓扑序列：在在AOVAOV网中，若不存在回路，则所有活动可排列网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓动都排在该活动的前面，我们把此序列叫做拓扑序列。扑序列。n拓扑排序拓扑排序 由由AOVAOV网构造拓扑序列的过程叫拓扑排序。网构造拓扑序列的过程叫拓扑排序。AOVAOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的，满足上述定义的任，满足上述定义的任一线性序列都称为它的拓扑序列。一线性序列都称为它的拓扑序列。拓扑有序序列：拓扑有序序列：（C1C1，C2C2，C3C3，C4C4，C5C5，C8C8，C9C9，C7C7，C6C6）（C2C2，C5C5，C1C1，C8C8，C3C3，C9C9，C4C4，C7C7，C6C6）如何进行拓扑排序？如何进行拓扑排序？解决方法：解决方法：1 1）从有向图中选取一个没有前驱的顶点，并）从有向图中选取一个没有前驱的顶点，并输出之；输出之；2 2）从有向图中删去此顶点以及所有以它为尾）从有向图中删去此顶点以及所有以它为尾的弧；的弧；3 3）重复上述两步，直至图空，或者图不空但）重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。后一种情况说明有向找不到无前驱的顶点为止。后一种情况说明有向图中存在环。图中存在环。课程编号课程编号课程名称课程名称先导课程编号先导课程编号C1C1程序设计基础程序设计基础无无C2C2离散数学离散数学C1C1C3C3数据结构数据结构C1C1，C2C2C4C4汇编语言汇编语言C1C1C5C5算法分析与设计算法分析与设计C3C3，C4C4C6C6计算机组成原理计算机组成原理C11C11C7C7编译原理编译原理C5C5，C3C3C8C8操作系统操作系统C3C3，C6C6C9C9高等数学高等数学无无C C 1010线性代数线性代数C9C9C11C11普通物理普通物理C9C9C12C12数值分析数值分析C9C9，C10C10，C1C1课程先后关系如图：课程先后关系如图：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c11如何在计算机中实现如何在计算机中实现 拓扑排序呢？拓扑排序呢？拓扑排序算法的实现拓扑排序算法的实现n为了实现拓扑排序的算法，对给定的有向图可采用邻为了实现拓扑排序的算法，对给定的有向图可采用邻接表作为它的存储结构。接表作为它的存储结构。n将每个