第科技学院计算机学院

Office:9栋楼9-206（网络教研室•: 課件PPT下載：第6章图6.1图6.1图(注:顶点(Vertices)和边V：顶点(数据元素)的有穷非空集合E：边的有穷 表示圖形所有頂點的集合V(G)={V1,V2,V3,…,Vm}，其中表示圖形所有邊的集合E(G)={E1,E2,E3,…,En}，其中 无向图(Undigraph)每条边都是无方向 有向图(Digraph

每条边都是有方

图的定义和基本图的定义和基本案例引图的类 图结图的遍图的应案例分析与教学目1.掌握：图的基本 熟练掌握：最短路算法（Dijkstra算法图的定义和基图的定义和基2.图的基如果无向图中任意两个顶点间都存在边，则称之为无向完全图(CompletedGraph)。在一个含有n个顶点的无向完全图中，边数为n(n-1)/2条。如果有向图中任意两个顶点间都存在方向互为相反的两完全图：任意两个点都有一条边无向完边(Edges)是没有方向性边(V1,V2)与边(V2,V1)是相同并且边以()表示

有向完边(Edges)是有方向性边<V1,V2>与边<V2,V1>是不相的。边以<>表示。<V1,V2>，其中图的定

图的定义和基本2.图的基 之间的连线记为有序偶对<vi，vj，其中顶点vi称为初始点(弧E2={<v1,v2>,<v2,v1>,<v2,v3>,<v1,v3>}，以弧<v1,v3>【举【举例1】假设有一个无向图形，如下图所示ABCDE请问，此无向图形的顶点(V)和边(E)如何【解答E(G)={(A,B),(A,C),(B,A),(B,D),(C,A),(C,E),(D,B),(D,E),(E,C)有向【举例2】假设有一个有向图形，如下图A

请问，此有向图形的顶点(V)和边(E)如何表示呢稀疏图：有很少边或弧的图。当一个图中含有较少的，则称之为稀疏图(SparseGraph)稠密图：有较多边或弧的图。当一个图接近完全图时，称之稠密图(Dense网：边/弧带权的图。在边或者弧上的数据信息称为边的权Nwok。邻接：有边/弧相连的两个顶点之间的关系。无向图中存在(vi,vjvj邻接于vi。无向

有向图的定

图的定义和基本2.图的基

点v和w互为邻接点；和顶点v关联的边的数目定义为v；顶点的入度(InDegree)是以顶点v为弧头的弧的数目，记ID(v)；顶点的度记为TD(v)，例：ID(V2)=2，TD(v)=OD(v)+图的2.图的基本术vvPhvvvi,imv(，v,i，v)和(vi,j，vi,j+1)∈E，1≤j≤m-1都是图中的边。路径的长度是路径上的边或弧的图的定2.图的基路径：接续的边构成的顶点序路径长度：路径上边或弧的数目/权值之和回路(环)：简单路径：简单回路简单环：path在图形G中，相异两点间所经过的边称为路径，如下图中，A到E的径有{(A,B),(B,E)}、{(A,C),(C,E)}或{(A,B),(B,D),(D,E)}等路径，它有一条路径A AAsimplepath指除了起点(第一个节点)与终点(最后一个节点)外的所有节点都不相同的路径。亦即路径不会有循环现象起点及终点的A中，{(,BDE,,A起点及终点，所以是一个。AABCBCDEDE图图上图(B)的A为简单路径，路径CEB为简单路径BDE,B就不是简单路径(即为循环路径)循环循环cycle起点和终点皆相同的路径。例如下图的{B,D, ,B}起点及终点都是BAABBCDE图的2.图的基都是连通的，则称图G为连通图(ConnectedGraph)。量(ConnectedComponent)；连通图的连通分量是它本身图的图6.3连通图 图的定义和基图的2.图的基有向图G中，如果从vi到vj有路径，则称顶点vi和顶点vj是连通的；若图中任意两个顶点之间都存都有路径，则称此有向图为强连通图。有向图中的极大连通子图称作该有向图的强连通分量。例如，图6.5中的G5就是一个强连通图。而G6就是非图的定义和基图的2.图的基 图G6及两个连通分连通图（强连通图（Strongly在无（有）向图GVE中，若对任何两个顶点v、u存在从v到u的路径，则连通图（强连通图（Strongly 图 图无向图G的极大连通子图( alconnectedsubgraph)称极大连通子图意思是：该子图G通子图，将G任何不该子图中的顶点加入，子图不再连通非 V1图 V2

连通分 强连G的极大强连通子图称为G强连强连通分图的定义和基图的2.图的基本术V2⊆V1，E2⊆E1，即V2为V1的子集，E2为E1子子两GV，{）、G（V，E），若V V，E1称G的。例:(b)、(ca子 图的定义和基图的2.图的基连通图G的生成树，是包含G的全部n个顶点的一个极小连点之间有了第二条路径。一棵有n个顶点的生成树有且仅有(n-1)条边。如果一个图有n个顶点和小于(n-1)条边，则是非连通图。如果它多于(n-1)条边，则一定有环。但图的定义和基图的定义和基2.图的基本术如果一个有向图有且仅有一个顶点的入度为0，其他顶点的入度均为1，则这个图是一棵有向树。当一个有向图有多个顶点的入度为0时，它的生成森林则由多棵有向树构成。这个生成森林含图的定义和基图的定2.图的基图6.7连通图G3的生成 图6.8有向图G7及生成森极小连通子图：该子图是G的连通子图，在该子删除任何一条边，子图不再连通生成树：包含无向图G所有顶点的极小连通子图。集合连通图 G1的生成6.2图的定义和基本图的定义--2.图的抽象数据类型定ADT类型标识符CreateGraph(&G,V,VR)//初始条件：V是图的顶点集，VR是图中弧(或InitGraph(&g); /*初始化图即构造一个空图*/) 图的定义和基图的定义图的定义和基GetVex(G,x);//在图G中查找到顶点x并返回x的值PutVex(&G,v,value);/*为顶点v赋值*/

图的定义--2.图的抽象数据类型定InsertArc(&G,v,w);//若G是有向图，则增加弧//若G是无向图，则增加弧<v,w>和DeleteArc(&G,v,w);//若G是有向图，则删除弧//若G是无向图，则删除弧<v,w>和 //返回v的第一//若没有邻接NextAdjVex(G,x,w);//返回v的(相对于w的)下一个邻//若w是v的最后一个邻接顶点图的定义和基图的定义--2.图的抽象数据类型定}ADT

V(G)是顶点有限集合，常用字母或者自然数(顶点)来标识图中顶点。规定第i个顶点，即为i的顶点用vi表示；E(G)是图中边的集合，它确定了图G的数据元间的关系。6.36.3(5)图的初始条件：图G存在操作结果：对图进行深度优先遍初始条件：图G操作结果：对图进行广度优先遍6.4图 顺 结构 数组表示法（邻接矩阵链 结构 多重链邻邻接邻接多链邻接矩阵(数组)表示邻接邻接矩

图 与操–邻接矩阵（AdjacencyMatrix）是用两个数组来 数组（邻接矩阵）表示 设图AVEn个顶点，则图的邻接矩阵是一个二维数组A.Edge[n][n]，定义为：AA.Edge[i][j]<i,j>E或者(i,j否则无向图的邻接矩阵表示 顶点表：（v1v2v3v4 A.Edge 分析1：无向图的邻接矩阵是对称分析2：顶点i的度＝第i1的个数；有向图的邻接矩阵表示 A

A.Edge=

(v1v2v3v4 注：注： 顶点的入度=第i列 顶点的度=第i行 和+第i列 图图与操邻接矩法法网（ 图）的邻接矩阵表示 无边（弧定义为：A.Edge[i][j <vi,vj>或（vi, 无边（弧

(0

v2

v4v5v6 ∞

N.Edge

∞0 ∞∞8∞0∞∞∞ ∞∞∞ 03∞∞ 图的与操邻接矩阵--2.网的邻接矩00000000 00 00 0图 与操邻接矩阵--3.邻接矩阵表示法的特 。图 与操邻接4.邻接矩阵表示法的优缺–用邻接矩阵方法图，很容易确定图中任意两个顶点之间是否有边相连（邻接），但要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大，同时，邻接矩阵空间为O(n2)，所以适用于稠密图。邻接矩阵 表//用两个数组分 顶点表和邻接矩#defineMaxInt#defineMVNum100typedefintArcType;typedefstruct{

//表示极大值，即//最大顶//假设顶点的数据类型为字//假设边的权值类型为整 //

//邻接//图的当前点数和边图 与操邻接矩阵--5.算法6.1 inti;if(G.vexs[i]==v)returni;return-1;}图 与操邻接矩阵--5.邻接voidDisplayAdjMatrix(AMGraphG) int }//for

图 与操邻接矩阵--5.邻接矩阵操voidCreateUndirectedGraphAdj(AMGraph intVerTexTypefor(k=0;k<pg- {//

//边数图 与操邻接矩阵--5.voidCreateUndirectedGraphAdj(AMGraph //pg->arcs[i][j]=1;pg-pg->arcs[i][j]=w;pg-pg->arcs[i][j]=1;/*创建有向图的邻接矩阵*/pg->arcs[i][j]=w;*创建有向网的邻接矩阵*/} 45ABCABA45ABCABACADBCCD【算法思输入总顶点数和总边数依次输入点的信息存入顶点表初始化邻接矩阵构造邻接矩阵45A45ABCABACADBCCDStatusCreateUDN(AMGraph//采用邻接矩阵表示法，创建无向网 for(i=0;i<G.vexnum;++i)for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)G.arcs[i][j]=MaxInt;for(k=0;

//输入总顶点//依次输入//初始化邻接矩阵，边的权值均置为极大//构造邻接矩//输入一条边依附的顶点及iLocateVex(Gv1);jLocateVex(Gv2);//确定v1和v2在GG.arcs[i][j]=w;//边<v1,v2>的权值置为return

//置<v1,v2>的对称边<v2,v1>的权值为45ABCA45ABCABACADBCCDinti;returni;return-1;}邻接矩阵表 图 与操图的邻接 邻接表(AdjacencyList)是图的一种顺序 图 与操邻接表--1.图的邻接 的边结点，info域和边或弧相关的信息，如权值。图6.11邻接表（链式）表示 表结对每个顶点建立一个单链表表结头结每个单链表有一个头结点（设为2个域），存Vi信息每个单链表的头结点另外用每个单链表有一个头结点（设为2个域），存Vi信息每个单链表的头结点另外用顺结。储顶点vi信

数据域，边有关信（如权值无向图的邻接表 0 1

3 1^31^

注：邻接表不唯一，因各个边结点的链入顺序是任空间效率为O(n+2e)若是稀疏图(e<<n2)，比邻接矩阵表示法O(n2)省空TD(Vi)=单链表 的结点个图 与操邻接表--3.无向图的邻接 法的特（1）第i个链表中结点的数目为第i 图 与操邻接表--–有向图的邻接表不方便查找以vi为弧头的节点数，为2121102002 102002 (a)无向图G1的邻接 1

01无向图01

10(c有10

有向图–仅以顶 作为信息输入，时间复杂度为O(n+e)^有向图的邻接表^空间效率为

邻接^ 2 1^210^0^

逆邻接3^0^0^2^^3^3出度OD(Vi)＝单链出边表中 入度ID(Vi)＝邻接点域为Vi的弧个数度：TD(ViODVi+IDVi图 与操邻接表--4.有向图的邻接 法的性 已知某网的邻接（出边）表，请画出该网1152

邻接表 表#defineMVNum //最大typedefenum{DG,DN,UDG,UDN}typedef int ode*OtherInfo typedefstructode*}VNode,typedefAdjListint GraphType

//边结//该边所指向的顶点的//指向下一条边的指//和边相关的//顶点信//指向第一条依附该顶点的边的//AdjList表示邻接表类//邻接//图的当前顶点数和//图的类型采用邻接表表示法创【算法思NU。 for(i=0;i<G.vexnum;++i){cin>>G.vertices[i].data;for(k=0; i=LocateVex(G,v1);j=LocateVex(G,//将新结点

////////生成一个新的边结点//邻接点序号为p1->nextarc=G.vertices[i].firstarc;//将新结点

//邻接点序号为p2->nextarc=G.vertices[j].firstarc;return邻接表表示法的特 优点：空间效率高，容易寻找顶点的邻接邻接矩阵与邻接表表示法的^1^123^024^134^024^1312（v1v2v3v4 0101010101010111010101110邻接矩阵与邻接表表示法的关 区别 接矩阵的空间复杂度为O(n2),而邻接表的空间复图 与操邻接表--邻接表intLocateVex(ALGraphG,VerTexType inti;if(G.AdjList[i].data==v)returni;return-1;图 与操voidCreateUndirectedGraphLink(ALGraph intVerTexTypeodefor(i=0;i<=pg- /*n为顶点数 scanf("%c",&pg->AdjList[i].data);/*构造顶点信息pg- }//forfor(k=0;k<pg-

/*e为边数/*确定两个顶点在图G中的位置 /*创建无向图的邻接表 ode ode));s-s->nextarc=pg->AdjList[i].firstarc;pg-图 与操)voidCreateUndirectedGraphLink(ALGraph ode ode));s-s->nextarc=pg->AdjList[j].firstarc;pg-/*创建有向图的邻接表 ode ode));s-s->nextarc=pg->AdjList[i].firstarc;pg-/*创建有向图的逆邻接表 ode ode));s-s->nextarc=pg->AdjList[j].firstarc;pg-}//for图 与操voidDisplayAdjList(ALGraph intodeprintf("for(i=0;i<G.vexnum;i++){while(p!=NULL){printf("->%d",p->adjvex);p=p-链表(OrthogonalList)--用于顶点结点表中的结(节)vex:顶点的数据域，保存顶点的数firstin:顶点的指针域，指向第一个以为弧头(head)的弧结

firstout:顶点的指针域，指向第一个vex为弧尾(tail)的info:弧的数据域(如权值)，保存弧的权值等tailvex:弧尾结点(tail)的位(地址)headvex:弧头结点(head)的位(地址)

hlink:指向相同弧头结点(head)下一个弧结点tlink:指向相同弧尾结点(tail)下一个弧结点链表(Orthogonal链表(OrthogonalList)--图 与操 typedefstruct inttailvex,headvex;odechar VexInfo

/*最大顶点数/*标记和边(或弧)的相关信息/*顶点的信息ode*firstin,*firstout;//标记vi的第一}VexNode /*顶点数和边数图 与操链表--图 /*建立有向图 链表。{ for(i=0;i<G.vexnum;i++){

um;j++){

}//for ode ode}; G.vexs[n].firstout=p;}}

//for

//将p连 建 链表的时间复杂度是O(n+e)图 与操 #defineMAX_VERTEX_NUMintstructArcBox

/*最大顶点数infoTypetypedefstructVexNode{VextexTypevex;

/*标记和边(或弧)的相关信息//顶点的信息 称用ArcBox*firstin,*firstout;//标记vi的第一个邻接节点的指VexNode /*顶点数和边数邻接多重表---用于无data:结点的数据域，保存结点的数据值firstedge:结点的指针域，给出自该结点出的第一条边的边结点的地址边结ivex:本条边依附的一个结点的地址ilink:依附于该结点（地址由ivex给出）jvex:本条边依附的另一个结点的地

info:边结点的数据域，保存边的过过邻接多重6.56.5 以及船上传教士人数不能少于野人以及船上传教士人数不能少于野人在每一次渡河后，都会有几种渡河方案供，究竟哪种方案最有利？这就是搜依靠经验，利用已有知识，根据问题的实际情况，

解路搜索空全状态空 8在一个3×3的方框内放有8个的小方块，紧邻空位的小方块2323765搜索引擎的两种基本抓

搜索引擎蜘蛛通 网页，获得页 后 爬行索排序返搜索引擎的搜索引擎的两种基本抓位的继搜索引擎的两种基本抓

的规两种策略结合=先广后深 URL的权重高，就采用深URL权重低，就采用宽度优先或者不 初始状态为i ，改visited[i]为1，防止被多图图常用的遍深度广度深度优先搜DFSDepth_First基本思想：——仿树的先序起起DFSv1→v2→v4→v8→v5→v3→v6→v7深度优先搜索的步 简单起始点 深度优先搜索练 142142365深度优先搜索的步 详细在图中某一起始顶点v，由v出发，它的任一邻接起 点再从w1出发，与w1接但还未被过的顶点然后再从w2出发，进行类似的邻接顶点都被过的顶点u深度优先搜索的步 详细 过的顶点，看是否还有起 它没有 的邻接顶点如果有， 此顶点，之 如果没有，就再退回一步进图中所有顶点都 过为止123456101110123456101110021000103100010410000150110006000100123456

——开辅助数组visited[n0001110101110000000000111010111000000010000110000111110111111邻邻142365DFSDFS讨论2：DFS算法如何编程？——可以用递归算voidDFS(AMGraphG,intv){cout<<v;visited[v]=true;for(w=0;w<G.vexnum;w++)

//图G为邻接矩阵 第v//依次检查邻接矩阵v所在的if((G.arcs[v][w]!=0)&&(!visited[w]))DFS(G,w);//w是v的邻接点，如果w ，则递归调用}讨论3：在图的邻接表中如何进行DFS？—照样借用visited[n0起 23DFSv0→v1→DFSv0→v1→v2→00001000001000110011101111123讨论4：邻接表的DFS算法如何编voidDFS(ALGraphG,intv){cout<<v;visited[v]=true;

——仍可用递归算//图G为邻//第v个顶if(!visited[w])DFS(G,w);}}

//边结点//表示w是v的邻接//如果w未，则递归调用//p指向下一个边结DFS算法效率分 用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加 问n个广度优先搜BFSBreadth_First基本思想：——仿树的层次遍历过起BFSv1→v2→v3→vvv6→v→v8广度优先搜索的步 简单 了起始点v之后，依 v的邻接点然后再依 这些顶点中未 过的邻接点直到所有顶点都 过为止 1从图中某个顶点v出发 v，并visited[v]的值为true，然后将v进队②依次检查u的所有邻接点w，如果 辅助队还需再开一辅助队起入队邻邻接v2 过BFS历【算法描述voidBFS(GraphG,intcout<<v;visited[v]=true;EnQueue(Q,DeQueue(Q,

第v个顶//辅助队列Q初始化，置//v//队列非//队头元素出队并置为 //w为u的尚 的邻接顶cout<<w;visited[w]=

EnQueue(QwwBFS算法效率分 如果使用邻接矩阵，则BFS对于每一个 到的顶，都要循环检测矩阵中的整整一行（n个元素），总用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加问n个头结点的时间，练 深度先搜索从顶点3121256^2^14^^1^3562345^6^DFS与BFS算法效率比 空间复杂度相同，都是O(n)(借用了堆栈或队列 补充：ACM算法设计-- 6.66.6最短拓扑关键最小生成 生成树：包含图G所有顶点的极小连通子图（n-1条边）连通

G1的生成画出下图^1^123^024^134^024^13邻接表无向无向连4生

生 求最小生成 首先明确有n个顶点、n-1条边。目目标构造最小生成树的准 必须只使用该网中的边必须使用且仅使用n-1条边来联结网络中的n个不能使用产生回路最小生成树的典型用 城市可能有n(n-1)/2条线路，那么，如何选择n–1条线路，使总费用最显然是一个生成树数学补充：贪心算法(Greedy。找零钱问题这就是在使用Knapsack问题(0/1 假设小偷的背包可裝30物價重单6371以贪婪算法的观念来看,第一步要最佳效益的商品2我们知道,物品1最划算,故5公斤全背包.(背包还可以装25公斤3再来考虑物品3,一样全部放入背中.(背包还可以装5公斤4最后考虑物品2,再放入5公斤的物品即完5最大利益为220物價重单637若此若此时商品改成不可分割,也就是说,对一个商品来要不就是全取,要不就是不此时,贪婪算法不一定能求得最大利因为：小偷的背包可以装下30因为：小偷的背包可以装下30物價重1523贪贪婪算法:先取物品1,再取物品3;但物品2,不可再选否则背包会断故以贪婪算法所得到的最好的利益为190但最佳的利益为物品2+物品3=200Knapsack问题(0/1 (Knapsack– fractionalknapsackproblem(OptimalKnapsack问题(0/1 Knapsack问题(0/1 Approximatesolutions,选取C选取CABE-D选取CEDBA--选取ABCDE--123Prim（普里姆）Kruskal（克鲁斯卡尔）Prim算法:归并顶点，与边数无关，适于Kruskal算法：归并边，适于稀疏普里姆算法的基本思想－－归并顶 NVE1.从某顶点u0出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合2.每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点3.直到所有顶点都加入到生成树顶点集合UT(G)=应用普里姆(Prim)算法构造最小生成ExampleforExamplefor克鲁斯卡尔(Kruskal)算法的基本思想－NVE1.n个顶点，没有边T={V,},每个顶点自 通分量2.E中选最小权值的边,若该边的两个顶点落在不同的连通分量上，则加入T中；否则舍去，重3.重复下去，直到所有顶点在同一连通分量上T(G)=O(|e|log应用克鲁斯卡尔算法构造最小生成树 √ExampleforExamplefor ysisofAlgorithms-Chapter BB）两种常见的最短

EdsgerW.一、单源最短路径—用Dijkstra（迪杰斯特拉）算RobertW.二、所有顶点间的最短路径—用Floyd（弗洛伊RobertW.一顶点到余各顶

最短路 型应用--计算机网络路最短路 型应用—机器人探型应用—游戏型应用—游戏开最短路DijkstraDijkstra算A*算Dijkstra算法的改进—A*算法（静Dijkstra算法的改进—A*算法（静态环境

Dijkstra算法的改进—D*算法（动态环境 学D*

型应用—火星探测从v0到其余各点的最短路径--按路径长度递增次序求 (v0,(v0,(v0,v4,(v0,v4,v3,无∞504315 504315

1060

0Dijkstra算法的思 504315 504315 选择：从这些路径中找出一长度最短的路径（v0,u）若在图中存在弧（u,vk）则以路径（v0,u,vk）（v0,vk）在调整后的各条路径中，再找度最短的路径，依此类推结构结构（顶点个数为主：邻接矩阵G[n][n](或者邻辅–数组S[n]：记录相应顶点是否已被确–数组D[n]：记录源点到相应顶点路径长 –数组Path[n]：记录相应顶点的前驱

0 1

5 5算法初始化结

212v=v=v=v=v=v=SD0∞∞−0−00【算法思初始化将v0D[i]=G.arcs[v0][vi]，(vi∈V−如果v0和顶点vi之间有弧，则将vi的前驱置为v0Path[iv0，否则Path[i1②选择下一条最短路径的终点vkD[k]=Min{D[i]|vi∈V−【算法思想】 i

k若S[i]=falseD[k]+G.arcs[k][i]<D[i]，则D[i]=D[k]+G.arcs[k][i];Path[i]=k;。⑤重复②～n−1次，即可按照路径长度的递增，逐个求得从v0到图上其余各顶点的最短路径Dijkstra算法的思 ABCABCDEFGH例5例504315 (v0,v2)+(v0,v2)+ 从v0到各终点的长度和最短路∞∞∞∞∞{v0,{v0,{v0,v4,s{v0,v200 30

S之外的当前短路径之顶S之外的当前短路径之顶 0算法流程求最短长度

初始化过程初始化过程 minmin=INFINTY;w< ! D[w]<v=w;v=w; 更新v0到V-S中顶点的

w<G.vexnum S[v]=true;!S[w] S[v]=true;Y【算法描voidShortestPath_DIJ(AMGraphG,int//用Dijkstra算法求有向网G的v0顶点到其余顶点的最短for(v=0;v<n;++v){S[v]=false;D[v]=

//n为G中顶点//n个顶点依次初始//S初始//将v0到各个终点的最短路径长度初if(D[v]<MaxInt)Path[v]=v0;//v0和v之间有弧，将v的前驱置为elsePath[v]=-

//如果v0和v之间无弧，则将v的前驱置为-//将v0加入//源点到源点的距离为

时间复杂度/*―开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集for(i=1;i<n;++i){min=MaxInt;{v=w;

//对其余n−1个顶点，依次进行计//选择一条当前的最短路径，终点为//将v加入for(w=0;w<n;++w)//更新从v0出发到集合V−S上所有顶点的最短路径长Path

//更新//更改w的前驱为AllpairsshortestFloyd’sAlgorithm:AllpairsshortestInaweightedgraph,findshortestpathsbetweeneverypairofSameidea:constructsolutionthroughseriesofmatricesD(0),D(1),…usinganinitialsubsetoftheverticesasintermediaries.43164316115234Floyd’sFloyd’sAlgorithm:AllpairsshortestBottom-upapproachObjectivefunction:LetAk(i,j)=lengthofashortestpathfromvertexitovertexjwithintermediatenodevk.RecurrencerelationAk(i,j)=Min{Ak-1(i,j),Ak-1(i,k)+Ak-1(k,j)Boundarycondition:A0(i,j)=c(i,j) i,j.Answer:An(i,Timecomplexity:Spacecomplexity:Floyd’sFloyd’s59ExampleforFloyd’s59ExampleforFloyd’s469469ExampleExampleforFloyd’s77用有向图来描述一个工程或系统的进行一个工程可以分为若干个子工程，只要完成了这些子（活动），就可以导致整个工程的完①AOV网Vertices)—用顶点表示活动的网②AOE网Edges)—用边表示活比比如教学计划的哪些课程是必须先修的，哪些课程是可以并行学习的在游戏的情中，描述各个分支情节之间的关分支情节之间，存在着一定的先决条件约束，即有些情节必须在其他情节完成后方可开始发展，而有些分在AOV网中，不应该出现有向环路，否则，顶点的后关系就会进入死循环。即情节将不能正确发情情情先决条遭遇强无受买看医治情 情 先决条遭遇无受买治教学计划的高等C1,C2C3,C2C5,C4C4,C9对学生选课工程图进行拓扑排序，得到的拓扑有序序C1,C2,C3,C4,C5,C6,C8,C9,或C1C8C9C2C5C3C4C7离散

数据程序学生课程学习工SourceremovalalgorithmforTopologicalsorting拓扑拓扑排序算法的思想－重复选择没有直接前思想－思想－重复选择没有直接前驱的顶点，即V(in-(i.e.source-removal输入AOV网络。令n为顶点在AOV网络中选一个没有直接前驱的顶点,并输出之从图中删去该顶点,同时删去所有它发出的有向边重复以上2、3步直到AO拓扑排序的过 最后得到拓扑C4C0,C3,C2,C1C5。满足图Solutionfor1-(1).ApplytheDFS-basedalgorithmtosolvethesortingproblemforthefollowingdigraphs:(a)andSolutionfor1-(1).ApplytheDFS-basedalgorithmtosolvethesortingproblemforthefollowingdigraphs:(a)andSolutionfor1-(2).Applythesource-removalalgorithmtosolvethesortingproblemforthefollowingdigraphs:(a)andSolutionfor Applythesource-removalalgorithmtosolvethetopologicalsortingproblemforthefollowingdigraphs:(a)and(b).关键AOE网络：定义结点为事件，有向边的指向表示事件的执行次序。单位是术语ABAB活动（有向边）：它的权值定义为活动进行所需要的时间。方起始结点事事件的最早发生时间（Ve(j)）：从起点到本结点的最长的路径。意味事件的最迟发生时间（Vl(j)）：不影响工程的如期完工，本结点事件必jjk活动的最早开始时间：eaiVej活动的最迟开始时间：laiVlkdutjk关键事件的最早发生时间（Ve(j)）：从起点到本结点的最长的路径。意味着事件能够发生的时(AB的AB活动的最早开始时间：e(aiVejjk活动的最迟开始时间laiVlkdutjjk关键活动：最早开始时间＝最迟开始时间2437Vn关键路径：从源点到收点的最长的一条路径，或者全部由2437Vn1起点 Ve(Vj)881、5、12、88的最大值

Vl(Vj)=取10-2、10-4、10-3、10-7小值310长路径起点

Ve(j)及Vl(j)）的求 收

37

VnVe(Vj)=3、5、12、88的最大值

Vl(Vj10-2、10-4、10-

、10-7的最小值

收

Vj

Vn Ve(Vj)=Vj的起始结点的最早发生时间+各自的边的权值中的和的最大值88

Vl(Vj终止结点的最迟发生时间-各自的边的权值的差的最小值3 0 0 0

10V15

131

212

57、

1、设每个结点的最早发生时间为0，将入为零的结点进2、将栈中入度为零的结点V取出，并一栈，用于形成逆向拓扑排序的序列。3、根据邻接表找到结点V的所有的邻，将结点V的最早发生时间+活动的权值得较；如果该值大，则用该值取代原最早发 55正向拓扑排序

4、反复执行2、3；直至栈空为 0 V1350

0StatusTopologicalsort（StatusTopologicalsort（ALGraphG,Stack{//对各顶点求入度，建立入度为零的栈Initstack（T）；count=0;ve[0..G.vexnum-1]=0;whilefor（p=G.vertices[i].firstarc;p;p=p-{k=p-if（!（--indegree[k]））Push（S,k）;if（ve[j]+*（p->info）>ve[k]）ve[k]=ve[j]+*（p->info）;}}if（count<G.vexnum）returnERROR;elsereturnOK;}//栈T为求事件的最迟发生时间11 13

21

3257V15

15

22正向拓扑排序8 28 8

利用V1358

22

迟发生时间的执行步1、设每个结点的最迟发生时间为收点10、00V1、5

V243、1V3、165

V5 22

V6

的最早发生2、将栈中的结点V3、根据逆邻接表找到结点V的所有的起始结点，将结点V的最迟发生时间-4、反复执行2、3；直至栈空逆向拓扑排序：实例的事件结点的最早发生时

最早

最迟Vl(k)-dut(j,k21 26 3

关键活V1355

23261011V1 3261011V1 2 2551

关键活关键活 11 3

216 V13 5 55关键例8-7对于图8-17所示的AOE网，要求计算各个事件vk的最早开始时间计算各个事件vk的最晚发生时间计算各个活动ai的最早开始时间计算各个活动ai的最晚开始时间

v3v

关键例8-7对于图8-17所示的AOE网，要求计算各个事件vk的最早开始时间最早开始时间事057给出整个工关键例8-7对于图8-17所示的AOE网，要求计算各个事件vk的最晚发生时间最晚发生时间事07关键例8-7对于图8-17所示的AOE网，要求计算各个活动ai的最早开始时间最早开始时间活00577关键例8-7对于图8-17所示的AOE网，要求计算各个活动ai的最晚开始时间最晚开始时间活507关键例8-7对于图8-17所示的AOE找出所有 关键活动有a2,a4,a6,a9,a13a2,a4,a6,a10,a14关键路径为(v0,v2,v3,v4,v6,v9)和(v0,v2,v3,v4,v7,v9)6.7用图G中的一个顶点表示一个人，两个人“认识”与否，用代表这两个人的顶95）99.5%以上的顶点都存在一条路径长度不超过7的路径①ViiNm70；SrtvittrtutrSr队头顶点u出队依次检查u的所有邻接点w，如果visited[w]的值为false，则将w标记为六度顶路径长度不超过7的顶点个数Visit_Num加将w③退出循环时输出从顶点Start出发，到其他顶点长度不超过7的路径的百分【算法描voidSixDegree_BFS(GraphG,int visited[Start]=true;//置顶点 标志数组相应分量值为InitQueue(Q辅助队列Q初始化，置空EnQueue(Q,Start);//Start进队for(len=1;len<=7&&!QueueEmpty(Q);len++)//统计路径长度不超过7的顶点个{DeQueue(Q,u);//队头顶点u//依次检查u的所有邻接点w，FirstAdjVex(G,u)表示u的第一个邻接//NextAdjVex(G,u,w)表示u相对于w的下一个邻接点，w≥0表示存在邻{

//w为u的尚 的邻接顶

//将w//路径长度不超过7的顶点个数加//w}//结束至多7次for//输出从顶点Start出发，到其他顶点长度不超过7}有向图有向图

Dijkstra算Floyd算邻接应无向图的应无向图的应

广度优先搜索最小生

掌握：图的基本概念及相关术语和 熟练掌握：图的两种遍历方法DFS和BFSDFS算法熟练掌握：最短路算法（Dijkstra算法）Howtoconstruct ysisadynamicprogrammingIngeneral,dynamicprogrammingmethodhastwoForwardBackwardHowtoconstruct ysisadynamicObjectivefunction(optimalRecurrenceBoundaryTimeSpace19F