图及其基本算法

图及其基本算法第1页，共83页，2023年，2月20日，星期五图的概念图（graph）是图型结构的简称。它是一种复杂的非线性数据结构。图在各个领域都着广泛的应用。图的二元组定义为：G=（V,E）其中V是非空的顶点集合，即V={vi|1<=i<=n,n>=1,vi∈elemtype，n为顶点数}E是V上顶点的序偶或无序对的集合，即对应边的集合。第2页，共83页，2023年，2月20日，星期五123412453图1

有向图图2

无向图第3页，共83页，2023年，2月20日，星期五图的基本术语

1、端点和邻接点在一个无向图中，若存在一条边（vi，vj），则称vi,vj为此边的两个端点，并称它们互为邻接点（adjacent），即vi是vj的一个邻接点，vj也是vi的一个邻接点。在一个有向图中，若存在一条边<vi,vj>，则称此边是顶点vi的一条出边（outedge），顶点vj的一条入边（inedge）；称Vi为此边的起始端点，简称起点或始点，vj为此边的终止端点，简称终点；称vi和vj互为邻接点，并称vj是vi的出边邻接点，vi是vj的入边邻接点。第4页，共83页，2023年，2月20日，星期五2、顶点的度、入度、出度无向图顶点v的度（degree）定义为以该顶点为一个端点的边的数目，简单地说，就是该顶点的边的数目，记为D（v）。如图2中v1顶点的度为2，v2顶点的度为3。有向图中顶点v的度有入度和出度之分，入度（indegree）是该顶点的入边的数目，记为ID（v）；出度（outdegree）是该顶点的出边的数目，记为OD（v）顶点v的度等于它的入度和出度之和，即D（v）=ID（v）+OD（v）。第5页，共83页，2023年，2月20日，星期五

3、完全图、稠密图、稀疏图若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。显然，若完全图是无向的，则图中包含有n（n-1）/2条边,若完全图是有向的，则图中包含有n（n-1）条边。当一个图接近完全图时，则可称为稠密图，相反地，当一个图有较少的边数（即e<<n（n–1））时，则可称为稀疏图。第6页，共83页，2023年，2月20日，星期五12543G112543G212543G3第7页，共83页，2023年，2月20日，星期五

4、子图设有两个图G=（V,E）和G’＝（V’,E’）,若V’是V的子集，且E’是E的子集，则称G’是G的子图。12453124531245图图的子图第8页，共83页，2023年，2月20日，星期五5、路径和回路在一个图G中，从顶点v到顶点v’的一条路径（path）是一个顶点序列vi0,vi1,vi2,...,vim,其中v=vi0,v’=vim,若此图是无向图，则（vi,j-1,vij）∈E（G），（1≤j≤m）；若此图是有向图，则<vi,j-1,vij>∈E（G），（1≤j≤m）。路径长度是指该路径上经过的边的数目。若一条路径上除了前后端点可以相同外，所有顶点均不同，则称此路径为简单路径。若一条路径上的前后两端点相同，则被称为回路或环（cycle），前后两端点相同的简单路径被称为简单回路或简单环。第9页，共83页，2023年，2月20日，星期五6、连通和连通分量在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。无向图G的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。第10页，共83页，2023年，2月20日，星期五1254376G11254G1136G127G13第11页，共83页，2023年，2月20日，星期五7、强连通图和强连通分量在有向图G中，若从顶点vi到顶点vj有路径，则称从vi到vj是连通的。若图G中的任意两个顶点vi和vj都连通，即从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图G的极大强连通子图称为G的强连通分量。显然，强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。第12页，共83页，2023年，2月20日，星期五12543G112543G2125G2143G22第13页，共83页，2023年，2月20日，星期五8、权和网在一个图中．每条边可以标上具有某种含义的数值，此数值称为该边的权（weight）。例如，对于一个反映城市交通线路的图，边上的权可表示该条线路的长度或等级；对于一个反映电子线路的图，边上的权可表示两端点间的电阻、电流或电压；对于一个反映零件装配的图，边上的权可表示一个端点需要装配另一个端点的零件的数量；对于一个反映工程进度的图，边上的权可表示从前一子工程到后一子工程所需要的天数。边上带有权的图称作带权图，也常称作网（network）。第14页，共83页，2023年，2月20日，星期五

图的存储结构

1、邻接矩阵邻接矩阵（adjacencymatrix）是表示顶点之间相邻关系的矩阵。设G＝（V，E）是具有n个顶点的图，顶点序号依次为1、2、···、n，则G的邻接矩阵是具有如下定义的n阶方阵。第15页，共83页，2023年，2月20日，星期五邻接矩阵的表示1234有向图12453无向图第16页，共83页，2023年，2月20日，星期五2、邻接表邻接表（adjacencylist）是对图中的每个顶点建立一个邻接关系的单链表，并把它们的表头指针用向量存储的一种图的表示方法。为顶点vi建立的邻接关系的单链表又称作vi的邻接表。vi邻接表中的每个结点用来存储以该顶点为端点或起点的一条边的信息，因而被称为边结点。vi邻接表中的结点数，对于无向图来说，等于vi的边数，邻接点数或度数；对于有向图来说，等于vi的出边数、出边邻接点数或出度数。第17页，共83页，2023年，2月20日，星期五邻接表描述边结点：

Eptr=^enode;Eode=recordadjvex:1..n;w:wtype;next:eptrend;vexnode=recorddata:datatypelink:eptr;end;Adjlnk=array[1..n]ofvexnode;Proccreate(G)Fori:=1tondobegininput(g[i].data);g[i].link:=nil;end;Fork:=1toedobegininput(i,j);new(s);s^.adjvex:=j;s^.next:=g[i].link;g[i].link:=s;end;第18页，共83页，2023年，2月20日，星期五1234有向图1234^23^4^1^有向图邻接表12453无向图42^535431^32^12351^2^无向图邻接表4第19页，共83页，2023年，2月20日，星期五3、边集数组边集数组（edgesetarray）是利用一维数组存储图中所有边的一种图的表示方法。该数组中所含元素的个数要大于等于图中边的条数，每个元素用来存储一条边的起点、终点（对于无向图，可选定边的任一端点为起点或终点）和权（若有的话），下各边在数组中的次序可任意安排，也可根据具体要求而定。第20页，共83页，2023年，2月20日，星期五

图的遍历

1、深度优先遍历深度优先搜索（depthfirstsearch）遍历类似树的先根遍历，它是一个递归过程.可叙述为：首先访问一个顶点vi（开始为初始点），并将其标记为已访问过，然后从vi的一个未被访问的邻接点（无向图）或出边邻接点（有向图）出发进行深度优先搜索遍历，当vi的所有邻接点均被访问过时，则退回到上一个顶点vk，从vk的另一个未被访问过的邻接点出发进行深度优先搜索遍历。算法：procdfs(v)beignprint(v);visited[v]:=true;forj:=1tondoifnotvisited[j]andg[v,j]=1thendfs(j);end第21页，共83页，2023年，2月20日，星期五练习1：无向图的深度优先搜索【问题描述】从文件中读入无向图的信息，按深度优先搜索的方式遍历图中的每一个结点，并按访问的现后顺序将结点输出，以V1作为第一个访问的结点。【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行两个数x和y，表示x与y之间有一条边。【输出文件】一行：结点的序列。

【示例】

输入：输出：

55125341213253545第22页，共83页，2023年，2月20日，星期五2、广度优先搜索遍历广度优先搜索（breadth—firstsearch）遍历类似树的按层遍历，其过程为：首先访问初始点vi,并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,···,vit并均标记为已访问过，然后再按照vi1,vi2,···,vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。算法：procbfs(v)beginsetnull(Q);print(v);visited[v]:=true;insert(Q,v);repeath:=delete(Q);forj:=1tondoifnotvisited[j]andg[h,j]=1thenbeginprint(j);visited[j]:=true;insert(Q,j);end;untilempty(Q);end;第23页，共83页，2023年，2月20日，星期五练习2：无向图的广度优先搜索【问题描述】从文件中读入无向图的信息，按广度优先搜索的方式遍历图中的每一个结点，并按访问的现后顺序将结点输出，以V1作为第一个访问的结点。【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行两个数x和y，表示x与y之间有一条边。【输出文件】一行：结点的序列。

【示例】

输入：输出：

55123541213253545第24页，共83页，2023年，2月20日，星期五非连通图的遍历前面提到的深度优先遍历和广度优先遍历都只从图的一个顶点开始进行一次遍历，对于连通图可以遍历到图的所有结点，但如果图不连通，则有一部分结点无法访问到。修改很简单，每次选取任意一个没有被遍历过的结点开始一次遍历，重复此操作直到遍历完图的所有结点即可。第25页，共83页，2023年，2月20日，星期五procbfs(v)beginsetnull(Q);print(v);visited[v]:=true;flag:=flase;{图中顶点是否访问完}whilenotflagdobeginflag:=true;insert(Q,v);repeath:=delete(Q);forj:=1tondoifnotvisited[j]andg[h,j]=1thenbeginprint(j);visited[j]:=true;insert(Q,j);end;untilempty(Q);forj:=1tondoifvisited[j]=falsethenbeginv:=j;flag:=false;end;end;end;非连通图的遍历第26页，共83页，2023年，2月20日，星期五图的连通分量对于连通图只有一个连通分量；对于非连通图有多个连通分量。如右图：有两个连通分量，它们分别是：1，2，34，512345第27页，共83页，2023年，2月20日，星期五求连通分量的算法procbfs(v)beginsetnull(Q);print(v);visited[v]:=true;flag:=flase;{图中顶点是否访问完}whilenotflagdobeginflag:=true;insert(Q,v);repeath:=delete(Q);添加操作：将每一个出队的顶点保存；

forj:=1tondoifnotvisited[j]andg[h,j]=1thenbeginprint(j);visited[j]:=true;insert(Q,j);end;untilempty(Q);

//repeat..until循环结束一次，得到一个连通分量；forj:=1tondoifvisited[j]=falsethenbeginv:=j;flag:=false;end;end;end;第28页，共83页，2023年，2月20日，星期五练习3：求无向图的连通分量【问题描述】从文件中读入无向图的信息，求出该图的连通分量个数。【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行两个数x和y，表示x与y之间有一条边。【输出文件】输出一个整数，表示连通分量的个数。

【示例】

输入：输出：

5521213253523第29页，共83页，2023年，2月20日，星期五有向图的强连通图分量定义：在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(stronglyconnected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(stronglyconnectedcomponents)。下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。第30页，共83页，2023年，2月20日，星期五Tarjan算法Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出：

Low(u)=Min{DFN(u),Low(v),(u,v)为树枝边，u为v的父节点

DFN(v),(u,v)为指向栈中节点的后向边(非横叉边)—指向其祖先的边

横叉边---从一个连通分量到另一个连通分量之间的边}

当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量（当前递归栈内存在一个SCC）。第31页，共83页，2023年，2月20日，星期五算法伪代码如下：tarjan(u){ DFN[u]=Low[u]=++Index//为节点u设定次序编号和Low初值

Stack.push(u)//将节点u压入栈中

foreach(u,v)inE//枚举每一条边

if(visnotvisted)//如果节点v未被访问过---说明是树枝

tarjan(v)//继续向下找

Low[u]=min(Low[u],Low[v]) elseif(vinS)//如果节点v还在栈内—说明是后向边

Low[u]=min(Low[u],DFN[v])//if(visvistedandvnotinS)---(u,v)是横叉边 if(DFN[u]==Low[u])//如果节点u是强连通分量的根

repeat v=S.pop//将v退栈，为该强连通分量中一个顶点

printv until(u==v)}第32页，共83页，2023年，2月20日，星期五算法流程的演示：从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN[6]=LOW[6]，找到了一个强连通分量。退栈到u=v为止，{6}为一个强连通分量。返回节点5，发现DFN[5]=LOW[5]，退栈后{5}为一个强连通分量。第33页，共83页，2023年，2月20日，星期五返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以LOW[4]=1。节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树枝边，所以LOW[3]=LOW[4]=1。继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW[2]=DFN[4]=5。返回1后，发现DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。第34页，共83页，2023年，2月20日，星期五每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。【输入文件】第一行两个数N,M。接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可能出现多个A,B）【输出文件】一个数，即有多少头牛被所有的牛认为是受欢迎的。【样例输入】33122123【样例输出】1练习4：受欢迎的牛第35页，共83页，2023年，2月20日，星期五图的生成树与最小生成树在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，即：若边集E（G’）中的边既将图中的所有顶点连通又不形成回路，则称子图G’是原图G的一棵生成树。最小生成树：给图中每个边赋一权值，所有生成树中所选择边的权值之和最小的生成树，称之为最小代价生成树，即是最小生成树。第36页，共83页，2023年，2月20日，星期五3124566555136462图31245651342图的最小生成树31245655564图的非最小生成树第37页，共83页，2023年，2月20日，星期五普里姆算法

假设G=（V，E）是一个具有n个顶点的连通网，T=（U，TE）是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点（假定取v1），将它并入U中，此时U={v1}，然后只要U是V的真子集，就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为（vi，vj），其中，并把该边（vi，vj）和顶点vj分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到（n一1）次后就把所有n个顶点都并入到生成树T的顶点集中，此时U＝V，TE中含有（n一1）条边，T就是最后得到的最小生成树。第38页，共83页，2023年，2月20日，星期五普里姆算法的关键之处是：每次如何从生成树T中到T外的所有边中，找出一条最短边。例如，在第k次前，生成树T中已有k个顶点和（k-1）条边，此时T中到T外的所有边数为k（n-k），当然它包括两顶点间没有直接边相连，其权值被看作为“无穷大”的边在内，从如此多的边中查找最短边，其时间复杂性为O（k（n-k）），显然是很费时的。是否有一种好的方法能够降低查找最短边的时间复杂性呢？关键问题第39页，共83页，2023年，2月20日，星期五方法是：假定在进行第k次前已经保留着从T中到T外每一顶点（共（n-k）个顶点）的各一条最短边，进行第k次时，首先从这（n-k）条最短边中，找出一条最最短的边（它就是从T中到T外的所有边中的最短边），假设为（vi,vj），此步需进行（n-k）次比较；然后把边（vi,vj）和顶点vj分别并入T中的边集TE和顶点集U中，此时T外只有n-（k+1）个顶点，对于其中的每个顶点vt，若（vj,vt）边上的权值小于已保留的从原T中到vt的最短边的权值，则用（vj，vt）修改之，使从T中到T外顶点vt的最短边为（vj，vt），否则原有最短边保持不变，这样，就把第k次后从T中到T外每一顶点vt的各一条最短边都保留下来了。为进行第（k+1）次运算做好了准备，此步需进行（n-k-1）次比较。所以，利用此方法求第k次的最短边共需比较2（n-k）-1次，即时间复杂性为O（n-k）。解决办法第40页，共83页，2023年，2月20日，星期五prim算法设一个辅助数组closedge，以记录从U到V-U具有最小代价的边。数组中的每个元素closedge[v]是记录类型，包含两个域：

closedge[v].lowcast=Min{cost(u,v)|u∈U};closedge[v].vex存储该边依附的在U中的顶点。第41页，共83页，2023年，2月20日，星期五代码procmintree_prim(gn:adjmatrix;u0:integer);beginforv:=1tondoifv<>u0thenwithclosedage[v]do[vex:=u0;lowcast:=gn[u0,v];]closedge[u0].lowcast:=0;{并入U集合}fori:=1ton-1dobegink:=min(closedge);{寻找代价最小的边}write(closedge[k].vex,k);第42页，共83页，2023年，2月20日，星期五

closedge[k].lowcast:=0;{并入U集合}forv:=1tondoifgn[k,v]<closedge[v].lowcastthenbeginclosedge[v].lowcast:=gn[k,v];closedge[v].vex:=k;end;

end;end;第43页，共83页，2023年，2月20日，星期五练习1：prim算法实现【问题描述】从文件中读入连通带权图的信息，按prim算法求出该图的最小生成树，以V1作为初始结点。【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行三个数x、y和k，k表示x与y之间边的权值。【输出文件】共m行，第一行：最小生成树的权；以下m-1行表示选取的边，边的第1个结点小于第2个结点，并按结点由小到大输出。

【示例】

输入：输出：

57451217142330151452424103534243571523第44页，共83页，2023年，2月20日，星期五练习2：EddypaintingEddybeginstolikepaintingpicturesrecently,heissureofhimselftobecomeapainter.EverydayEddydrawspicturesinhissmallroom,andheusuallyputsouthisnewestpicturestolethisfriendsappreciate.buttheresultitcanbeimagined,thefriendsarenotinterestedinhispicture.Eddyfeelsverypuzze,inordertochangeallfriends'sviewtohistechnicalofpaintingpictures,soEddycreatesaproblemforthehisfriendsofyou.

Problemdescriptionsasfollows:Givenyousomecoordinatespiontsonadrawingpaper,everypointlinkswiththeinkwiththestraightline,causesallpointsfinallytolinkinthesameplace.Howmanydistantsdoesyourdutydiscovertheshortestlengthwhichtheinkdraws?Input：Thefirstlinecontains0<n<=100,thenumberofpoint.Foreachpoint,alinefollows;eachfollowinglinecontainstworealnumbersindicatingthe(x,y)coordinatesofthepoint.

Inputcontainsmultipletestcases.Processtotheendoffile.Output：Yourprogramprintsasinglerealnumbertotwodecimalplaces:theminimumtotallengthofinklinesthatcanconnectallthepoints.SampleInput：31.01.02.02.02.04.0SampleOutput：3.41第45页，共83页，2023年，2月20日，星期五

克鲁斯卡尔算法假设G＝（V，E）是一个具有n个顶点的连通网，T＝（U，TE）是G的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空。此算法的基本思想是，将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边，若选取的边使生成树T形成回路，则将其舍弃，如此进行下去，直到TE中包含有n－1条边为止。此时的T即为最小生成树。第46页，共83页，2023年，2月20日，星期五克鲁斯卡尔算法的关键之处是：如何判断欲加入的一条边是否与生成树中已选取的边形成回路。这可将各顶点划分为所属集合的方法来解决，每个集合中的顶点表示一个无回路的连通分量。算法开始时，由于生成树的顶点集等于图G的顶点集，边集为空，所以n个顶点分属于n个集合。每个集合中只有一个顶点，表明顶点之问互不连通。关键问题第47页，共83页，2023年，2月20日，星期五Kruskal算法procmintree_krusk(gn:adjmatrix);beginfori:=1tondoun[i]:=i;fori:=1ton-1dobeginminedge(a,b);write(a,b,gn[a,b]);k:=un[b];fori:=1tondo{两个连通分量合并}ifun[i]=kthenun[i]:=un[a];end;end;procminedge(vara:integer;varb:integer);用于在剩下的边中选取不再同一连通分量上的最小代价的边，边的结点分别为a和b。为了实现该过程，可以将图中的边生成边结点（包含两个顶点和代价）数组，由小到大排序，然后通过排序后的数组进行处理；un数组：用来记载随着边的加入，各顶点属于哪个连通分量。第48页，共83页，2023年，2月20日，星期五练习3：Kruskal算法实现【问题描述】从文件中读入连通带权图的信息，按Kruskal算法求出该图的最小生成树，以V1作为初始结点。【输入文件】第一行两个整数m和n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行三个数x、y和k，k表示x与y之间边的权值。【输出文件】共m行，第一行：最小生成树的权；以下m-1行表示选取的边，按选取边的权值由小到大输出。

【示例】

输入：输出：

57451217142330351452424101534243571523第49页，共83页，2023年，2月20日，星期五练习4：判断最小生成树是否唯一Givenaconnectedundirectedgraph,tellifitsminimumspanningtreeisunique.

Definition1(SpanningTree):Consideraconnected,undirectedgraphG=(V,E).AspanningtreeofGisasubgraphofG,sayT=(V',E'),withthefollowingproperties:

1.V'=V.

2.Tisconnectedandacyclic.

Definition2(MinimumSpanningTree):Consideranedge-weighted,connected,undirectedgraphG=(V,E).TheminimumspanningtreeT=(V,E')ofGisthespanningtreethathasthesmallesttotalcost.ThetotalcostofTmeansthesumoftheweightsonalltheedgesinE'.InputThefirstlinecontainsasingleintegert(1<=t<=20),thenumberoftestcases.Eachcaserepresentsagraph.Itbeginswithalinecontainingtwointegersnandm(1<=n<=100),thenumberofnodesandedges.Eachofthefollowingmlinescontainsatriple(xi,yi,wi),indicatingthatxiandyiareconnectedbyanedgewithweight=wi.Foranytwonodes,thereisatmostoneedgeconnectingthem.OutputForeachinput,iftheMSTisunique,printthetotalcostofit,orotherwiseprintthestring'NotUnique!'.SampleInput23312123231344122232342412SampleOutput3NotUnique!第50页，共83页，2023年，2月20日，星期五最短路径由于从一顶点到另一顶点可能存在着多条路径。每条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。求图中一顶点vi到其余各顶点的最短路径和最短距离比较容易，只要从该顶点vi，出发对图进行一次广度优先搜索遍历，在遍历时记下每个结点的层次即可。第51页，共83页，2023年，2月20日，星期五若图是带权图（假定权值非负）从源点vi到终点vj的每条路径上的权（它等于该路径上所经边上的权值之和，称为该路径的带权路径长度）可能不同，我们把权值最小的那条路径也称做最短路径，其权值也称作最短路径长度或最短距离。实际上，这两类最短路径问题可合并为一类，这只要把第一类的每条边的权都设为1就归属于第二类了，所以在以后的讨论中，若不特别指明，均是指第二类的最短路径问题。第52页，共83页，2023年，2月20日，星期五求图的最短路径问题包括两个子问题：一是求图中一顶点到其余各顶点的最短路径，二是求图中每对顶点之间的最短路径。下面分别进行讨论。解决问题第53页，共83页，2023年，2月20日，星期五从一顶点到其余各顶点的最短路径迪杰斯特拉（Dijkstra）于1959年提出了解决此问题的一般算法，具体做法是按照从源点到其余每一顶点的最短路径长度的升序依次求出从源点到各顶点的最短路径及长度，每次求出从源点vi到一个终点vj的最短路径及长度后，都要以vj作为新考虑的中间点，用vi到vj的最短路径和最短路径长度对vi到其它尚未求出最短路径的那些终点的当前路径及长度作必要的修改，使之成为当前新的最短路径和最短路径长度，当进行n-2次后算法结束。第54页，共83页，2023年，2月20日，星期五始点终点最短路径路径长度v0v1无v2(v0,v2)10v3(v0,v4,v3)50v4(v0,v4)30v5(v0,v4,v3,v5)600123455105020103010060有向图第55页，共83页，2023年，2月20日，星期五始点终点最短路径路径长度v1V2(v1,v2)10V3(v1,v2,v3)27V4(v1,v5,v4)20v5(v1,v5)71253410751317492834无向图第56页，共83页，2023年，2月20日，星期五Dijkstra算法首先，引进一个辅助向量dist，dist[i]表示当前所找到的从始点V到每个终点Vi的最短路径长度。其初态为：若<v,vi>存在，则dist[i]为其上的权值，否则为最大值（计算机能表示）。算法:(1)用邻接矩阵cost表示带权图。S表示已找到的从v出发的最短路径的终点的集合，初态为空。dist向量的初值为：dist[v,i]=cost[v,i];(2)选择vj，使得：dist[j]=Min{dist[i]|vi∈V-S}；vj就是当前求得从v出发的最短路径的终点。S=S+{j};(3)修改从v出发到集合V-S上任意顶点vk可达的最短路径长度。ifdist[j]+cost[j,k]<dist[k]thendist[k]:=dist[j]+cost[j,k];(4)重复(2)(3)共n-1次。第57页，共83页，2023年，2月20日，星期五procshort_dij;beginfori:=1tondobegindist[i]:=cost[v0,i];ifdist[i]<maxthenpath[i]:=[v0]+[i]elsepath[i]:=[];end;s:=[v0];fork:=1ton-1dobeginwm:=max;j:=v0;fori:=1tondoifnot(iins)and(dist[i]<wm)thenbeginj:=i;wm:=dist[i];end;s:=s+[j];

fori:=1tondoifnot(iins)and(dist[j]+cost[j,i]<dist[i])thenbegindist[i]:=dist[j]+cost[j,i];path[i]:=path[j]+[i];end;end;end;其中：cost：邻接矩阵；path[i]：存储从v0到顶点i的最短路径；是以集合作为数组元素；dist[i]：存储相应路径长度；s：集合，表示已处理的顶点。第58页，共83页，2023年，2月20日，星期五练习5：Dijkstra算法练习【问题描述】从文件中读入带权图的信息，按Dijkstra算法根据给定源点求出从源点到该图中其余顶点的最短路径。【输入文件】第一行：一个整数L：L=0表示无向图，L=1表示有向图；第二行三个整数m、n和k，分别表示图的结点数、图中的边数以及源点。以下n行表示n条边：每一行三个数x、y和z，z表示x与y之间边的权值。【输出文件】共m-1行，每一行的数据包括：顶点：最短路径：路径，如果不存在路径，数据为：顶点：Nopath。

【示例】

输入：输出：

6812：Nopath13103：10：1315304：50：154161005：30：132356：60：15463450461054205660第59页，共83页，2023年，2月20日，星期五练习6：路由选择问题【问题描述】X城有一个含有N个节点的通信网络，在通信中，我们往往关心信息从一个节点I传输到节点J的最短路径。遗憾的是，由于种种原因，线路中总有一些节点会出故障，因此在传输中要避开故障节点。

任务一：在己知故障节点的情况下，求避开这些故障节点，从节点I到节点J的最短路径S0。

任务二：在不考虑故障节点的情况下，求从节点I到节点J的最短路径S1、第二最短路径S2。【输入文件】第1行：NIJ(节点个数起始节点目标节点)

第2—N+1行：Sk1Sk2…SkN(节点K到节点J的距离为SkJK=1，2，……，N)

最后一行：PT1T2……Tp(故障节点的个数及编号)【输出文件】S0S1S2(S1<=S2从节点I到节点J至少有两条不同路径)【输入输出样例】route.in515

010500

1000620

5003035

063006

0203560

12route.out402230第60页，共83页，2023年，2月20日，星期五每对顶点之间的最短路径求图中每对顶点之间的最短路径是指把图中任意两个顶点vi和vj（i≠j）之间的最短路径都计算出来。解决此问题有两种方法：一是分别以图中的每个顶点为源点共调用n次迪杰斯特拉算法，此方法的时间复杂性为O（n3）；二是采用下面介绍的弗洛伊德（Floyed）算法，此算法的时间复杂性仍为O（n3），但比较简单。第61页，共83页，2023年，2月20日，星期五弗洛伊德算法实际上是一个动态规划的算法。从图的邻接矩阵开始，按照顶点v1，v2，···，vn的次序，分别以每个顶点vk（1≤k≤n）作为新考虑的中间点，在第k-1次运算Ak-1（A（0）为原图的邻接矩阵G）的基础上，求出每对顶点vi到vj的最短路径长度计算公式为：第62页，共83页，2023年，2月20日，星期五Floyd算法procshortpath_floyd;beginfori:=1tondoforj:=1tondobeginlength[i,j]:=cost[i,j];iflength[i,j]<maxthenpath[i,j]:=[i]+[j];end;fork:=1tondofori:=1tondoforj:=1tondo

iflength[i,k]+length[k,j]<length[i,j]thenbeginlength[i,j]:=length[i,k]+length[k,j];path[i,j]:=path[i,k]+path[k,j];end;end;其中：cost为邻接矩阵；path[i,j]：表示顶点i到j的最短路径；length[i,j]：第63页，共83页，2023年，2月20日，星期五练习7：Floyd算法练习【问题描述】从文件中读入带权图的信息，按Dijkstra算法根据给定源点求出从源点到该图中其余顶点的最短路径。【输入文件】第一行：一个整数L：L=0表示无向图，L=1表示有向图；第二行三个整数m、n，分别表示图的结点数和图中的边数。以下n行表示n条边：每一行三个数x、y和z，z表示x与y之间边的权值。第n+2行：整数R，以下R行每行一个整数表示顶点标号作为源点。【输出文件】共R行，每一行的数据表示源点到其余顶点的距离，按顶点编号由小大输出，如果没有路径，输出-1。【示例】输入：1输出：-11050306068-1–1–1203013101530161002353450461054205660215第64页，共83页，2023年，2月20日，星期五拓扑排序

在实际工作中，经常用一个有向图来表示施工的流程图，或产品生产的流程图。一个工作往往可以分为若干个子工程，把子工程称为“活动”。在有向图种若以顶点表示“活动”的网(ActivityOnVertexnetwork),简称为AOV网。第65页，共83页，2023年，2月20日，星期五对于一个AOV网，构造其所有顶点的线性序列，使此序列不仅保持网中各顶点间原有的先后关系，而且使原来没有先后关系的顶点之间也建立起人为的先后关系。这样的线性序列称为拓扑有序序列。构造AOV网的拓扑有序序列的运算称为拓扑排序。某个AOV网，如果它的拓扑有序序列被构造成功，则该网中不存在有向回路，其各个子工程可按拓扑有序序列的次序进行安排。显然，一个AOV网的拓扑有序序列并不是唯一的。第66页，共83页，2023年，2月20日，星期五

对AOV网进行拓扑排序的方法和步骤是：在网中选择一个没有前趋的顶点且输出之；从网中删去该顶点，并且删去从该顶点发出的全部有向边；重复上述两步，直至网中不存在没有前趋的顶点为止。第67页，共83页，2023年，2月20日，星期五图中v1和v6没有前驱，则任选一个。假设为v6，输出v6；在删除v6及<v6,v4>和<v6,v5>之后，只有v1没有前驱；输出v1及删除<v1,v2>,<v1,v3>,<v1,v4>；之后v3，v4都没有前驱，以此类推。可得到拓扑排序结果：v6-v1-v4-v3-v2-v5123456第68页，共83页，2023年，2月20日，星期五拓扑排序算法typearcptr=^arctp;arctp=recordadjvex:integer;nextarc:arcptr;end;vexnode=recordvexdata:integer;indegree:integer;firstarc:arcptr;end;functiontopsort:boolean;begincrt_adjlist(dig);init(top);fori:=1tondoifdig[i].indegree=0thenpush(top,i);m:=0;whilenotempty(top)dobeginj:=pop(top);write(dig[j].data);m:=m+1;q:=dig[j].firtarc;whileq<>nildobegink:=q^.adjvex;dig[k].indegree:=dig[k].indegree-1;ifdig[k].indegree=0thenpush(top,k);q:=q^.nextarc;end;end;ifm<nthenreturnfalseelsereturntrue;end;其中，dig为邻接表；top为栈；第69页，共83页，2023年，2月20日，星期五拓扑排序改进算法proctoposort(GL);{对邻接表进行拓扑排序}begintop:=0;fori:=1tondoifGL[i].indegree=0then[Gl[i].indegree:=top;top:=i;]m:=0;whiletop<>0dobeginj:=top;top:=GL[top].indegree;write(GL[j].data);m:=m+1;p:=GL[j].firstarc;whilep<>nildobegink:=p^.adjvex;GL[k].indegree:=GL[k].indegree-1;ifGL[k].indegree=0then[GL[k].indegree:=top;top:=k;]p:=p^.next;end;ifm<nthenwriteln("thenetworkhasacycle");end;end;第70页，共83页，2023年，2月20日，星期五该算法不用栈实现，对于入度为0的顶点，利用顶点的indegree域，将所有的入度为0的顶点利用静态链表的形式组织起来。第71页，共83页，2023年，2月20日，星期五练习1：拓扑排序处理【问题描述】从文件中读入AO网的信息，求出该网的一个拓扑排序序列。（注意：有向图）【输入文件】第一行两个整数m和n，分别表示网的结点数和网中的边数。以下n行表示n条边：每一行两个数x和y，表示x与y之间有一条边。【输出文件】只有一行。如果不能进行拓扑排序，输出：can’tsort；否则，输出该网的拓扑排序序列。【示例】输入：68输出：6132451213143235456465第72页，共83页，2023年，2月20日，星期五逆拓扑排序对AOV网进行逆拓扑排序的方法和步骤是：在网中选择一个没有后继的顶点且输出之；从网中删去该顶点，并且删去以该顶点作为弧头的全部有向边；重复上述两步，直至网中不存在没有后继的顶点为止。第73页，共83页，2023年，2月20日，星期五练习2：逆拓扑排序练习【问题描述】从文件中读入AO网的信息，求出该网的一个逆拓扑排序序列。（注意：有向图）【输入文件】第一行两个整数m和n，分别表示网的结点数和网中的边数。以下n行表示n条边：每一行两个数x和y，表示x与y之间有一条边。【输出文件】只有一行。如果不能进行逆拓扑排序，输出：can’tsort；否则，输出该网的逆拓扑排序序列。【示例】输入：68输出：5462311213143235456465第74页，共83页，2023年，2月20日，星期五练习3：软件安装盘软件安装通常是一件令人头疼的事。软件一般都包括若干个相对独立的部分（称为“组件”），在安装的时候由用户决定安装哪些部分。并且，这些相对独立的组件之间在安装时有一定的先后顺序要求。由于当代的个人计算机普遍安装了软盘驱动器，所以软件的最流行的载体形式是软盘。然而，由于软盘的容量有限，稍大一些的软件就无法用一张软盘装下。这时，这些软件往往要用很多张软盘来存储。每张磁盘上存储了软件的一个或多个组件。这些软盘称为软件的安装盘。由于软件的各个组件分散在不同的软盘上，而在安装时又有一定的先后顺序要求，所以很容易发生要求用户反复换盘的情况。而计算机用户在安装软件的时候，最反感的就是反复在软盘之间切换：找盘、插盘、取盘、找盘、插盘、取盘、…，一切都显得那么琐碎和无序。因此，有必要对软件安装盘的制作提出下述要求：永远不要让用户将一张磁盘插入两次。更精确地，要求对安装盘从1开始顺序编号，使得安装的时候，用户只要按顺序插入磁盘即可。出于经济的考虑，通常要求安装盘的总数最少。写一个程序，对于给定的软件，制定最优的安装盘方案。输入输入文件的第一行是一个正整数M（1<=M<=109），给出了每张磁盘的最大容量（字节数）。输入文件的第二行是一个正整数N（1<=N<=100），给出了软件的组件数。接下来的N行每行给出一个组件的详细信息。包括：组件所占的字节数；在安装该组件之前应先安装的组件序号（如有多个组件须先安装，则每个都应列出其序号，若无须先安装其它组件，则该行只含组件所占字节数）。输入文件中同一行相邻两项之间用一个或多个空格隔开。输出输出文件的第一行给出了最优安装盘方案的软盘数。如果不存在最优安装盘方案，则输出0。接下来的每一行顺序给出了每张盘上存储的组件的序号。如果一张盘上存储了多个组件，则输出所有这些组件的序号，中间用一个空格隔开。样例输入1457664351266591234518325421样例输出2123第75页，共83页，2023年，2月20日，星期五关键路径由于在AOE-网中有些活动可以并行的进行，所以完成工程的最短时间是从开始点到完成点的最长路经的长度（指的是路径上各活动持续时间之和，不是路径上弧的数目），路径上最长的路径叫做关键路径。假设开始点是v1，从v1到vi的最长路径长度称为事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示活动的最早开始时间。用e(i)表示。再定义一个活动ai的最迟开始时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最迟必须开始的时间。l(i)-e(i)是完成活动ai的时间余量。l(i)=e(i)的活动叫关键活动。关键路径上的活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。第76页，共83页，2023年，2月20日，星期五结点表示事件，弧表示活动。如下图中的网，从v1到v9的最长路径是(v1,v2,v5,v8,v9),路径长度为18，即v9的最早发生时间是18。而活动a6的最早开始时间是5，最迟开始时间为8。分析关键路径的目的是辨析哪些是关键活动，以便争取提高关键活动的工效，缩短整个工期。123456789a3=5a1=6a2=4a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第77页，共83页，2023年，2月20日，星期五寻找关键活动判别关键活动即是找e(i)=l(i)的活动。为了求AOE-网中活动的e(i)=l(i),首先应求得事件的最早发生时间ve(j)和最迟开始时间vl(j)。如果活动ai由<j,k>表示，其持续时间记为dut(<j,k>),则有：e(i)=ve(j)l(i)=vl(k)-dut(<j,k>);求ve(j)和le(j):(1)从ve(1)=0出发向前推进：ve(j)=Max{ve(i)+dut(<i,j>)},<i,j>€T,2≤j≤n其中，T表示所有以j为头的弧