1、上页上页 下页下页节节末页末页结束结束第七章第七章 图图图的定义和术语图的定义和术语图的存储结构图的存储结构图的基本操作图的基本操作-遍历遍历应用应用最小生成树最小生成树 拓扑排序拓扑排序 关键路径关键路径 最短路最短路上页上页 下页下页节节末页末页结束结束7.17.1图的定义和图的定义和术语术语l线性表、树和图：从关系、结构两个角度区分线性表、树和图：从关系、结构两个角度区分 AB E C D B CA D F El图图Graph;顶点顶点Vertex;序偶序偶;弧弧Arc;弧头弧头B/弧尾弧尾AlDigraph;Undigraph;无序对无序对(A,B):;Edgel网网NetWork:弧
2、或边含权的图弧或边含权的图,分分有向网有向网DN、无向网无向网UDNl(无向无向)完全图完全图:边数最大的无向简单图边数最大的无向简单图,满足满足e=n*(n-1)/2l有向完全图有向完全图:弧数最大的有向简单图弧数最大的有向简单图,e=n*(n-1)l稀疏图稀疏图(如如enlogn)稠密图稠密图ABECF1597211132上页上页 下页下页节节末页末页结束结束BECBBC子图Subgraph 邻接点:无向图如A与B互为邻接点,有向图如A邻接到B无向图顶点的度,如TD(A)=2；有向图分入/出度,度为两者之和 ID(A)=1,OD(A)=2,TD(A)=3路径、简单路径、回路(环)、路径长度
3、术语术语 B CA D F EABECF上页上页 下页下页节节末页末页结束结束若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图。连通图。如能找到一条含全部顶点如能找到一条含全部顶点的路径则说明是连通图的路径则说明是连通图无向图中的极大连通子图称作此图的连通分量。连通分量。极大指顶点尽量多,顶点连同其关联的边构成连通分量.图本身连通则连通分量唯一,是自身BACDFEBACDFE连通图连通图,连通分量连通分量(无向图)上页上页 下页下页节节末页末页结束结束若任意两顶点间都存在一条有向路径，则称此有向图为强连通图强连通图。ABECFABECF有向图的极大强连通子图称作它的强连通分量强连通分
4、量。强连通图、强连通分量强连通图、强连通分量(有向图)上页上页 下页下页节节末页末页结束结束连通图的一个含有全部顶点的子图,如果连通且极小极小，则它必是一颗树(边数为n-1)，称该树为原连通图的生成树。破圈法可得生成树 对非连通图，由各个连通分量的生成树组成的集合称为此非连通图的生成森林生成森林。BACDFE生成树与生成森林（无向图）生成树与生成森林（无向图）注注:树是含边数最小的连通图树是含边数最小的连通图(n-1);(n-1);图中图中若边少于若边少于n-1n-1则必不连通；若图连通则至则必不连通；若图连通则至少含少含n-1n-1条边；若图中多于条边；若图中多于n-1n-1条边则必然条边则
5、必然含有回路。含含有回路。含n-1n-1条边的连通图必然是树条边的连通图必然是树上页上页 下页下页节节末页末页结束结束ADT Graph 数据对象数据对象V：若干顶点组成的集合：若干顶点组成的集合 数据关系数据关系R：R=VR VR|v,wV 且 表示从 v 到 w 有一条弧，可代表v认识w 或 v到w有路等)基本操作基本操作 图的抽象数据类型定义图的抽象数据类型定义逻辑结构逻辑结构上页上页 下页下页节节末页末页结束结束CreatGraph(&G,V,VR);CreatGraph(&G,V,VR);/按定义(V,VR)构造图GDestroyGraph(&G);DestroyGraph(&G);
6、/销毁图G结构的建立和销毁结构的建立和销毁上页上页 下页下页节节末页末页结束结束插入或删除顶点、弧插入或删除顶点、弧InsertVex(&G,v);/在图在图G G中增添新顶点中增添新顶点v v。DeleteVex(&G,v);/删除删除G G中顶点中顶点v v及其相关的弧。及其相关的弧。InsertArc(&G,v,w);/在在G G中增添弧中增添弧，若，若G G是无是无向的，则还增添对称弧向的，则还增添对称弧DeleteArc(&G,v,w);/在在G G中删除弧中删除弧，若，若G G是无是无向的，则还删除对称弧向的，则还删除对称弧上页上页 下页下页节节末页末页结束结束遍遍 历历DFSTr
7、averse(G,v,Visit();/从顶点v起深度优先深度优先遍历图G,对每个顶点执行一次VisitBFSTraverse(G,v,Visit();/从v起广度优先广度优先遍历图G，每个顶点调用一次函数Visit规则规则:访问起始顶点访问起始顶点v,v,然后选取与然后选取与v v邻接的未访问的第一个顶点邻接的未访问的第一个顶点w,w,访问之，再选取与访问之，再选取与w w邻接的未访问的第一个顶点，访问之。重复进邻接的未访问的第一个顶点，访问之。重复进行至当前节点的所有邻接点都被访问过，此时后退到最近访问过行至当前节点的所有邻接点都被访问过，此时后退到最近访问过的定点，找其下一个未访问的邻接
8、点访问，依次类推。如的定点，找其下一个未访问的邻接点访问，依次类推。如ABE ABE FCD FCD H H说明说明:一次可遍历所有与一次可遍历所有与v v连通的顶点。若尚有顶点未访问连通的顶点。若尚有顶点未访问(非连通非连通图图),),则从其开始重复上述过程则从其开始重复上述过程.对应树的先根遍历。可得深度优先对应树的先根遍历。可得深度优先生成树或森林以及连通分量生成树或森林以及连通分量递归描述递归描述：访问：访问v,v,逐个从逐个从v v未访问的邻接点出发递归遍历未访问的邻接点出发递归遍历.规则规则:访问访问v,v,访问访问v v的全部未访问的邻接点的全部未访问的邻接点,再逐个从这些邻接点
9、出再逐个从这些邻接点出发重复发重复.一次可遍历所有与一次可遍历所有与v v连通的顶点连通的顶点,若尚有顶点未访问则从其若尚有顶点未访问则从其开始重复开始上述过程开始重复开始上述过程.如如ABEHFCDABEHFCD对应树层序遍历对应树层序遍历,可得广度优先生成树可得广度优先生成树/森林森林,可得连通分量可得连通分量,实现实现?B CA D F EH上页上页 下页下页节节末页末页结束结束对顶点的访问操作对顶点的访问操作LocateVex(G,u);/若G中存在顶点与u”相等”，则返回该顶点在图中“位置位置”(下标或指针)GetVex(G,v);/返回G中顶点v的值。PutVex(&G,v,val
10、ue);/为G中顶点v赋值value。上页上页 下页下页节节末页末页结束结束对邻接点的操作对邻接点的操作FirstAdjVex(G,v);/返回返回G G中顶点中顶点v v的的“第一个邻接点第一个邻接点”。若该顶点。若该顶点/在在 G G 中没有邻接点，则返回中没有邻接点，则返回“空空”。NextAdjVex(G,v,w);/w/w是是v v的一个邻接点的一个邻接点,返回返回v v的的“下一个邻接点下一个邻接点”。/若若w w是是v v的最后一个邻接点，则返回的最后一个邻接点，则返回“-1”-1”。上页上页 下页下页节节末页末页结束结束图的图的数组数组表示表示(p161)(邻接矩阵邻接矩阵)图
11、的图的邻接表邻接表表示表示(p163)有向图的有向图的十字链表十字链表表示表示(p164)无向图的无向图的邻接多重表邻接多重表表示表示(p166)7.2 7.2 图的存储结构图的存储结构上页上页 下页下页节节末页末页结束结束BACDFE邻接矩阵邻接矩阵:行、列各对应一个顶点行、列各对应一个顶点,若第若第i i行对应的顶点到行对应的顶点到第第j j列对应的顶点有弧相连则列对应的顶点有弧相连则Aij=1,Aij=1,否则为否则为0 0。n n*n n阶阶 A B C D E F ABCDEF1 1、图的数组表示、图的数组表示-邻接矩阵邻接矩阵adjacency matrixadjacency ma
12、trix上页上页 下页下页节节末页末页结束结束0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 ABECD无向图的邻接矩阵必为对称阵网的邻接矩阵Aij=wAij=wijij或或上页上页 下页下页节节末页末页结束结束 A B C D E FABCDEF/-图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示-typedef char VertexType;#define INFINITY 10000 /最大值最大值#define MAX_VERTEX_NUM 20 /最大顶点个数最大顶点个数typedef enumDG,DN,UDG,UDN Gr
13、aphKind;/图类型图类型 typedef struct ArcCell /弧的定义弧的定义 VRType adj;/邻接数邻接数,0/1或或w/。VRTypeVRType为为int/doubleint/double InfoType *info;/弧的附加信息数组弧的附加信息数组ArcCell,ArcCell,AdjMatrixAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;MAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图的定义图的定义 VertexType vexsMAX_VERTEX_NUM;/顶点信息顶点信息
14、AdjMatrix arcs;/邻接矩阵邻接矩阵,存储弧信息存储弧信息,静态数组静态数组 int vexnum,arcnum;/顶点数，弧数顶点数，弧数 GraphKind kind;/图的类型标记图的类型标记 MGraph;/矩阵图矩阵图上页上页 下页下页节节末页末页结束结束Status CreateGraph(Mgraph&G)/输入图的种类及顶点和边信息构造图输入图的种类及顶点和边信息构造图G(邻接矩阵表示邻接矩阵表示)scanf(“%d”,&G.kind);/枚举值枚举值DG,DN实输入实输入0 1 switch(G.kind)case DG:return CreateDG(G);ca
15、se DN:return CreateDN(G);case UDG:return CreateUDG(G);case UDN:return CreateUDN(G);default:return ERROR;图的创建图的创建上页上页 下页下页节节末页末页结束结束Status CreateUDN(Mgraph&G)/建立无向网建立无向网G 输入输入G.vexnum,G.arcnum,IncInfo;/IncInfo为为0 0表各弧无附加信息表各弧无附加信息 for(i=0;i G.vexnum;+i)scanf(“%c”,G.vexsi);for(i=0;i G.vexnum;+i)for(j=
16、0;jvexnum;+j)G.arcsij=INFNITY,NULL;/各弧初始化各弧初始化 for(k=0;k G.arcnum;+k)scanf(“%c%c%lf”,&v1,&v2,&w);/输入一条输入一条“边边”及其权及其权值值 i=LocateVex(G,v1);j=LocateVex(G,v2);/确定顶点下标确定顶点下标 G.arcsij.adj=w;if(IncInfo)输入输入G.arcsij.info;G.arcsji=G.arcsij;/无向网需将对称弧加入无向网需将对称弧加入 /ENDABECF1597211132上页上页 下页下页节节末页末页结束结束BACDFE AB
17、CDEF邻接矩阵优缺点：邻接矩阵优缺点：易于求顶点度易于求顶点度(区分有区分有/无向图无向图)、求邻接点，易判断两点间是否有、求邻接点，易判断两点间是否有弧或边相连弧或边相连,但不利于稀疏图的存储，因弧不存在时也要存储相应但不利于稀疏图的存储，因弧不存在时也要存储相应信息，且要预先分配足够大空间信息，且要预先分配足够大空间上页上页 下页下页节节末页末页结束结束小结：小结：u掌握图的概念和基本术语掌握图的概念和基本术语u掌握图的掌握图的邻接矩阵存邻接矩阵存储，理解优缺点储，理解优缺点u掌握图的掌握图的深度优先遍历和广度优先遍历的深度优先遍历和广度优先遍历的规则规则u会通过遍历求图的连通分量和深度
18、优先、会通过遍历求图的连通分量和深度优先、广度优先生成树、生成森林广度优先生成树、生成森林u作业：作业：1 5 B CA D F EH上页上页 下页下页节节末页末页结束结束 A B C D E FABCDEF/-图的数组图的数组(邻接矩阵邻接矩阵)存储表示存储表示-typedef char VertexType;#define INFINITY 10000 /最大值最大值#define MAX_VERTEX_NUM 20 /最大顶点个数最大顶点个数typedef enumDG,DN,UDG,UDN GraphKind;/图类型图类型 typedef struct ArcCell /弧的定义弧的
19、定义 VRType adj;/邻接数邻接数,0/1或或w/。VRTypeVRType为为int/doubleint/double InfoType *info;/弧的附加信息数组弧的附加信息数组ArcCell,ArcCell,AdjMatrixAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;MAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图的定义图的定义 VertexType vexsMAX_VERTEX_NUM;/顶点信息顶点信息 AdjMatrix arcs;/邻接矩阵邻接矩阵,存储弧信息存储弧信息,静态数组静态数组 i
20、nt vexnum,arcnum;/顶点数，弧数顶点数，弧数 GraphKind kind;/图的类型标记图的类型标记 MGraph;/矩阵图矩阵图上页上页 下页下页节节末页末页结束结束0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3 BACDFE顶点数组(头结点)邻接点链表无向图中每条边出现两次无向图中每条边出现两次,n,n个个顶点顶点e e条边需条边需n n个头结点和个头结点和2e2e个个表结点表结点2 2、邻接表存储表示、邻接表存储表示上页上页 下页下页节节末页末页结束结束1 4230 120 1 2 3 4 A B C D E邻接表举例邻接表
21、举例ABECDtypedef struct ArcNode int adjvex;struct ArcNode*nextarc;InfoType *info;ArcNode;data firstarcadjvex nextarc infotypedef struct VNode VertexType data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;GraphKind kind;ALGraph;/邻接表图上页上页 下页下页节节末页末页结束结束S
22、tatus CreateGraph(ALGraph&G)/建立图的邻接表的结构建立图的邻接表的结构 scanf(“%d”,&G.kind);switch(G.kind)case DG:return CreateDG(G);case DN:return CreateDN(G);case UDG:return CreateUDG(G);case UDN:return CreateUDN(G);default:return ERROR;邻接表图的创建邻接表图的创建【补充补充】上页上页 下页下页节节末页末页结束结束Status CreateDN(ALGraph&G)/建立有向网建立有向网 scanf(
23、“%d%d%d”,&G.vexnum,&G.arcnum,&IncInfo);for(i=0;i G.vexnum;+i)scanf(G.verticesi.data);G.verticesi.firstarc=NULL;for(k=0;kadjvex=j;if(IncInf)输入输入(arcn-info);(arcn-info);arc-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=arcn;/邻接点与输入逆序排列P164,正序?/邻接点顺序依赖输入顺序和创建程序，邻接点顺序依赖输入顺序和创建程序，“不给不给”默认正默认正序序 Retur
24、n OK；/思考无向网的创建有何不同？思考无向网的创建有何不同？上页上页 下页下页节节末页末页结束结束1 4230 120 1 2 3 4 A B C D E邻接表说明：邻接表说明：ABECD稀疏图用邻接表存储相对节省空间稀疏图用邻接表存储相对节省空间对有向图易求顶点出度与邻接点对有向图易求顶点出度与邻接点,但求入但求入度难度难.若只求入度可引入逆邻接表若只求入度可引入逆邻接表,也可结也可结合邻接表与逆邻接表引入合邻接表与逆邻接表引入十字链表十字链表对无向图易求度对无向图易求度,但边出现两次但边出现两次,为方便边为方便边操作可借助操作可借助多重链表多重链表A B C D E 303420 01
25、234上页上页 下页下页节节末页末页结束结束3、“有向图有向图”的十字链表存储表示的十字链表存储表示【选选】ABDCE0 10 A1 B2 C3 D4 E.tailv headv hlink tlinkinfodatafirstinfirstout0 3 VexNode:VexNode:ArcBox:ArcBox:1 22 4 3 2 4 0 4 1 具体邻接点顺序依赖输入顺具体邻接点顺序依赖输入顺序和图的创建程序，如逆序序和图的创建程序，如逆序上页上页 下页下页节节末页末页结束结束3、“有向图有向图”的十字链表存储表示的十字链表存储表示【选选】typedef struct ArcBox in
26、t tailvex,headvex;InfoType *info;struct ArcBox*hlink,*tlink;/指向同弧头/尾的下一弧 ArcBox;typedef struct VexNode /顶点的结构表示顶点的结构表示 VertexType data;ArcBox *firstin,*firstout;VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM;int vexnum,arcnum;OLGraph;上页上页 下页下页节节末页末页结束结束Status CreateDG(OLGraph G)scanf(&G.vexnum,&
27、G.arcnum,&IncInf);for(i=0;i G.vexnum;+i)scanf(&G.xlisti.data);G.xlisti.firstin=NULL;G.xlisti.firstout=NULL;for(k=0;kinfo);/END 上页上页 下页下页节节末页末页结束结束4、“无向图无向图”的邻接多重表存储表示的邻接多重表存储表示【选选】无向图的邻接表存储中，一条边出现两次，分别在两个无向图的邻接表存储中，一条边出现两次，分别在两个顶点对应的链表中，对边的操作复杂。为此，将每条边顶点对应的链表中，对边的操作复杂。为此，将每条边(Vi,Vj)只用一个如下结点表示只用一个如下结
28、点表示:顶点表示为：顶点表示为：mark ivexilink jvexjlinkinfodata firstedge0 1 2 3 A B C DABDC01 031 2 2 3 e1e2e3 e4 将边看作有向的，将边看作有向的，如如A-BA-B上页上页 下页下页节节末页末页结束结束typedef struct Ebox VisitIf mark;/访问标记访问标记 int ivex,jvex;/该边依附的两个顶点的位置该边依附的两个顶点的位置 struct EBox*ilink,*jlink;/指向对应顶点为指向对应顶点为i,j的下一边的下一边 InfoType *info;EBox;4、
29、“无向图无向图”的邻接多重表存储表示的邻接多重表存储表示【选选】typedef struct VexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;AMLGraph;/邻接多重表邻接多重表typedef struct VexBox VertexType data;EBox *firstedge;/指向第一条依附该顶点的边指向第一条依附该顶点的边 VexBox;上页上页 下页下页节节末页末页结束结束7.37.3图的遍历图的遍历深度优先遍历深度优先遍历规则规则:访问访问v,v,逐个从逐个从v v未访问的邻接点出发递归未访问的邻接点出发递归遍历，如此可遍
30、历所有与遍历，如此可遍历所有与v v连通的顶点连通的顶点.若尚有若尚有顶点未访问顶点未访问(不连通不连通),),则从其开始重复上述过程则从其开始重复上述过程.如如ABEFCDH.ABEFCDH.void DFS(G，v)VisitFunc(v);visitedv=TRUE;VisitFunc(v);visitedv=TRUE;for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if（!visitedw）DFS(G，w)；void DFSTraverse(Graph
31、 G,Status(*Visit)(int v)VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/visited数组和数组和VisitFunc函数为全局函数为全局每个顶点调用一次每个顶点调用一次DFS,DFSDFS,DFS主要操主要操作是查找邻接点作是查找邻接点,当用邻接矩阵存当用邻接矩阵存储时查找某顶点的邻接点复杂度为储时查找某顶点的邻接点复杂度为O(n),O(n),总复杂度总复杂度O(nO(n2 2););当邻接表存当邻接表存储时查找邻接点总复杂度为
32、储时查找邻接点总复杂度为O(e),O(e),总复杂度为总复杂度为O(n+e)O(n+e)DFSTraverseDFSTraverse每调用一次每调用一次DFSDFS所访所访问的顶点连通这些顶点关联的边构问的顶点连通这些顶点关联的边构成一个连通分量成一个连通分量.只保留走过的边只保留走过的边得生成树或生成森林得生成树或生成森林 B CA D F EH上页上页 下页下页节节末页末页结束结束abchdekfgachkfedbgabcdefghk2345607070807812385547注意邻接点的顺序作题时若未给出则默认为正序注意邻接点的顺序作题时若未给出则默认为正序,实际上应依赖实际上应依赖创建
33、程序和输入顺序。若给出存储结构则以所给为准。如上例创建程序和输入顺序。若给出存储结构则以所给为准。如上例既非正序也非逆序既非正序也非逆序,如如h h、k k顶点对应的链表，画生成树时注意顶点对应的链表，画生成树时注意求图的连通分量、深度优先生成树或生成森林求图的连通分量、深度优先生成树或生成森林P171P171DFSTraverseDFSTraverse每调用一次每调用一次DFSDFS所访问的顶点连同这些顶点关联的所访问的顶点连同这些顶点关联的边构成一个连通分量边构成一个连通分量.只保留走过的边得生成树或生成森林只保留走过的边得生成树或生成森林上页上页 下页下页节节末页末页结束结束7.3 7.
34、3 图的遍历图的遍历广度优先遍历广度优先遍历BFSTraverse(G,v,Visit();规则规则:访问访问v,v,访问访问v v的各未访问的邻接点的各未访问的邻接点,之后逐个从这些邻接之后逐个从这些邻接点出发重复上述操作点出发重复上述操作。待与待与v v连通的顶点访问毕再从另一顶点出连通的顶点访问毕再从另一顶点出发发.如如ABEHFCDABEHFCD实现：实现：对各个顶点对各个顶点v v：若其尚未访问则访问若其尚未访问则访问v,v,之后之后v v入队。入队。【队顶元素出队，逐个访问其尚未访问的邻接点，没访问完一队顶元素出队，逐个访问其尚未访问的邻接点，没访问完一个便入队个便入队】。重复。重
35、复【】【】中内容到队空中内容到队空 B CA D F EH上页上页 下页下页节节末页末页结束结束void BFSTraverse(Graph G,Status(*Visit)(int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;InitQueue(Q);for(v=0;v=0;w=NextAdjVex(G,v,w)if(!visitedw)/注意注意NextAdjVex返回值约定返回值约定 Visit(w);visitedw=TRUE;EnQueue(Q,w);对各个顶点对各个顶点v v：若其尚未访问则访问若其尚未访问则访问v,v,之后之后v v入队。入队。【队
36、顶元素出队，逐个队顶元素出队，逐个访问其尚未访问的邻接点，每访问完一个便入队访问其尚未访问的邻接点，每访问完一个便入队】。重复。重复【】【】中内容到队空中内容到队空每个顶点进一次队每个顶点进一次队,出队时主要操作是查找邻接点出队时主要操作是查找邻接点,当用邻接矩阵存储时查找某顶点的各邻接点复杂度当用邻接矩阵存储时查找某顶点的各邻接点复杂度的为的为O(n),O(n),总复杂度总复杂度O(nO(n2 2););当用邻接表存储时查找当用邻接表存储时查找邻接点复杂度为邻接点复杂度为O(e),O(e),总复杂度为总复杂度为O(n+e)O(n+e)上页上页 下页下页节节末页末页结束结束7.4.3 7.4.
37、3 最小生成树最小生成树P173P173假设要在假设要在 n 个城市之个城市之间建立通讯联络网，间建立通讯联络网，不同城市间建立通讯不同城市间建立通讯设施的代价设施的代价不同不同，如，如何在最节省经费的前何在最节省经费的前提下建立这个通讯网？提下建立这个通讯网？即找权值之和最小的即找权值之和最小的极小连通子网，问题极小连通子网，问题转换为转换为在连通网中找在连通网中找一颗生成树，最小生一颗生成树，最小生成树成树abcdegf195141827168213ae12dcbgf7148531621上页上页 下页下页节节末页末页结束结束uKuaskal算法算法直接找权值最小的边直接找权值最小的边,若并
38、入后构成回路则舍若并入后构成回路则舍弃弃KruskalKruskal算法求最小生成树：算法求最小生成树：设设N=(V,E)是连通网是连通网,求最小生成树求最小生成树令令T=(V,),T=(V,),各顶点自各顶点自成一连通分量成一连通分量在在E E中找代价最小的边中找代价最小的边,若该边的顶点落在若该边的顶点落在不同不同连通分量连通分量上，则将其并上，则将其并入入,依次类推至所有顶依次类推至所有顶点到一个连通分量上点到一个连通分量上总总O(eloge)O(eloge)，与，与n n无关，无关，适合稀疏图适合稀疏图abcdegf195141827168213ae12dcbgf71485316217
39、121819PrimPrim算法是逐个顶点并入，再据顶点找最小边；算法是逐个顶点并入，再据顶点找最小边；上页上页 下页下页节节末页末页结束结束普里姆普里姆PrimPrim算法求最小生成树：算法求最小生成树：abcdegf195141827168213ae12dcb7aaa1914180e12ee8160d3dd7210c5 0e0gd0f0设设U U代表已并入最小生成树中的顶点的集合，最初任选一点放代表已并入最小生成树中的顶点的集合，最初任选一点放入入U U。之后找。之后找U U到到U U最小边，将对应新顶点并入，共最小边，将对应新顶点并入，共N-1N-1轮即可轮即可从顶点从顶点u u0 0开
40、始开始,令令U=uU=u0 0,初始化初始化u0u0到其余各顶点距离到其余各顶点距离 找最小的边输出找最小的边输出,并入新顶点并入新顶点,赋赋0+0+更新表更新表使使U U到非到非U U距离更小距离更小。如上重复如上重复n-1n-1次次上页上页 下页下页节节末页末页结束结束构造下表对应的数组构造下表对应的数组,每个元素对应一个顶点每个元素对应一个顶点,元素取值是当前轮从元素取值是当前轮从U到该点最小边的信息到该点最小边的信息(出发点下标和代价出发点下标和代价),顶点被并入顶点被并入U后代价置后代价置0struct VertexType adjvex;/出发点名称出发点名称 VRType low
41、cost;/代价代价closedgeMAX_VERTEX_NUM;aaa1914180e12ee8160d3dd7210c5 0e0d0上页上页 下页下页节节末页末页结束结束void MiniSpanTree_Prim(MGraph G,VertexType u)/用普里姆算法从用普里姆算法从u出发求网出发求网G(邻接矩阵表示邻接矩阵表示)最小生成树最小生成树,输出各边输出各边 k=LocateVex(G,u);closedgek.lowcost=0;/将将u并入并入U,赋赋0 for(j=0;jG.vexnum;+j)/据据u更新数组元素代价更新数组元素代价 if(j!=k)closedge
42、j=u,G.arcskj.adj;for(i=1;ik closedgek.lowcost=0;/将将k号结点并入号结点并入U，赋，赋0 for(j=0;jG.vexnum;+j)/据据k号结点更新数组元素代价号结点更新数组元素代价 if(G.arcskj).adjclosedgej.lowcost closedgej=G.vexsk,G.arcskj.adj;将初始点将初始点u u并入并入U,U,初始化表初始化表;之后找小边并入之后找小边并入,赋赋0+0+更新更新 重复重复复杂度为复杂度为O(n2),与与边数无关，适合稠边数无关，适合稠密图密图上页上页 下页下页节节末页末页结束结束7.5.1
43、 7.5.1 拓扑排序拓扑排序pAOV-网网:顶点表示顶点表示活动活动,弧表示活动间弧表示活动间先后先后(依赖依赖)关系关系的有向图的有向图.pAOV-网用以表示工程或系统的施工计划，可据此判网用以表示工程或系统的施工计划，可据此判断工程是否可以顺利进行断工程是否可以顺利进行pAOV-网中应存在一个覆盖全部顶点的序列网中应存在一个覆盖全部顶点的序列(全序全序),在在该序列中顶点出现的顺序满足网中的先后关系该序列中顶点出现的顺序满足网中的先后关系(偏序偏序)。一个全序就对应一个合法的一个全序就对应一个合法的完整完整工序工序BDACBDAC上页上页 下页下页节节末页末页结束结束由某个集合上的一个由
44、某个集合上的一个偏序偏序得到该集合上的得到该集合上的一个一个全序全序,该操作称该操作称为为拓扑排序拓扑排序。若得到一个含全部顶点的拓扑有序序列若得到一个含全部顶点的拓扑有序序列(全序全序)则则说明工程可顺利开展说明工程可顺利开展,不存在则说明图中存在有向回路不存在则说明图中存在有向回路,不合理不合理何谓拓扑排序何谓拓扑排序BDACABCDABCD或或ACBDACBD均是含全均是含全部顶点的拓扑有序序部顶点的拓扑有序序列列(DAG(DAG图图)BDAC不存在含全部顶点的拓扑有不存在含全部顶点的拓扑有序序列序序列,存在有向回路存在有向回路BCDB上页上页 下页下页节节末页末页结束结束从有向图中选取
45、一没有前驱的顶点并输出之；从有向图中选取一没有前驱的顶点并输出之；重复上述两步，至重复上述两步，至图空图空(得一全序得一全序)或图不空但或图不空但不存在无前驱的顶点不存在无前驱的顶点(得一有向环得一有向环)。从图中从图中“删除删除”此顶点及所有从其出发的弧此顶点及所有从其出发的弧如何进行拓扑排序如何进行拓扑排序abcghdfea bc hdgfeBDACA入度入度0顶点入栈顶点入栈,出栈并据此更新入度出栈并据此更新入度,零入度者入栈零入度者入栈重复至栈空重复至栈空上页上页 下页下页节节末页末页结束结束3 3、拓扑排序算法的实现、拓扑排序算法的实现将入度为将入度为0的顶点入栈的顶点入栈,出栈并据
46、此更新入度出栈并据此更新入度,如此重如此重复复Status TopologicalSort(ALGraph G)/G用邻接表存储用邻接表存储,若若G无回路则输出拓扑有序序列无回路则输出拓扑有序序列,返返OK,否则返否则返ERROR.FindInDegree(G,indegree);/求各顶点入度存入数组求各顶点入度存入数组indegreeindegree InitStack(S);InitStack(S);for(i=0;iG.vexnum;+i)if(!indegreei)Push(s,i);count=0;/用以对输出的顶点进行计数用以对输出的顶点进行计数 while(!StackEmpt
47、y(S)Pop(S,i);printf(G.verticesi.data);+count;if(countnextarc)for(p=G.verticesi.firstarc;p!=NULL;p=p-nextarc)k=p-adjvex;k=p-adjvex;-indegreek;/-indegreek;/更新入度更新入度 if(!indegreek)Push(S,w);/if(!indegreek)Push(S,w);/新的入度为零的顶点入新的入度为零的顶点入栈栈 最初求入度最初求入度O(e);第一波顶点入栈第一波顶点入栈O(n)；若为；若为DAG图则图则每个顶点入栈、出栈各一次每个顶点入栈
48、、出栈各一次,O(n);入度减入度减1的操作执行的操作执行e次次,故总复杂的度故总复杂的度O(n+e)上页上页 下页下页节节末页末页结束结束作业：作业：7.7prim算法注意画表，多张算法注意画表，多张Kruscal算法，手工执行，直接给答案算法，手工执行，直接给答案abcdegf195141827168213ae12dcbgf71485316217121819上页上页 下页下页节节末页末页结束结束作业：作业：l9 对下图执行教材中的拓扑排序算法，写出得对下图执行教材中的拓扑排序算法，写出得到的拓扑有序序列到的拓扑有序序列abcghdfeabcdegf195141827168213ae12dc
49、bgf7148531621上页上页 下页下页节节末页末页结束结束7.5.2 7.5.2 关键路径关键路径AOE网网：顶点表示状态，弧表示：顶点表示状态，弧表示活动活动，弧权表示完成活动所，弧权表示完成活动所需需时间时间。用以估算工程的完成时间。用以估算工程的完成时间问问:最短最短工期工期多长？哪些活动是影响工期的多长？哪些活动是影响工期的“关键活动关键活动”abcdefghk64521187244源点源点汇点汇点174关键路径关键路径(长度最长的路径长度最长的路径)决定工期决定工期关键活动关键活动:工程正常开展工程正常开展最早开始时间最早开始时间等于等于最迟开始时间最迟开始时间的活动的活动ee
50、(act)=ee(act)=ve(ve(头头)与与 el(act)el(act)=vl(vl(尾尾)-dur(act)-dur(act)上页上页 下页下页节节末页末页结束结束ve(源点源点)=0.对普通顶点对普通顶点v,设设W为其前驱顶点集则为其前驱顶点集则ve(v)=max ve(w)+dut(w,v)|wW u如何保证求如何保证求ve(v)ve(v)时时ve(w)ve(w)已经求出？已经求出？关键活动求取关键活动求取求各点最早到达时间求各点最早到达时间ve(x)abcdefghk64521187244实现实现:各顶点各顶点ve初始化为初始化为0,找无前驱顶点找无前驱顶点,据其据其ve值值更
