1、数据结构数据结构返回主目录返回主目录q学习目标学习目标v领会图的类型定义。领会图的类型定义。v熟悉图的各种存储结构及其构造算法，了熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。解各种存储结构的特点及其选用原则。v熟练掌握图的两种遍历算法。熟练掌握图的两种遍历算法。v理解各种图的应用问题的算法。理解各种图的应用问题的算法。本章说明本章说明q重点和难点重点和难点v图的应用极为广泛，而且图的各种应用问图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。理解各种图的算法及其应用场合。q知识点知
2、识点v图的类型定义、图的存储表示、图的图的类型定义、图的存储表示、图的深度深度优先搜索优先搜索遍历和图的遍历和图的广度优先搜索广度优先搜索遍历、遍历、无向网的无向网的最小生成树最小生成树、最短路径、最短路径、拓扑排拓扑排序序、关键路径、关键路径 本章说明本章说明7.1 图的定义和术语图的定义和术语 图图(Graph)图图G是由两个集合是由两个集合V和和VR组成组成的，记为的，记为G=(V,VR)其中：其中：V是是顶点顶点的有穷非空有限集的有穷非空有限集 VR是是两个顶点之间关系的两个顶点之间关系的有限集合，有限集合，即边集合，边是顶点的即边集合，边是顶点的无序对无序对或或有序对有序对 有向图有
3、向图有向图有向图G是由两个集合是由两个集合V和和VR组成组成的的 其中：其中：V是顶点的是顶点的有穷有穷非空有限集非空有限集 VR是是有向边有向边（也称（也称弧弧）的有限集合，）的有限集合，弧是弧是顶点的有序对顶点的有序对，记为，记为，v,w是是顶点，顶点，v为弧尾，为弧尾，w为弧头为弧头7.1 图的定义和术语图的定义和术语例如例如:G1=(V1,VR1)其中其中V1=1,2,3,4VR1=,有向图有向图G124137.1 图的定义和术语图的定义和术语 无向图无向图由顶点集和边集构成的图。由顶点集和边集构成的图。若若 VR 必有必有 VR,则称则称 (v,w)为顶点为顶点 v 和顶点和顶点 w
4、 之间存在一条之间存在一条边边。例如例如:G2=(V2,VR2)V2=A,B,C,D,E,FVR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)无向无向图图G2251437.1 图的定义和术语图的定义和术语 有向完全图有向完全图有有n个顶点，个顶点，n(n-1)弧的弧的有向图有向图 无向完全图无向完全图有有n个顶点，个顶点，n(n-1)/2条条边的边的无向图无向图例例有向完全图有向完全图无向完全图无向完全图1232317.1 图的定义和术语图的定义和术语 稀疏图稀疏图有很少条边和弧有很少条边和弧(enlogn)的图的图 稠密图稠密图与稀疏图相反与稀疏图相反
5、 权权与图的边或弧相关的数与图的边或弧相关的数 网网带权的图带权的图 有向网有向网弧带权的图弧带权的图 无向网无向网边带权的图边带权的图ABECF1597211132 子图子图如果图如果图G(V，E)和图和图G(V，E)，满足：，满足：V V 且且 E E，则称则称G 为为G的子图的子图 邻接点邻接点在无向在无向 图中一条边连起来图中一条边连起来 的两个顶点的两个顶点(v,v )，互称互称邻接点邻接点，称边，称边 (v,v )依附依附于顶点于顶点 v和和v 7.1 图的定义和术语图的定义和术语BBCAEFC7.1 图的定义和术语图的定义和术语ABECF顶点的顶点的度度(TD)=)=出度出度(O
6、D)+)+入度入度(ID)例如例如:ID(B)=2OD(B)=1TD(B)=3 顶点的度顶点的度 无向图中无向图中顶点的度顶点的度为与为与每个顶点相连的边数每个顶点相连的边数 有向图中有向图中顶点的度顶点的度为为:入度：以入度：以该顶点为头该顶点为头的弧的弧的数目的数目 出度：以出度：以该顶点为尾该顶点为尾的弧的弧的数目的数目7.1 图的定义和术语图的定义和术语 路径路径路径是一个顶点的序列路径是一个顶点的序列V=Vi,0,Vi,1,Vi,n，满足，满足(Vi,j-1,Vi,j)E 或或 E,(1j n)路径上边的数目称作路径上边的数目称作“路径长度路径长度”回路（环）回路（环）第一个顶点和最
7、后一个第一个顶点和最后一个顶点相同的路径顶点相同的路径 简单路径简单路径序列中序列中顶点不重复出现顶点不重复出现的的路径路径 简单回路简单回路除了第一个顶点和最后一除了第一个顶点和最后一个顶点外，个顶点外，其余顶点不重复出现其余顶点不重复出现的回路的回路7.1 图的定义和术语图的定义和术语连通连通从顶点从顶点V V到顶点到顶点W W有一条路有一条路径，则说径，则说V V和和W W是是连通的连通的连通图连通图图中图中任意个顶点都是任意个顶点都是连通的连通的例例G1G1245136路径：路径：1 1，2 2，3 3，5 5，6 6，3 3路径长度：路径长度：5 5简单路径：简单路径：1 1，2 2
8、，3 3，5 5回路：回路：1 1，2 2，3 3，5 5，6 6，3 3，1 1简单回路：简单回路：3 3，5 5，6 6，3 3例例连通图连通图245136连通分量连通分量指的是无向图中的极大连通子指的是无向图中的极大连通子图图强连通图强连通图有向图中，如果对每一对有向图中，如果对每一对V Vi i,V,Vj j V V,V Vi i V Vj j,从从V Vi i到到V Vj j 和从和从V Vj j到到 V Vi i都存都存在路径在路径强连通分量强连通分量指的是有向图中的极大强连指的是有向图中的极大强连通子图通子图7.1 图的定义和术语图的定义和术语强连通图强连通图3 35 56 6例
9、例例例245136非连通图非连通图7.1 图的定义和术语图的定义和术语生成树生成树是连通图的一个是连通图的一个极小极小连通子图，连通子图，它含有图的它含有图的全部顶点全部顶点，但只有足以构成一棵，但只有足以构成一棵树的树的n-1n-1条边条边生成森林生成森林对非连通图，各个连通分量的对非连通图，各个连通分量的生成树的集合生成树的集合ABCDEFCDABEF一个有向图及其生成森一个有向图及其生成森林林7.2 图的存储结构图的存储结构 图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示 图的邻接表存储表示图的邻接表存储表示 有向图的十字链表存储表示有向图的十字链表存储表示 无向图的邻接多重表存储
10、表示无向图的邻接多重表存储表示7.2 图的存储结构图的存储结构 邻接矩阵邻接矩阵表示顶点间相联关系的矩阵表示顶点间相联关系的矩阵定义：设定义：设G=(V,E)是有是有n 1个顶点的图，个顶点的图，G的邻接矩阵的邻接矩阵A是具有以下性质的是具有以下性质的n阶方阵阶方阵，其它0E(G)v,v或)v,(v若1,jijijiA 图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示7.2 图的存储结构图的存储结构00110001011101010101010100001100000000110有向图有向图G1v2v4v1v3无向无向图图G2v2v5v1v4v37.2 图的存储结构图的存储结构特点：特点：
11、无向图无向图的邻接矩阵的邻接矩阵对称对称，可压缩存储；有，可压缩存储；有n个顶点个顶点的无向图需存储空间为的无向图需存储空间为n(n+1)/2有向图有向图邻接矩阵邻接矩阵不一定对称不一定对称；有；有n个顶点的有向图个顶点的有向图需存储空间为需存储空间为n无向图中顶点无向图中顶点Vi的度的度TD(Vi)是邻接矩阵是邻接矩阵A中第中第i行行元素之和元素之和有向图中有向图中:顶点顶点Vi的出度是的出度是A中第中第i行元素之和行元素之和顶点顶点Vi的入度是的入度是A中第中第i列元素之和列元素之和网的邻接矩阵可定义为：网的邻接矩阵可定义为：ijij,(v,v)v,vE(G),ijA i j，其它7.2
12、图的存储结构图的存储结构5735487214263816例例23753186421457.2 图的存储结构图的存储结构 邻接矩阵的优缺点邻接矩阵的优缺点 优点优点：容易实现图的创建、销毁、查找顶点容易实现图的创建、销毁、查找顶点v v和返和返回回v v的值操作。容易判定顶点间有无边（弧），容的值操作。容易判定顶点间有无边（弧），容易计算顶点的度（出度、入度）易计算顶点的度（出度、入度）缺点：缺点：所占空间只和顶点个数有关，和边数无关，所占空间只和顶点个数有关，和边数无关，在在边边数数较少较少时，空间时，空间浪费浪费较大较大 邻接矩阵的存储表示邻接矩阵的存储表示#define INFINITY
13、INT_MAX#define MAX_VERTEX_NUM 20typedef enum DG,DN,AG,AN GraphKind;/有向图，有向网，无向图，无向网有向图，有向网，无向图，无向网7.2 图的存储结构图的存储结构typedef struct ArcCell /邻接矩阵邻接矩阵 VRType adj;/顶点关系类型顶点关系类型 InfoType *info;/该弧相关信息的指针该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;/顶
14、点向量顶点向量 AdjMatrix arcs;/弧的信息弧的信息 int vexnum,arcnum;/顶点数和弧数顶点数和弧数 GraphKind kind;/图的种类图的种类MGraph;7.2 图的存储结构图的存储结构 建立无向图邻接矩阵的算法建立无向图邻接矩阵的算法 算法中：算法中：G.vexs，一维，顶点向量，一维，顶点向量 .arcs ，二维，邻接矩阵，二维，邻接矩阵 .vexnum，顶点数，顶点数 .arcnum，边数，边数7.2 图的存储结构图的存储结构 图的邻接表存储表示图的邻接表存储表示 邻接表邻接表是图的一种链式存储结构，为依附每是图的一种链式存储结构，为依附每个顶点的边
15、（或弧）建立一个单链表个顶点的边（或弧）建立一个单链表 顶点结构顶点结构 adjvexnextarcinfo表结点表结点datafirstarc头结点头结点顶点顶点位置位置下一下一条弧条弧相关相关信息信息顶点顶点数据数据第一第一条弧条弧V1V2 V3V40123V1V2V3V4V5012347.2 图的存储结构图的存储结构有向图有向图G12413无向无向图图G22514312 3 0 31 420 431 20 21 7.2 图的存储结构图的存储结构 图的图的邻接表邻接表存储表示存储表示#define MAX_VERTEX_NUM 20Typedef struct ArcNode /表结点表结
16、点 int Adjvex;/与与vi邻接的顶点的下标位置邻接的顶点的下标位置 struct ArcNode *nextarc;/与与vi邻接的下一个顶点邻接的下一个顶点 InfoType *info;/ArcNode;Typedef struct Vnode /头结点头结点 VertexType data;ArcNode *firstarc;Vnode,AdjListMAX_VERTEX_NUM;Typedef struct /图图 AdjList vertices;int vexnum,arcnum,kind;ALGraph;7.2 图的存储结构图的存储结构 邻接表是顶点的向量结构和边（弧）
17、的单链表结构邻接表是顶点的向量结构和边（弧）的单链表结构 每个顶点结点包括两个域，将每个顶点结点包括两个域，将n n个顶点放在一个向个顶点放在一个向量中（称为顺序存储的结点表）；一个顶点的所有邻量中（称为顺序存储的结点表）；一个顶点的所有邻接点链接成单链表，该顶点在向量中有一个指针域指接点链接成单链表，该顶点在向量中有一个指针域指向其第一个邻接点。向其第一个邻接点。邻接表的邻接表的优缺点优缺点 空间较省；空间较省；无向图无向图容易求容易求各顶点的各顶点的度度；表中结点个数是边的两倍；表中结点个数是边的两倍；有向图有向图容易求容易求顶点的顶点的出度出度；不容易求不容易求顶点的顶点的入度入度，要，
18、要遍历整个表。为了求顶点的入度，有时可设遍历整个表。为了求顶点的入度，有时可设逆邻接表逆邻接表（指向某顶点的邻接点链接成单链表）指向某顶点的邻接点链接成单链表）7.2 图的存储结构图的存储结构 建立邻接表的算法建立邻接表的算法 有向图有向图G12413V1V2V3V43 0 0 2 逆邻接表逆邻接表 第第i(i(下标下标i-1)i-1)链表的结点个数即为链表的结点个数即为ViVi顶点的入度。顶点的入度。7.2 图的存储结构图的存储结构 有向图的十字链表存储表示有向图的十字链表存储表示 十字链表结点结构十字链表结点结构tailvex headvex hlink tlink info弧结点弧结点d
19、ata firstin firstout顶点结点顶点结点弧尾弧尾位置位置弧头弧头位置位置弧尾相同的下弧尾相同的下一条弧指针一条弧指针弧相关信息弧相关信息的指针的指针弧头相同的弧头相同的下一条弧指下一条弧指针针指向该顶点指向该顶点第一条入弧第一条入弧指向该顶点指向该顶点第一条出弧第一条出弧7.2 图的存储结构图的存储结构例例v2v4v1v30 20 12 32 03 23 13 0 v1v2 v3v40123 7.2 图的存储结构图的存储结构 有向图十字链表存储表示有向图十字链表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcBox /弧结点弧结点
20、int tailvex,hesdvex;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;7.2 图的存储结构图的存储结构 建立有向图十字链表算法建立有向图十字链表算法 思想：思想：（1 1）初始化表头向量、数
21、据、指针）初始化表头向量、数据、指针 （2 2）输入一条弧，确定在）输入一条弧，确定在G G中位置，申请中位置，申请结点空间，赋值结点空间，赋值 （3 3）插入到十字链表中）插入到十字链表中 （4 4）若）若InInfoInInfo=1=1，输入其信息，输入其信息 （5 5）重复（）重复（2 2）至（）至（4 4），直到所有弧输），直到所有弧输入完为止。入完为止。7.2 图的存储结构图的存储结构 无向图的邻接多重表存储表示无向图的邻接多重表存储表示 邻接多重表结点结构邻接多重表结点结构mark ivex ilink jvexinfo边结点边结点jlinkdatafirstedge顶点结点顶点结
22、点i顶点顶点下一个依附下一个依附于于i顶点的边顶点的边j顶点顶点下一个依附下一个依附于于j顶点的边顶点的边第第1个依附于个依附于该顶点的边该顶点的边7.2 图的存储结构图的存储结构例例v1v2v4v5v30123v1v3v4v24v5 0 1 0 3 2 3 2 1 2 4 4 1 指向下一指向下一个依附于个依附于v1v1的边的边指向下一指向下一个依附于个依附于v2v2的边的边7.2 图的存储结构图的存储结构 无向图邻接多重表存储表示无向图邻接多重表存储表示#define MAX_VERTEX_NUM 20Typedef emnu unvisited,visited VisitIf;typed
23、ef struct ArcBox /弧结点弧结点 VisitIf mark;int ivex,jvex;struct EBox *ilink,*jlink;infoType *info;EBox;Typedef struct VexBox /顶点结点顶点结点 VertexType data;EBox *firstedge;/指向第指向第1条依附该顶点的边条依附该顶点的边VexBox;Typedef struct /顶点表顶点表 VexBox adjlistMAX_VERTEX_NUM;int vexnum,arcnum;AMLGraph;7.3 图的遍历图的遍历 从图的某顶点出发，对图中的每个
24、从图的某顶点出发，对图中的每个顶点进行一次访问且使每个顶点仅被访顶点进行一次访问且使每个顶点仅被访问一次的过程。问一次的过程。深度优先遍历深度优先遍历广度优先遍历广度优先遍历7.3 图的遍历图的遍历思想：思想：（1 1）从图的某一顶点）从图的某一顶点V0V0出发，访出发，访问该顶点；然后依次从问该顶点；然后依次从V0V0的的未被访问的未被访问的邻接邻接点出发，深度优先遍历图，直至图点出发，深度优先遍历图，直至图中所有和中所有和V0V0相通的顶点都被访问到；相通的顶点都被访问到；（2 2）若此时图中尚有顶点未被访若此时图中尚有顶点未被访问，则另选图中一个问，则另选图中一个未被访问的顶点未被访问的
25、顶点作作起点，重复上述过程，直至图中起点，重复上述过程，直至图中所有顶所有顶点点都被访问为止都被访问为止 深度优先遍历深度优先遍历7.3 图的遍历图的遍历V1V2V4V5V3V7V6V8例例1深度遍历：深度遍历：V1V1 V2 V2 V4 V4 V8 V8 V5 V5 V3 V3 V6 V6 V7V7V1V2V4V5V3V7V6V87.3 图的遍历图的遍历例例2V1V2V4V5V3V7V6V8例例3V1V2V4V5V3V7V6V8例例2：V1 V2 V4 V8 V5 V6 V3 V7例例3：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例例4例例4：V1 V2
26、V4 V8 V3 V6 V7 V57.3 图的遍历图的遍历从上面例可见从上面例可见:1.从深度优先搜索遍历连通图的过从深度优先搜索遍历连通图的过程类似于树的先根遍历程类似于树的先根遍历;解决的办法是解决的办法是:为每个顶点设立一个为每个顶点设立一个“访问标志访问标志 visitedw”;2.如何判别如何判别V的邻接点是否被访问？的邻接点是否被访问？7.3 图的遍历图的遍历开始开始访问标志初始化访问标志初始化i=1Vi访问过访问过DFSi=i+1i=Vexnums结束结束NNYY 深度优先遍历算法深度优先遍历算法开始开始访问访问V,置置标志标志求求V邻接点邻接点有邻接点有邻接点w求下一邻接点求下
27、一邻接点W访问过访问过结束结束NYNYDFSwV07.3 图的遍历图的遍历abchdekfg812345670F F F F F F F F F0 1 2 3 4 5 6 7 8T T T T T T T T Tach d kfe bgachkfedbg访问标志访问标志:访问次序访问次序:例如例如:achdkfe7.3 图的遍历图的遍历 广度优先搜索广度优先搜索思想思想 （1）从图的某一顶点）从图的某一顶点V0出发，访问出发，访问该顶点后，依次访问该顶点后，依次访问V0的各个的各个未被访问过未被访问过的邻接点；然后分别从这些邻接点出发，的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图
28、中所有已被访问广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到的顶点的邻接点都被访问到 （2）若此时图中尚有顶点未被访问，若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访重复上述过程，直至图中所有顶点都被访问为止问为止7.3 图的遍历图的遍历V1V2V4V5V3V7V6V8例例1广度遍历：广度遍历：V1V1 V2 V2 V3 V3 V4 V4 V5 V5 V6 V6 V7 V7 V8V8V1V4V5V3V7V8V2V67.3 图的遍历图的遍历例例2V1V2V4V5V3V7V6V8例例3V1V2V
29、4V5V3V7V6V8例例2：V1 V2 V3 V4 V5 V6 V7 V8例例3：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例例4例例4：V1 V2 V3 V4 V6 V7 V8 V57.3 图的遍历图的遍历 广度优先遍历算法广度优先遍历算法 思想：借助队列思想：借助队列开始开始标志数组初始化标志数组初始化Vi=1Vi=1ViVi访问过访问过BFSBFSVi=Vi+1Vi=Vi+1Vi=VexnumsVi=Vexnums结束结束N NN NY YY Y7.3 图的遍历图的遍历开始开始访问访问V0,置置标志标志求求V邻接点邻接点ww存在吗存在吗V下一邻接点下
30、一邻接点ww访问过访问过结束结束NYNYBFS初始化队列初始化队列V0入队入队队列空吗队列空吗队头队头V出队出队访问访问w,置置标志标志w入队入队NY7.4 生成树生成树生成树生成树最小生成树最小生成树构造最小生成树构造最小生成树7.4 生成树生成树 生成树生成树 定义：所有（定义：所有（n n个）顶点均由边（个）顶点均由边（n-1n-1个）连接在一起，但不存在回路的图个）连接在一起，但不存在回路的图 深度优先生成树：由深度优先遍历得深度优先生成树：由深度优先遍历得到的生成树到的生成树 广度优先生成树：由广度优先遍历得广度优先生成树：由广度优先遍历得到的生成树到的生成树 生成森林：非连通图每个
31、连通分量的生成森林：非连通图每个连通分量的生成树一起组成非连通图生成树一起组成非连通图7.4 生成树生成树 说明说明 一个图可以有许多棵不同的生成树一个图可以有许多棵不同的生成树 所有生成树具有以下共同特点：所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图生成树是图的极小连通子图一个有一个有n n个顶点的连通图的生成树有个顶点的连通图的生成树有n-1n-1条边条边生成树中任意两个顶点间的路径是唯一生成树中任意两个顶点间的路径是唯一的的在生成树中再加一条边必然形成回路在生成树中再加一条边必然形成回路 含含n n个顶点个顶点n
32、-1n-1条边的图不一定是生成树条边的图不一定是生成树7.4 生成树生成树V5V1V2V4V3V7V6V8例例深度：深度：V1 V2 V4 V8 V5V3 V6 V7V1V2V4V5V3V7V6V8深度优先生成树深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树广度优先生成树广度：广度：V1 V2 V3 V4 V5V6 V7 V8V5V1V2V4V3V7V6V8V5V1V2V4V3V7V6V87.4 生成树生成树例例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林深度优先生成森林7.4 生成树生成树 最小生成树最小生成树问题提出问题提出 假设要在假设要在 n 个城
33、市之间建立通讯联络网，个城市之间建立通讯联络网，则连通则连通 n 个城市只需要修建个城市只需要修建 n-1条线路，条线路，如何如何在最节省经费的前提下建立在最节省经费的前提下建立这个这个通讯网通讯网？顶点顶点表示城市表示城市权权城市间建立通信线路所需花费代价城市间建立通信线路所需花费代价 最小（代价）生成树最小（代价）生成树：希望找到一棵生成树，：希望找到一棵生成树，它的每条边上的权值之和即建立该通信网所需它的每条边上的权值之和即建立该通信网所需花费的总代价）最小花费的总代价）最小7.4 生成树生成树 问题分析问题分析 n n个城市间，最多可设置个城市间，最多可设置n(n-1)/2n(n-1)
34、/2条线路条线路 n n个城市间建立通信网，只需个城市间建立通信网，只需n-1n-1条线路条线路 该问题等价于该问题等价于：构造网的一棵：构造网的一棵最小生成树最小生成树，即：，即：在在e e条带权的边中选取条带权的边中选取n-1n-1条边条边（不构成回路），（不构成回路），使使“权值之和权值之和”为最小为最小。16543271317918127524107.4 生成树生成树 构造最小生成树方法构造最小生成树方法方法一：普里姆方法一：普里姆(Prim)(Prim)算法（选点法）算法（选点法）思想：设思想：设N=(V,E)N=(V,E)是连通网，是连通网，TETE是是N N上最小生上最小生成树中
35、边的集合成树中边的集合（1）初始令初始令U=u0,(u0 V),TE=（2）在所有）在所有u U,v V-U的边的边(u,v)E中，找一中，找一条代价最小的边条代价最小的边(u0,v0)（3）将）将(u0,v0)并入集合并入集合TE，同时，同时v0并入并入U（4）重复上述操作直至）重复上述操作直至U=V为止，则为止，则 T=(V,TE)为为N的最小生成树的最小生成树树存储结构：树存储结构：邻接矩阵表示邻接矩阵表示算法实现算法实现算法评价：算法评价：O(n)7.4 生成树生成树例例16543265135664255352461314211316131446131425246131427.4 生成
36、树生成树方法二：克鲁斯卡尔方法二：克鲁斯卡尔算法（选边法）算法（选边法）思想：设思想：设N=(V,E)N=(V,E)是连通网，是连通网，TETE是是N N上最上最小生成树中边的集合小生成树中边的集合（1）初始状态为只有）初始状态为只有n个顶点而无边的个顶点而无边的非连通图非连通图T=(V,)，每个顶点自成一个，每个顶点自成一个连通分连通分（2）在）在E中选取代价最小的边，若该边中选取代价最小的边，若该边依附的顶点落在依附的顶点落在T中不同的连通分量上，中不同的连通分量上，则将此边加入到则将此边加入到T中；否则，舍去此边，中；否则，舍去此边，选取下一条代价最小的边选取下一条代价最小的边（3）依此
37、类推，直至依此类推，直至T中所有顶点都在中所有顶点都在同一连通分量上为止同一连通分量上为止7.4 生成树生成树例例165432651356642516543265135664257.4 生成树生成树 算法描述：算法描述：构造非连通图构造非连通图 ST=(V,);k=i=0;/k 计选中的边数计选中的边数 while(kn-1)+i;检查边集检查边集 E 中第中第 i 条权值最小的边条权值最小的边(u,v);若若(u,v)加入加入ST后不使后不使ST中产生回路中产生回路，则则 输出边输出边(u,v);且且 k+;7.4 生成树生成树普里姆算法普里姆算法 克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间
38、复杂度O(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名算法名适应范围适应范围比较两种算法7.5 拓扑排序拓扑排序有向无环图有向无环图拓扑排序拓扑排序关键路径关键路径7.5 拓扑排序拓扑排序 有向无环图：一个无环的有向图有向无环图：一个无环的有向图（DAG）是描述一项工程或系统的进行过程的有效是描述一项工程或系统的进行过程的有效工具。工具。7.5 拓扑排序拓扑排序问题提出：学生选修课程问题问题提出：学生选修课程问题顶点顶点表示课程表示课程有向弧有向弧表示先决条件，若课程表示先决条件，若课程i i是课程是课程j j的先决的先决条件，则图中有弧条件，则图中有弧 i,j学生应按怎样的顺序学习这
39、些课程，才能无矛盾、学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业顺利地完成学业拓扑排序拓扑排序定义定义AOVAOV网网用用顶点顶点表示表示活动活动，用，用弧弧表示表示活动间优先活动间优先关系关系的有向图称为顶点表示活动的网的有向图称为顶点表示活动的网(Activity On(Activity On Vertex network)Vertex network)，简称，简称AOVAOV网网若若 是图中有向边，则是图中有向边，则vivi是是vjvj的直接前驱；的直接前驱；vjvj是是vivi的直接后继的直接后继AOVAOV网中网中不允许有回路不允许有回路，这意味着某项活动以自己为先决，
40、这意味着某项活动以自己为先决条件条件7.5 拓扑排序拓扑排序拓扑排序拓扑排序把把AOVAOV网络中各顶点网络中各顶点按照按照它们它们相互相互之间的优先关系之间的优先关系排列成一个线性序列的过程排列成一个线性序列的过程检测检测AOVAOV网中是否存在环方法：对有向图构造其顶点网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若的拓扑有序序列，若网中所有顶点网中所有顶点都在它的拓扑有序都在它的拓扑有序序列中，则该序列中，则该AOVAOV网必定不存在环网必定不存在环拓扑排序的方法拓扑排序的方法在有向图中选一个在有向图中选一个没有前驱没有前驱的顶点且输出之的顶点且输出之从图中从图中删除删除该顶点和
41、所有该顶点和所有以它为尾的弧以它为尾的弧重复上述两步，直至全部顶点均已输出；或者当重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止图中不存在无前驱的顶点为止7.5 拓扑排序拓扑排序C1C2C3C4C5C6C7C8C9C10C11C12无无C1C1,C2C1C3,C4C11C3.C5C3,C6无无C9C9C1,C9,C10程序设计基础程序设计基础离散数学离散数学数据结构数据结构汇编语言汇编语言语言的设计和分析语言的设计和分析计算机原理计算机原理编译原理编译原理操作系统操作系统高等数学高等数学线性代数线性代数普通物理普通物理数值分析数值分析课程代号课程代号 课程名称课程名称 先
42、修课先修课C1C2C3C4C5C6C7C8C9C10C11C12例例7.5 拓扑排序拓扑排序C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8一个一个AOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的7.5 拓扑排序拓扑排序C1C2C3C4C5C6C7C8C9C10C11C12C3C4C5C6C7C8C9C10C11C127.5 拓扑排序拓扑排序C2C3C4C5C6C7C8C9C10C11C127.5 拓扑排序拓
43、扑排序C4C5C6C7C8C9C10C11C12C5C6C7C8C9C10C11C12C6C8C9C10C11C127.5 拓扑排序拓扑排序C6C7C8C9C10C11C12C6C8C10C11C12C6C8C11C127.5 拓扑排序拓扑排序C6C8C12C8C12C87.5 拓扑排序拓扑排序 算法实现算法实现 以邻接表作存储结构以邻接表作存储结构 把邻接表中所有入度为把邻接表中所有入度为0的顶点进栈的顶点进栈 栈非空时，输出栈顶元素栈非空时，输出栈顶元素Vj并退栈；在邻并退栈；在邻接表中查找接表中查找Vj的直接后继的直接后继Vk，把，把Vk的入度的入度减减1；若；若Vk的的入度为入度为0则
44、进栈则进栈 重复上述操作直至栈空为止。若栈空时输重复上述操作直至栈空为止。若栈空时输出的顶点个数不是出的顶点个数不是n，则有向图有环；否则，则有向图有环；否则，拓扑排序完毕拓扑排序完毕 5 5 4 3 2 5 2 40122inlinkvex next301234567.5 拓扑排序拓扑排序32104例例123456top16toptop 算法描述算法描述入度入度7.5 拓扑排序拓扑排序 5 5 4 3 2 5 2 40122inlinkvex next30123456输出序列：输出序列：63210416toptop7.5 拓扑排序拓扑排序输出序列：输出序列：6321041topp 5 5 4
45、 3 2 5 2 40122inlinkvex next301234567.5 拓扑排序拓扑排序0122inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6321041topp7.5 拓扑排序拓扑排序0122inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6321041topp7.5 拓扑排序拓扑排序0112inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6321041topp7.5 拓扑排序拓扑排序0112inlink 5 5 4 3vex next2
46、 2 5 2 40123456输出序列：输出序列：6321041topp=NULL7.5 拓扑排序拓扑排序0112inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6 1321041toptop7.5 拓扑排序拓扑排序0112inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6 132104topp7.5 拓扑排序拓扑排序0102inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6 132104topp47.5 拓扑排序拓扑排序0102inlink 5 5
47、4 3vex next2 2 5 2 40123456输出序列：输出序列：6 132104p4top7.5 拓扑排序拓扑排序0102inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6 132104p4top7.5 拓扑排序拓扑排序0002inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6 132104p4top37.5 拓扑排序拓扑排序0002inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6 132104p4top37.5 拓扑排序拓扑排序0002i
48、nlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6 132104p4top37.5 拓扑排序拓扑排序0001inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6 132104p4top37.5 拓扑排序拓扑排序0001inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6 132104p=NULL4top37.5 拓扑排序拓扑排序0001inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6 1 3321044top
49、37.5 拓扑排序拓扑排序0001inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：输出序列：6 1 3321044topp7.5 拓扑排序拓扑排序0001inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：输出序列：6 1 3321044topp7.5 拓扑排序拓扑排序0001inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：输出序列：6 1 3321044topp7.5 拓扑排序拓扑排序0000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：输出序
50、列：6 1 3321044topp27.5 拓扑排序拓扑排序0000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：输出序列：6 1 3321044topp27.5 拓扑排序拓扑排序0000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：输出序列：6 1 3321044top2p=NULL7.5 拓扑排序拓扑排序0000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：输出序列：6 1 3 2321044top2p=NULL7.5 拓扑排序拓扑排序0000inlink 5 5 4 3
