数据结构图结构.pptx

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

1、特点：非线性结构，是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。图的应用极为广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。第第7 7章章 图图第1页/共74页7.1 基本术语7.2 存储结构7.3 图的遍历7.4 图的其他运算7.5 图的应用第第7 7章章 图图第2页/共74页7.1 7.1 图的基本术语图：记为 G(V,E)其中：V 是G的顶点集合，是有穷非空集；E 是G的边集合，是有穷集。问：当E(G)为空时，图G存在否？答：还存在！但此时图G只有顶点而没有边。有向

2、图：无向图：完全图：图G中的每条边都是有方向的；图G中的每条边都是无方向的；图G任意两个顶点都有一条边相连接；vv若若 n n 个顶点的无向图有个顶点的无向图有 n n(n n-1)/2-1)/2 条边条边,称为称为无向完全图无向完全图vv若若 n n 个顶点的有向图有个顶点的有向图有n(n-1)n(n-1)条边条边,称为称为有向完全图有向完全图V=vertex E=edge第3页/共74页证明：完全有向图有完全有向图有n(n-1)n(n-1)条边条边。证明：证明：若是完全有向图，则顶点若是完全有向图，则顶点1 1必与所有其他顶点各有必与所有其他顶点各有2 2条连线，即有条连线，即有2(n-1

3、)2(n-1)条边，条边，顶点顶点2 2有有2(n-2)2(n-2)条边，条边，顶点，顶点n-1n-1有有2 2条边条边,顶点顶点n n有有0 0条边条边.总边数总边数2(n-12(n-1 n-2n-21 10)=2(n-1+0)n/2=0)=2(n-1+0)n/2=n(n-1)n(n-1)完全无向图有完全无向图有n n(n n-1)/2-1)/2 条边条边。证明：证明：若是完全无向图，则顶点若是完全无向图，则顶点1 1必与所有其他顶点各有必与所有其他顶点各有1 1条连线，即有条连线，即有n-1n-1条边，顶条边，顶点点2 2有有n-2n-2条边，条边，顶点，顶点n-1n-1有有1 1条边条边

4、,顶点顶点n n有有0 0条边条边.总边数总边数 n-1n-1 n-2n-21 10=0=（n-1+0)n/2=n-1+0)n/2=n(n-1)/2n(n-1)/2 第4页/共74页例：判断下列4种图形各属什么类型？无向无向图(树)有向图有向n n(n n-1)/2-1)/2 条边条边n n(n n-1)-1)条边条边G1的顶点集合为V(G1)=0,1,2,3边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)完全图完全图第5页/共74页稀疏图：稀疏图：稠密图：稠密图：设有两个图 G(V,E)和 G(V,E)。若 V V 且 E E,则称 图G 是 图G

5、的子图。子 图：边较少的图。通常边数=E=1/2 E=1/2TD(vTD(vi i)答：是树！而且是一棵有向树！第8页/共74页生成树：生成树：是一个是一个是一个是一个极小连通子图极小连通子图极小连通子图极小连通子图，它含有图中全部顶点，但，它含有图中全部顶点，但，它含有图中全部顶点，但，它含有图中全部顶点，但只只只只 有有有有n n-1-1条边条边条边条边。如果在生成树上添加如果在生成树上添加如果在生成树上添加如果在生成树上添加1 1条边，必定构成一个环。条边，必定构成一个环。条边，必定构成一个环。条边，必定构成一个环。若图中有若图中有若图中有若图中有n n个顶点，却少于个顶点，却少于个顶点

6、，却少于个顶点，却少于n n-1-1条边，必为非连通条边，必为非连通条边，必为非连通条边，必为非连通图。图。图。图。生成森林：生成森林：由若干棵生成树组成，含全部顶点，但构成这由若干棵生成树组成，含全部顶点，但构成这由若干棵生成树组成，含全部顶点，但构成这由若干棵生成树组成，含全部顶点，但构成这些些些些 树的边是最少的。树的边是最少的。树的边是最少的。树的边是最少的。第9页/共74页简单路径：简单路径：路径上各顶点 v1,v2,.,vm 均不互相重复。回 路：例：若路径上第一个顶点 v1 与最后一个顶点vm 重合，则称这样的路径为回路或环。路径：在图在图 GG(V,E)(V,E)中中,若从顶点

7、若从顶点 vi vi 出发出发,沿一些边经过一些顶点沿一些边经过一些顶点 vp1,vp2,vp1,vp2,vpmvpm，到达顶点，到达顶点vj vj。则称顶点序列。则称顶点序列 (vi vp1 vp2.vpm vj)(vi vp1 vp2.vpm vj)为从顶点为从顶点vi vi 到顶到顶点点 vj vj 的路径。它经过的边的路径。它经过的边(vi,vp1)(vi,vp1)、(vp1,vp2)(vp1,vp2)、.、(vpm,vj)(vpm,vj)应当是属于应当是属于E E的边。的边。路径长度：非带权图的路径长度是指此路径上非带权图的路径长度是指此路径上 边的条数边的条数；带权图的路径长度是指

8、路径上带权图的路径长度是指路径上各边的权之和各边的权之和。第10页/共74页ADT Graph 数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VR；VR=|v,wV 且 P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息基本操作P：CreatGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。InsertVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中添加新顶点。（参见P156-257）图的抽象数据类型图的抽象数据类型注意：V 的大小写含义不同！第11页/

9、共74页7.2 7.2 图的存储结构图的特点：非线性结构（图的特点：非线性结构（m:n m:n）邻接表邻接多重表十字链表设计为邻接矩阵链式存储结构：顺序存储结构：无！（多个顶点，无序可言）但可用数组描述元素间关系。可用多重链表重点介绍：邻接矩阵(数组)表示法邻接表(链式)表示法第12页/共74页一、邻接矩阵（数组）表示法一、邻接矩阵（数组）表示法一、邻接矩阵（数组）表示法一、邻接矩阵（数组）表示法vv建立一个建立一个顶点表（记录各个顶点信息）顶点表（记录各个顶点信息）和一个和一个邻接矩阵（表示各个顶点之间关系）邻接矩阵（表示各个顶点之间关系）。vv设图设图 A=(A=(V V,E E)有有 n

10、 n 个顶点，则图的邻接矩阵是一个二维数组个顶点，则图的邻接矩阵是一个二维数组 A.EdgennA.Edgenn，定，定义为：义为：v1v2v3v5v4v4A例例1 1：邻接矩阵：邻接矩阵：A.Edge=（v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0分析分析1 1：无向图的邻接矩阵是无向图的邻接矩阵是对称对称的；的；分析分析2 2：顶点顶点i i 的的度度第第 i i 行行(列列)中中1 1 的个数的个数；特别：特别：完全图的邻接矩阵中，对角元素为完全图的邻接矩阵中，对角元素为0 0，其余全，其余

11、全1 1。0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0顶点表：顶点表：第13页/共74页例2：有向图的邻接矩阵分析分析1 1：有向图的邻接矩阵可能是不对称的。分析分析2 2：顶点的出度=第i行元素之和，OD(Vi)=A.Edge i j 顶点的入度=第i列元素之和。ID(Vi)=A.Edge j i 顶点的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(Vi)+ID(Vi)v1v2v3v4A A邻接矩阵：A.Edge=(v1 v2 v3 v4)v1

12、v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 第14页/共74页 容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。特别讨论：网（即有权图）的邻接矩阵定义为：A.Edge i j=Wij 或（vi,vj）V

13、R 无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：邻接矩阵：N.Edge=(v1 v2 v3 v4 v5 v6 )邻接矩阵法优点：邻接矩阵法缺点：顶点表：5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 第15页/共74页注：用两个数组分别存储顶点表和邻接矩阵#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /假设的最大顶点数Typedef enum DG,DN,AG,AN GraphKind;/有向/无向图，有向/无向网Typedef struct ArcCell /弧（边）结点

14、的定义 VRType adj;/顶点间关系，无权图取1或0；有权图取权值类型 InfoType *info;/该弧相关信息的指针ArcCell,AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM;Typedef struct /图的定义VertexType vexs MAX_VERTEX_NUM ;/顶点表，用一维向量即可AdjMatrix arcs;/邻接矩阵Int Vernum,arcnum;/顶点总数，弧（边）总数GraphKind kind;/图的种类标志Mgraph;图的邻接矩阵存储表示（参见教材P161）对于n个顶点的图或网，空间效率=O(n2)第16页

15、/共74页Status CreateUDN(Mgraph&G)/无向网的构造，用邻接矩阵表示scanf(&G.vexnum,&G.arcnum,&IncInfo);/输入总顶点数，总弧数和信息for(i=0;iG.vexnum,;+i)scanf(&G.vexsi);/输入顶点值，存入一维向量中for(i=0;iG.vexnum;+i)/对邻接矩阵n*n个单元初始化，adj=,info=NULL for(j=0;jG.vexnum;+j)G.arcsij=INFINITY,NULL;for(k=0;kG.arcnum;+k)/给邻接矩阵有关单元赋初值(循环次数弧数 scanf(&v1,&v2,

16、&w);/输入弧的两顶点以及对应权值 i=LocateVex(G,v1);j=LocateVex(G,v2);/找到两顶点在矩阵中的位置(n次?G.arcsij.adj=w;/输入对应权值 If(IncInfo)Input(*G.arcsij.info);/如果弧有信息则填入 G.arcsji=G.arcs i j；/无向网是对称矩阵 return OK;/CreateUDN 例：用邻接矩阵生成无向网的算法（参见教材P162）对于n个顶点e条弧的网，建网时间效率=O(n2+n+e*n)第17页/共74页二、邻接表（链式）表示二、邻接表（链式）表示二、邻接表（链式）表示二、邻接表（链式）表示法法

17、法法vv对每个顶点对每个顶点v vi i 建立一个建立一个单链表单链表，把与，把与v vi i有关联的有关联的边的信息边的信息（即度或出度边）（即度或出度边）链接链接起起来，表中每个结点都设为来，表中每个结点都设为3 3个域；个域；vv每个单链表还应当附设一个每个单链表还应当附设一个头结点头结点（设为（设为2 2个域），存个域），存v vi i信息；信息；adjvex nextarcinfodatafirstarc表结点表结点头结点头结点邻接点域，表示vi一个邻接点的位置链域，指向vi下一个边或弧的结点数据域，与边有关信息（如权值）数据域，存储顶点vi 信息链域，指向单链表的第一个结点vv 每

18、个单链表的每个单链表的头结点另外用顺序存储头结点另外用顺序存储结构存储。结构存储。第18页/共74页例例例例1 1：无向图的邻接表无向图的邻接表无向图的邻接表无向图的邻接表v1v2v3v5v4v4邻接表0123413341420例例2 2：有向图的邻接表有向图的邻接表v1v2v3v4V4V3V2V12301邻接表(出边)V4V3V2V13020逆邻接表(入边)注：邻接表不唯一，因各个边结点的链入顺序是任意的。邻接表不唯一，因各个边结点的链入顺序是任意的。v1v2v3v4v5231420第19页/共74页例例例例3 3：已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网

19、络。已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的存储结构形成后，图便唯一确定！第20页/共74页分析1:对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。邻接表存储法的特点：邻接表存储法的特点：分析2:在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？邻接表的缺点：怎样计算有向图顶点的出度？怎样计算有向图顶点的入度

20、？怎样计算有向图顶点Vi的度：需遍历全表邻接表的优点：TD(Vi)=单链表中链接的结点个数OD(Vi)单链出边表中链接的结点数I D(Vi)邻接点为Vi的弧个数TD(Vi)=OD(Vi)+I D(Vi)空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。第21页/共74页讨论：讨论：邻接表与邻接矩阵有什么异同之处？邻接表与邻接矩阵有什么异同之处？1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无

21、关）。邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（en2)第22页/共74页图的邻接表存储表示图的邻接表存储表示（参见教材（参见教材P163P163）#define MAX_VERTEX_NUM 20 /假设的最大顶点数Typedef struct ArcNode int adjvex;/该弧所指向的顶点位置 struct ArcNode*nextarcs;/指向下一条弧的指针 InfoArc *info;/该弧相关信息的指针 ArcNode；Typedef struct VN

22、ode /顶点结构 VertexType data;/顶点信息 ArcNode *firstarc;/指向依附该顶点的第一条弧的指针VNode,AdjList MAX_VERTEX_NUM;Typedef struct /图结构 AdjList vertics;/应包含邻接表 int vexnum,arcnum;/应包含顶点总数和弧总数 int kind;/还应说明图的种类（用标志）ALGraph;/图结构空间效率为O(n+2e)或O(n+e)时间效率为O(n+e*n)第23页/共74页 它是有向图的另一种链式结构。思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。1、每条弧对应一个结点(

23、称为弧结点，设5个域）2、每个顶点也对应一个结点（称为顶点结点，设3个域）tailvexheadvexHlinktlinkinfo顶点结点弧结点三、十字链表三、十字链表tailvex:弧尾顶点位置 headvex:弧头顶点位置hlink:弧头相同的下一弧位置tlink:弧尾相同的下一弧位置info:弧信息 n个顶点用顺序存储结构 data :存储顶点信息。Firstin :以顶点为弧头的第一条弧结点。Firstout:以顶点为弧尾的第一条弧结点。dataFirstinFirstout适用于有向图第24页/共74页#define MAX_VERTEX_NUM 20Typedef struct A

24、rcBox /弧结点结构 int tailvex,headvex;struct ArcBox*hlink,tlink;InfoType *info;ArcBox；Typedef struct VexNode /顶点结构 VertexType data;ArcBox *firstin,*firstout;VexNode;Typedef struct VexNode xlist MAX_VERTEX_NUM;/表头向量 int vexnum,arcnum;OLGraph;/图结构十字链表存储结构描述：十字链表存储结构描述：第25页/共74页0v11v22v33v4v1v2v3v40 1022 02

25、3例：例：画出有向图的十字链表。画出有向图的十字链表。十字链表优点：容易操作，如求顶点的入度、出度等。空间复杂度与邻接表相同；建立的时间复杂度与邻接表相同。303132数组下标不属结点分量第26页/共74页这是无向图的另一种存储结构，当对边操作时，无向图应采用此种结构存储。1、每条边只对应一个结点（称为边结点），设立6个域；2、每个顶点也对应一个结点（顶点结点），设立2个域；mark ivexilinkjvexjlinkinfo边结点四、邻接多重表四、邻接多重表mark：标志域，如处理过或搜索过。Ivex,jvex:顶点域，边依附的两个顶点位置。ilink:指向下一条依附顶点 i 的边结点位置

26、。jlink:指向下一条依附顶点 j 的边结点位置。info:边信息，如权值等。n个顶点用顺序存储结构 data :存储顶点信息。Firstedge:依附顶点的第一条边结点。dataFirstedge顶点结点适用于无向图第27页/共74页0v11v22v33v44v501031214232434v1v2v3v5v4v4例：例：画出无向图的邻接多重画出无向图的邻接多重表表邻接多重表优点：容易操作，如求顶点的度等。空间复杂度与邻接表相同；建立的时间复杂度与邻接表相同。数组下标不属结点分量第28页/共74页一、深度优先搜索二、广度优先搜索 7.3 图的遍历图的遍历遍历定义：从已给的连通图中某一顶点出

27、发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历图的遍历，它是，它是图的基本运算。遍历实质：找每个顶点的邻接点的过程。图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。解决思路：可设置一个辅助数组 visited n，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i 被访问，就立即改 visited i为1，防止它被多次访问。图常用的遍历：怎样避免重复访问？第29页/共74页一、深度优先搜索一、深度优先搜索一、深度优先搜索一、深度优先搜索(DFSDFSDFSDF

28、S)基本思想：仿树的先序遍历过程。Depth_First Searchv1v1v2v3v8v7v6v4v5DFS DFS 结果结果例例1 1：v2v4v8v5v3v6v7例例2 2：v2 v1 v3 v5 v2 v1 v3 v5 DFS DFS 结果结果v4 v4 v6 v6起点起点遍历步骤第30页/共74页深度优先搜索（遍历）步骤：深度优先搜索（遍历）步骤：详细归纳：E在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；E再从 w1 出发，访问与 w1邻接但还未被访问过的顶点 w2；E然后再从 w2 出发，进行类似的访问，E如此进行下去，直至到达所有的邻接顶点都被访问过

29、为止。E接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。简单归纳：1)访问起始点 v;2)若v的第1个邻接点没访问过，深度遍历此邻接点；3)若当前邻接点已访问过，再找v的第2个邻接点重新遍历。第31页/共74页讨论讨论1 1：计算机如何实现计算机如何实现DFSDFS？1 2345610 000002 20 0000030 0000040 0000050 0000060 0000000000012345601000011

30、100001 11 110001 11 11 10101 11 11 111 101 11 11 11 11 11DFS DFS 结果结果邻接矩阵A辅助数组 visited n 起点v2v1v3v5v2v1v3v5v4v4v6v6开辅助数组 visited n！例：1 23 456101 11 11 1002 21 1 00 01 1031 1 00 01 1041 1 00 001 1501 11 1 00060 001 100第32页/共74页讨论讨论2 2：在图的邻接表中如何进行在图的邻接表中如何进行DFSDFS？v0 v1 v2 v3v0 v1 v2 v3DFS DFS 结果结果000

31、00123辅助数组 visited n 1000110011101111例：照样借用visited n！起点0123注意：在邻接表中，并非每个链表元素（表结点）都被扫描到,遍历速度很快。第33页/共74页深度优先遍历图的算法:课本P169页Boolean visited MAX;/访问标志数组Status(*VisitFunc)(int v);/函数变量Void DFSTraverse(Graph G,Status(*Visit)(int v)/对图G做深度优先遍历 VisitFunc=Visit;/使用全局变量VisitFunc,使DFS不必设函数指针参数 for(v=0;vG.vexnum

32、;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;v=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对对v v的尚未访问的邻接点的尚未访问的邻接点w w递归调用递归调用DFSDFS 第35页/共74页DFS DFS 算法效率分析算法效率分析算法效率分析算法效率分析:（设图中有设图中有 n n 个顶点，个顶点，e e 条边条边）n如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。n如果用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问

33、n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。第36页/共74页二、广度优先搜索二、广度优先搜索二、广度优先搜索二、广度优先搜索(BFS BFS BFS BFS)基本思想：仿树的层次遍历过程。Breadth_First Searchv1v1v2v3v8v7v6v4v5BFS BFS 结果结果例例1 1：v2v3v4v5v6v7v8例例2 2：v3 v3 BFS BFS 结果结果v4v4 v5 v5 起点遍历步骤起点v2 v1 v6 v2 v1 v6 v9 v8 v7v9 v8 v7第37页/共74页广度优先搜

34、索（遍历）步骤：广度优先搜索（遍历）步骤：简单归纳：在访问了起始点v之后，依次访问 v的邻接点；然后再依次访问这些顶点中未被访问过的邻接点；直到所有顶点都被访问过为止。广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。第38页/共74页讨论讨论1 1：计算机如何实现计算机如何实现BFSBFS？邻接表除辅助数组visited n 外，还需再开一辅助队列！例：起点辅助队列v2已访问过了BFS BFS 遍历结果遍历结果入队！初始f=n-1,r=0第39页/共74页讨论2：BFS算法如何编程？Vo

35、id BFSTraverse(Graph G,Status(*Visit)(int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;InitQuene(Q);/置空的辅助队列Q for(v=0;v=0;w=NextAdjVex(G,u,w)if(!Visited w)/w为u的尚未访问的邻接顶点 Visited w=TRUE;Visit(w);EnQuene(Q,w);/if /while /if /BFSTraverse层次遍历应当用队列！（见课本P170）第40页/共74页BFS BFS 算法效率分析算法效率分析算法效率分析算法效率分析:DFSDFS与与BFSB

36、FS之比较：之比较：空间复杂度相同，都是O(n)(借用了堆栈或队列）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。如果使用邻接表来表示图，则BFS循环的总时间代价为 d0+d1+dn-1=O(e)，其中的 di 是顶点 i 的度。如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n 个元素），总的时间代价为O(n2)。（设图中有设图中有 n n 个顶点，个顶点，e e 条边条边）第41页/共74页7.4 7.4 图的其他运算1.求图的生成树2.求最小生成树3.求最短路径第42页/共74页1.求图的生成树求图的生成树生成树的特征n 个顶点的连

37、通网络的生成 树有 n 个顶点、n-1 条边。求生成树的方法DFS（深度优先搜索）和 BFS（广度优先搜索）对于连通图,仅需从图中任一顶点出发,进行DFS或BFS,便可访问到图中所有顶点.对于非连通图,需从多个顶点出发进行搜索,而每一次 从一个新的起始点出发进行搜索过程中 得到的顶点访问序 列恰为其各个连通 分量中的顶点集.第43页/共74页连通图的生成树连通图的生成树:按照按照DFS/BFSDFS/BFS方式图中方式图中所有顶点所有顶点和遍和遍历图过程中历图过程中历经的边历经的边构成该图的构成该图的DFS/BFSDFS/BFS生成树生成树.-教材教材P172 P172 算法算法7.87.8非

38、连通图的生成森林:每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树,这些连通分量的生成树组成非连通图的生成森林.-教材P171 算法7.7第44页/共74页连通图的深度优先生成树Void DFSTree(Graph G,int v,CSTree&T)/从第v个顶点出发深度优先遍历图G,建立以T为根的生成树 visitedv=TRUE;first=TRUE;for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)p=(CSTree)malloc(sizeof(CSNode);/分配孩子结点 *p=GetVex(G,w),NU

39、LL,NULL;if(first)第45页/共74页2.2.求最小生成树求最小生成树目标：在网的多个生成树中，寻找一个各边权值之和最小的生成树。应用：n个城市建网，如何选择n1条线路，使总费用最少？vKruskal（克鲁斯卡尔）算法vPrim（普里姆）算法 算法：任何一个无向连通图的最小生成树只有一种归并边归并顶点构造最小生成树的算法有许多，基本原则是：u尽可能选取权值最小的边，但不能构成回路；u选择n-1条边构成最小生成树。第46页/共74页KruskalKruskal（克鲁斯卡尔）算法（克鲁斯卡尔）算法算法思想：设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是其最小生成树。初值：

40、U=V，TE=。对G中的边按权值大小从小到大依次选取。选取权值最小的边(vi，vj)，若边(vi，vj)加入到TE后形成回路，则舍弃该边(边(vi，vj)；否则，将该边并入到TE中，即TE=TE(vi，vj)。重复，直到TE中包含有n-1条边为止。第47页/共74页KruskalKruskal（克鲁斯卡尔）算法（克鲁斯卡尔）算法例：1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 21 15 54 43 32 21 13 35 52 24 46 6(V1,V3)(V1,V3)(V4,V6)(V4,V6)(V2,V5)(V2,V5)(V3,V6)(V3

41、,V6)(V2,V3)(V2,V3)第48页/共74页计算机内怎样实现计算机内怎样实现KruskalKruskal算法？算法？算法设计思路：算法设计思路：见教材见教材P175P175最后一段最后一段.特点：将边归并适于求稀疏网的最小生成树。故采用邻接表作为图的存储表示。第49页/共74页（1）初始状态：U=u0,（u0 V），TE=,（2）从E中选择顶点分别属于U、V-U两个集合、且权值最小的边（u0,v0)，将顶点v0归并到集合U中，边（u0,v0)归并到TE中；（3）直到U=V为止。此时TE中必有n-1条边，T（V，TE）就是最小生成树。设：N=（V,E）是个连通网，另设U为最小生成树的顶

42、点集，TE为最小生成树的边集。构造步骤:普利姆（普利姆（PrimPrim）算法）算法第50页/共74页例：1 14 46 65 52 23 31 15 56 65 55 54 46 63 36 62 23 36 64 42 25 51 1注：在最小生成树的生成过程中，所选的边都是 一端在V-U中，另一端在U中。V1-V3-V6-V4-V2-V5第51页/共74页设计思路：设计思路：增设一辅助数组Closedge n，每个数组分量都有两个域：要求：使Colsedge i.lowcost=min(u,vi)u U 计算机内怎样实现计算机内怎样实现PrimPrim（普里姆）算法（普里姆）算法？Pri

43、m算法特点:将顶点归并，与边数无关，适于稠密网。故采用邻接矩阵作为图的存储表示。adjvexadjvexlowcostlowcostvi 在U中的邻点uColsedge iV-U中顶点viu与vi之间对应的边权从u1un中挑第52页/共74页vexlowcotvexlowcotvexlowcotvexlowcotvexlowcotVexlowcotV-UU65432vclosedge1423561655536426具体示例：具体示例：具体示例：具体示例：算法实现参见：教材P175 算法7.912,3,4,5,6161115111,32,4,5,60351536341,3,62,4,535062

44、3601,3,6,42,535036001,3,6,4,25000023000001,3,6,4,2,513起点46245235123456显然，Prim算法的时间效率O（n2）第53页/共74页一顶点到其余各顶点3.3.求最短路径求最短路径两种常见的最短路径问题：一、单源最短路径用Dijkstra（迪杰斯特拉）算法二、所有顶点间的最短路径用Floyd（弗洛伊德）算法典型用途：交通问题。如：城市A到城市B有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何选择一条线路，使总费用（或总时间）最少？问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的

45、路径，即最短路径。（注：最短路径与最小生成树不同，路径上不一定包含n个顶点）任意两顶点之间第54页/共74页一、单源最短路径一、单源最短路径 (Dijkstra算法算法)目的：设一有向图G=（V,E），已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于或等于0。例1：源点从FA的路径有4条：FA：24 FBA：518=23 FBCA：5+7+9=21 FDCA：25+12+9=36又：从FB的最短路径是哪条？从FC的最短路径是哪条？第55页/共74页v0(v0,v1)10源点终点 最 短路 径路径长度(v0,v1,v2)(v0,v3,v2)(v0,v3

46、)30 v1 v2 v3 v4100(v0,v4)(v0,v3,v4)(v0,v3,v2,v4)例2：6001234 509070讨论：计算机如何自动求出这些最短路径？(v0,v1,v2,v4)60第56页/共74页Dijkstra（迪杰斯特拉）算法（迪杰斯特拉）算法算法思想：先找出从源点v0到各终点vk的直达路径（v0,vk），即通过一条弧到达的路径。从这些路径中找出一条长度最短的路径（v0,u）,然后对其余各条路径进行适当调整：若在图中存在弧（u,vk），且（v0,u）+（u,vk）（v0,vk）,则以路径（v0,u,vk）代替（v0,vk）。在调整后的各条路径中，再找长度最短的路径，依此

47、类推。总之，按路径“长度”递增的次序来逐步产生最短路径第57页/共74页算法描述：（1）设Ann为有向网的带权邻接矩阵，Aij表示弧（vi，vj)的权值，S为已找到从源点v0出发的最短路径的终点集合，它的初始状态为 v0.辅助数组distn为各终点当前找到的最短路径的长度，它的初始值为：distiAv0,i/即邻接矩阵中第v0行的权值（2）选择u，使得 distumindistw|wV-S /w是S集之外的顶点 /distu是从源点v0到S集外所有顶点的弧中最短的一条 S=S u /将u加入S集（3）对于所有不在S中的终点w，若 distu+Au,w distw /即(v0,u)(u,w)(v

48、0,w)则修改distw为：distw distu+Au,w（4）重复操作（2）、（3）共n-1次，由此求得从v0到各终点的最短路径。第58页/共74页(v0,v2)+(v2,v3)(v0,v3)终终点点 从从v0到各终点的到各终点的dist值和最短路径值和最短路径v1v2v3v4v5vjS之外的当前最短路径之顶点60v0,v2,v350v0,v4,v330v0,v490v0,v4,v560v0,v4,v3,v55540312100603010102050sv0,v2v0,v2,v4v0,v2,v4,v3 v0,v2,v4,v3,v510v0,v2 30v0,v4100v0,v5例3：v2v4

49、v3v5100v0,v5012345distwdistw0 1 2 3 4 5与最小生成树的不同点：路径可能是累加的！10v0,v250v0,v4,v330v0,v4第59页/共74页二、二、所有顶点之间的所有顶点之间的最短路径最短路径问题的提出：问题的提出：已知一个各边权值均大于已知一个各边权值均大于0 0的带权的带权有向图，对每一对顶点有向图，对每一对顶点 vi vj，希望求出希望求出vi 与与vj之间的最短路径和最短路径长度。之间的最短路径和最短路径长度。解决思路：解决思路：可以通过可以通过调用调用n n次次Dijkstra算法算法来完成，但时间来完成，但时间复杂度为复杂度为O(n3)。

50、改进：改进：Floyd算法（略）算法（略）第60页/共74页7.5 图的应用图的应用1.拓扑排序2.求关键路径第61页/共74页 AOE网(Activity On Edges)用边表示活动的网络AOE网定义：如果在无环的带权有向图中，用有向边表示一个工程中的活动，用边上权值表示活动持续时间，用顶点表示事件，则这样的有向图叫做用边表示活动的网络，简称 AOE。有两种常用的活动网络（Activity Network）：AOV网(Activity On Vertices)用顶点表示活动的网络AOV网定义：若用有向图表示一个工程，在图中用顶点表示活动，用弧表示活动间的优先关系。Vi 必须先于活动Vj