1、Email:李冬梅北京林业大学信息学院图第6章数据结构（C语言版）（第2版）线性结构 一个对一个，如线性表、栈、队列树形结构 一个对多个，如树集合 数据元素间除“同属于一个集合”外，无其它关系图形结构 多个对多个，如图逻辑结构目 录 导 航6.16.26.36.46.56.66.7图的定义和基本术语案例引入图的类型定义图的存储结构图的遍历图的应用案例分析与实现Contents掌握：图的基本概念及相关术语和性质熟练掌握：图的邻接矩阵和邻接表两种存储表示方法熟练掌握：图的两种遍历方法DFS和BFS熟练掌握：最短路算法（Dijkstra算法）掌握：最小生成树的两种算法及拓扑排序算法的思想01OPTI
2、ON02OPTION03OPTION04OPTION05OPTIONtarget目标图的定义和术语V1V2V3V4G1V1V2V4V5G2V3 图：Graph=(V,E)V：顶点(数据元素)的有穷非空集合；E：边的有穷集合。无向图：有向图：每条边都是无方向的每条边都是有方向的完全图：任意两个点都有一条边相连无向完全图有向完全图n(n-1)/2 条边n(n-1)条边图的定义和术语图的定义和术语稠密图有较多边或弧的图。邻接有边/弧相连的两个顶点之间的关系。存在(vi,vj)，则称vi和vj互为邻接点；存在，则称vi邻接到vj，vj邻接于vi 稀疏图有很少边或弧的图。网边/弧带权的图。关联(依附)：
3、边/弧与顶点之间的关系。存在(vi,vj)/，则称该边/弧关联于vi和vj顶点的度：与该顶点相关联的边的数目，记为TD(v)在有向图中,顶点的度等于该顶点的入度与出度之和。顶点 v 的入度是以 v 为终点的有向边的条数,记作 ID(v)顶点 v 的出度是以 v 为始点的有向边的条数,记作OD(v)问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？答：是树！而且是一棵有向树！图的定义和术语路径：接续的边构成的顶点序列。路径长度：路径上边或弧的数目/权值之和。回路(环)：第一个顶点和最后一个顶点相同的路径。简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。简单回路
4、(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径。图的定义和术语 非连通图 连通图 强连通图 非强连通图 V0 V1 V2 V3 V0 V4 V3 V1 V2 V0 V1 V2 V3 V0 V2 V3 V1 V5 V4连通图（强连通图）在无（有）向图G=(V,E)中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图（强连通图）。图的定义和术语(a)(b)(c)V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2子图设有两个图G=（V，E）、G1=（V1，E1），若V1 V，E1 E，则称 G1是G的子图。例:(b)、(c)是(a
5、)的子图权与网图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。图的定义和术语连通分量（强连通分量）非连通图 V0 V2 V3 V1 V5 V4无向图G 的极大连通子图称为G的连通分量。极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通。V0 V2 V3 V1 V5 V4连通分量图的定义和术语有向图G 的极大强连通子图称为G的强连通分量。极大强连通子图意思是：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。强连通分量 V0 V1 V2 V3 V0 V2 V3 V1图的定义和术语极小连通
6、子图：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。生成树：包含无向图G 所有顶点的极小连通子图。生成森林：对非连通图，由各个连通分量的生成树的集合。连通图 G1G1的生成树 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2图的定义和术语目 录 导 航6.16.26.36.46.56.66.7图的定义和基本术语案例引入图的类型定义图的存储结构图的遍历图的应用案例分析与实现Contents六度空间理论你和任何一个陌生人之间所间隔的人不会超过6个，也就是说，最多通过6个中间人你就能够认识任何一个陌生人。目 录 导 航6.16.26.36.4
7、6.56.66.7图的定义和基本术语案例引入图的类型定义图的存储结构图的遍历图的应用案例分析与实现Contents图的类型定义CreateGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DFSTraverse(G)初始条件：图G存在。操作结果：对图进行深度优先遍历。BFSTraverse(G)初始条件：图G存在。操作结果：对图进行广度优先遍历。目 录 导 航6.16.26.36.46.56.66.7图的定义和基本术语案例引入图的类型定义图的存储结构图的遍历图的应用案例分析与实现Contents图的存储结构顺序存储结构数 组 表 示
8、法（邻接矩阵）链式存储结构多重链表邻接矩阵(数组)表示法邻接表(链式)表示法重点介绍邻接表邻接多重表十字链表 ,),(,.否否则则或或者者如如果果01AEjiEjijiEdgev 建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表 示各个顶点之间关系）。v 设图 A=(V,E)有 n 个顶点，则图的邻接矩阵是一个二维数 组 A.Edgenn，定义为：数组（邻接矩阵）表示法邻接矩阵：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：无向图的邻接矩阵是对称的；分析2：顶点i 的度第
9、 i 行(列)中1 的个数；特别：完全图的邻接矩阵中，对角元素为0，其余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顶点表：无向图的邻接矩阵表示法v1v2v3v5v4v4分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点的出度=第i行元素之和 顶点的入度=第i列元素之和 顶点的度=第i行元素之和+第i列元素之和v1v2v3v4A邻接矩阵：A.Edge=(v1 v2 v3 v4)v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0
10、注：在有向图的邻接矩阵中，第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 有向图的邻接矩阵表示法13定义为：A.Edge i j=Wij 或（vi,vj）VR 无边（弧）v1v2v3v4Nv5v65489755邻接矩阵：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 网（即有权图）的邻接矩阵表示法6容易实现图的操作，如：求某顶点的度
11、、判断顶点之间是否有边、找顶点的邻接点等等。n个顶点需要n*n个单元存储边;空间效率为O(n2)。对稀疏图而言尤其浪费空间。邻接矩阵表示法的特点缺点：优点：/用两个数组分别存储顶点表和邻接矩阵#define MaxInt 32767 /表示极大值，即#define MVNum 100 /最大顶点数 typedef char VerTexType;/假设顶点的数据类型为字符型 typedef int ArcType;/假设边的权值类型为整型 typedef struct VerTexType vexsMVNum;/顶点表 ArcType arcsMVNumMVNum;/邻接矩阵 int vexn
12、um,arcnum;/图的当前点数和边数 AMGraph;邻接矩阵的存储表示【算法思想】采用邻接矩阵表示法创建无向网4 5A B C DA B 500A C 200A D 150B C 400C D 600输入总顶点数和总边数。依次输入点的信息存入顶点表中。初始化邻接矩阵，使每个权值初始化为极大值。构造邻接矩阵。Status CreateUDN(AMGraph&G)/采用邻接矩阵表示法，创建无向网G cinG.vexnumG.arcnum;/输入总顶点数，总边数 for(i=0;iG.vexsi;/依次输入点的信息 for(i=0;iG.vexnum;+i)/初始化邻接矩阵，边的权值均置为极大
13、值 for(j=0;jG.vexnum;+j)G.arcsij=MaxInt;for(k=0;kv1v2w;/输入一条边依附的顶点及权值 i=LocateVex(G,v1);j=LocateVex(G,v2);/确定v1和v2在G中的位置 G.arcsij=w;/边的权值置为w G.arcsji=G.arcsij;/置的对称边的权值为w /for return OK;/CreateUDN【算法描述】4 5A B C DA B 500A C 200A D 150B C 400C D 600 int LocateVex(MGraph G,VertexType u)/存在则返回u在顶点表中的下标;否
14、则返回-1 int i;for(i=0;iG.vexnum;+i)if(u=G.vexsi)return i;return-1;4 5A B C DA B 500A C 200A D 150B C 400C D 600【算法描述】v 对每个顶点vi 建立一个单链表，把与vi有关联的边的信息链接起来，每个结点设为3个域；v 每个单链表有一个头结点（设为2个域），存vi信息；adjvex nextarcinfodatafirstarc表结点头结点邻接点域，表示vi一个邻接点的位置链域，指向vi下一个边或弧的结点数据域，与边有关信息（如权值）数据域，存储顶点vi 信息链域，指向单链表的第一个结点v
15、每个单链表的头结点另外用顺序存储结构存储。邻接表（链式）表示法0123413341420注：邻接表不唯一，因各个边结点的链入顺序是任意的v1v2v3v4v5231420无向图的邻接表表示空间效率为O(n+2e)。若是稀疏图(eG.vexnumG.arcnum;/输入总顶点数，总边数 for(i=0;i G.verticesi.data;/输入顶点值 G.verticesi.firstarc=NULL;/初始化表头结点的指针域为NULL /for【算法描述】采用邻接表表示法创建无向网for(k=0;kv1v2;/输入一条边依附的两个顶点 i=LocateVex(G,v1);j=LocateVex
16、(G,v2);p1=new ArcNode;/生成一个新的边结点*p1 p1-adjvex=j;/邻接点序号为j p1-nextarc=G.verticesi.firstarc;G.verticesi.firstarc=p1;/将新结点*p1插入顶点vi的边表头部 p2=new ArcNode;/生成另一个对称的新的边结点*p2 p2-adjvex=i;/邻接点序号为i p2-nextarc=G.verticesj.firstarc;G.verticesj.firstarc=p2;/将新结点*p2插入顶点vj的边表头部 /for return OK;/CreateUDG 采用邻接表表示法创建无
17、向网邻接表表示法的特点优点：空间效率高，容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。缺点：v1v2v3v5v4v44321013341420v5v4v3v2v1231420（v1 v2 v3 v4 v5 ）v1v2v3v4v50 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0邻接矩阵与邻接表表示法的关系1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空
18、间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。邻接矩阵与邻接表表示法的关系2.区别：3.用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图结点表中的结点的表示：data：结点的数据域，保存结点的数据值。firstin:结点的指针域，给出自该结点出发的的第一条边的边结点的地址。firstout：结点的指针场，给出进入该结点的第一条边的 边结点的地址。十字链表-用于有向图datafirstinfirstout边结点表中的结点的表示：info:边结点的数据域，保存边的权值等。tailvex:本条边的出发结点的地址。headvex:本条边的终止结点的地址。hlink:终止结点相同的边中的下一
19、条边的地址。tlink:出发结点相同的边 中的下一条边的地址。十字链表-用于有向图infotailvexheadvexhlinktlink十字链表十字链表-用于无向图结点表中的结点的表示：data:结点的数据域，保存结点的数据值。firstedge:结点的指针域，给出自该结点出发的的第一条边的边结点的地址。datafirstedge十字链表-用于无向图边结点表中的结点的表示：ivex:本条边依附的一个结点的地址。ilink:依附于该结点（地址由ivex给出）的边中的下一条边的的地址。jvex:本条边依附的另一个结点的地址。jlink:依附于该结点（地址由jvex给出）的边中的下一条边的的地址。
20、info:边结点的数据域，保存边的权值等。mark:边结点的标志域，用于标识该条边是否被访问过。markivexilinkjvexjlinkinfo十字链表目 录 导 航6.16.26.36.46.56.66.7图的定义和基本术语案例引入图的类型定义图的存储结构图的遍历图的应用案例分析与实现Contents图的遍历遍历实质找每个顶点的邻接点的过程图的特点图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。遍历定义从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。
21、人工智能-搜索问题有3个传教士和3个野人来到河边准备渡河，河岸有一条船，每次最多可坐2个人。问传教士为安全起见，应如何规划摆渡方案，使得在任何时刻，在河两岸以及船上传教士人数不能少于野人人数？在每一次渡河后，都会有几种渡河方案供选择，究竟哪种方案最有利？这就是搜索问题。适用情况：难以获得求解所需的全部信息；更没有现成的算法可供求解使用。人工智能-搜索问题概念：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索对这类问题，一般我们都转换为状态空间的搜索问题。人工智能-搜索问题如传教士和野人问题，可用在河左岸的传教士人数、野
22、人人数和船的情况来表示。即，初始时状态为（3，3，1），结束状态为（0，0，0），而中间状态可表示为（2，2，0）、（3，2，1）等等。这类问题的解，就是一个合法状态的序列，其中序列中第一个状态是问题的初始状态，而最后一个状态则是问题的结束状态。SgS0解路径搜索空间全状态空间人工智能-搜索问题在一个33的方框内放有8个编号的小方块，紧邻空位的小方块可以移入到空位上，通过平移小方块可将某一布局变换为另一布局。请给出从初始状态到目标状态移动小方块的操作序列。2318476512384765例:8数码难题搜索引擎的两种基本抓取策略预处理爬行和抓取排名搜索引擎蜘蛛通过跟踪链接访问网页，获得页面HTM
23、L代码存入数据库。索引程序对抓取来的页面数据进行文字提取、中文分词、索引等处理，以备排名程序调用用户输入关键词后，排名程序调用索引库数据，计算相关性，然后按一定格式生成搜索结果页面。爬行抓取索引排序返回搜索引擎的两种基本抓取策略搜索引擎的两种基本抓取策略-深度优先如封建帝位的继承。不能深入的情况下才考虑其他分支的策略搜索引擎的两种基本抓取策略-广度优先类似长幼有序的规则两种策略结合=先广后深+权重优先先把这个页面所有的链接都抓取一次再根据这些URL的权重来判定URL的权重高，就采用深度优先，URL权重低，就采用宽度优先或者不抓取。图常用的遍历：解决思路：设置辅助数组 visited n，用来标
24、记每个被访 问过的顶点。初始状态为0i 被访问，改 visited i为1，防止被多次访问怎样避免重复访问？深度优先搜索广度优先搜索基本思想：仿树的先序遍历过程。v1v1v2v3v8v7v6v4v5DFS 结果v2v4v8v5v3v6v7起点深度优先搜索(DFS Depth_First Search)深度优先搜索的步骤简单归纳：访问起始点v;若v的第1个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找v的第2个邻接点重新遍历。213456213546深度优先搜索练习深度优先搜索的步骤详细归纳：E 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；E 再从 w
25、1 出发，访问与 w1邻接但还未被访问过的顶点 w2；E 然后再从 w2 出发，进行类似的访问，E 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。起点深度优先搜索的步骤详细归纳：E接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。起点213546讨论1：计算机如何实现DFS？1 2345610 000000 0000030 0000040 0000050 0000060 00000000000123456
26、010000110000111000111010111110111111邻接矩阵A辅助数组 visited n 开辅助数组 visited n！1 23 45610 11 10021 00 01031 00 01041 00 00150 11 00060 00 100讨论1：计算机如何实现DFS？DFS 结果213456213546void DFS(AMGraph G,int v)/图G为邻接矩阵类型 coutv;visitedv=true;/访问第v个顶点 for(w=0;w G.vexnum;w+)/依次检查邻接矩阵v所在的行 if(G.arcsvw!=0)&(!visitedw)DFS(
27、G,w);/w是v的邻接点，如果w未访问，则递归调用DFS 讨论2：DFS算法如何编程？可以用递归算法！讨论3：在图的邻接表中如何进行DFS？v0 v1 v2 v3DFS 结果00000123辅助数组 visited n 1000110011101111照样借用visited n！起点0123讨论4：邻接表的DFS算法如何编程？void DFS(ALGraph G,int v)/图G为邻接表类型 coutadjvex;/表示w是v的邻接点 if(!visitedw)DFS(G,w);/如果w未访问，则递归调用DFS p=p-nextarc;/p指向下一个边结点 仍可用递归算法用邻接矩阵来表示图
28、，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n2)。用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。DFS算法效率分析基本思想：仿树的层次遍历过程广度优先搜索(BFS Breadth_First Search)v1v1v2v3v8v7v6v4v5BFS 结果v2v3v4v5v6v7v8起点简单归纳：广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一
29、个递归的过程，其算法也不是递归的。广度优先搜索的步骤在访问了起始点v之后，依次访问 v的邻接点；然后再依次访问这些顶点中未被访问过的邻接点；直到所有顶点都被访问过为止。从图中某个顶点v出发，访问v，并置visitedv的值为true，然后将v进队。只要队列不空，则重复下述处理。【算法思想】队头顶点u出队。依次检查u的所有邻接点w，如果visitedw的值为false，则访问w，并置visitedw的值为true，然后将w进队。讨论1：计算机如何实现BFS？邻接表除辅助数组visited n 外，还需再开一辅助队列起点辅助队列v2已访问过了BFS 遍历结果入队！void BFS(Graph G,
30、int v)/按广度优先非递归遍历连通图G cout=0;w=NextAdjVex(G,u,w)if(!visitedw)/w为u的尚未访问的邻接顶点 coutw;visitedw=true;EnQueue(Q,w);/w进队 /if /while/BFS【算法描述】如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n 个元素），总的时间代价为O(n2)。用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。BFS算法效率分析 已知图的邻接表，分别给出用深度优先搜索和广度优先搜索从顶点
31、3出发的遍历序列。1 2 4 1 3 6 2 4 6 5 3 5 1 6 5 2 1 深度：3，6，5，1，2，4 广度：3，6，2，5，1，4练习空间复杂度相同，都是O(n)(借用了堆栈或队列）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。DFS与BFS算法效率比较补充：ACM算法设计-DFS&BFS.ppt目 录 导 航6.16.26.36.46.56.66.7图的定义和基本术语案例引入图的类型定义图的存储结构图的遍历图的应用案例分析与实现Contents图的应用最小生成树最短路径拓扑排序关键路径极小连通子图：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再
32、连通。生成树：包含图G所有顶点的极小连通子图（n-1条边）。G1的生成树连通图 G1 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2最小生成树v2v4v1v3DFS生成树邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生成树v0无向连通图画出下图的生成树v0v1v2v4v4v3求最小生成树首先明确：目标：在网的多个生成树中，寻找一个各边权值之和最小的生成树。使用不同的遍历图的方法，可以得到不同的生成树从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1
33、条边。123必须只使用该网中的边来构造最小生成树；构造最小生成树的准则必须使用且仅使用n-1条边来联结网络中的n个顶点不能使用产生回路的边欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2 条线路，那么，如何选择n1条线路，使总费用最少？数学模型：顶点表示城市，有n个；边表示线路，有n1条；边的权值表示线路的经济代价；连通网表示n个城市间通信网。显然此连通网是一个生成树！最小生成树的典型用途补充：贪心算法(Greedy Algorithm)算法原理以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪心法不要回溯。
34、算法优点因为省去了为寻找解而穷尽所有可能所必须耗费的大量时间，因此算法效率高。注意贪婪算法的精神就是“只顾如何获得眼前最大的利益”,有时不一定是最优解。平时购物找钱时，为使找回的零钱的硬币数最少，不考虑找零钱的所有各种发表方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪心法。找零钱问题补充：贪心算法(Greedy Algorithm)一个小偷，背着一个可载重W公斤的背包行窃.店内有数种不同的商品，不同商品有不同的重量及价值。考虑商品可以分割的情形(例如，可以只取1/2或1/3个商品)。目的在于求出
35、如何偷到最大利益价值的商品。Knapsack问题假设小偷的背包可裝30公斤的物品假设商品价格/重量如下:物品價值重量单价1505102601063140207Knapsack问题1 以贪婪算法的观念来看，第一步要找到最佳效益的商品。2 我们知道，物品1最划算，故5公斤全放入背包。(背包还可以装25公斤)3 再来考虑物品3，一样全部放入背包中。(背包还可以装5公斤)4 最后考虑物品2，再放入5公斤的物品2，即完成工作。5 最大利益为220元。物品價值重量单价1505102601063140207Knapsack问题物品價值重量150526010314020贪婪算法：先取物品1，再取物品3；但物品
36、2，不可再选取，否则背包会断裂。故以贪婪算法所得到的最好的利益为190元。但最佳的利益为物品2+物品3=200元。因为：小偷的背包可以装下30公斤的物品 u若此时商品改成不可分割，也就是说,对一个商品来说，要不就是全取,要不就是不取。u此时，贪婪算法不一定能求得最大利益。Knapsack问题v Prim（普里姆）算法 v Kruskal（克鲁斯卡尔）算法如何求最小生成树Prim算法归并顶点，与边数无关，适于稠密网。Kruskal算法归并边，适于稀疏网。设连通网络 N=V,E 普里姆算法的基本思想归并顶点从某顶点 u0 出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点
37、集合U中每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到U中直到所有顶点都加入到生成树顶点集合U中为止应用普里姆算法构造最小生成树的过程 设连通网络 N=V,E 克鲁斯卡尔算法的基本思想归并边A构造一个只有 n个顶点，没有边的非连通图 T=V,每个顶点自成一个连通分量C重复下去，直到所有顶点在同一连通分量上为止。B在 E 中选最小权值的边,若该边的两个顶点落在不同的连通分量上，则加入 T 中；否则舍去，重新选择应用克鲁斯卡尔算法构造最小生成树的过程典型用途：交通问题。如：城市A到城市B有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何
38、选择一条线路，使总费用（或总时间）最少？问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。（注：最短路径与最小生成树不同，路径上不一定包含n个顶点）最短路径一顶点到其余各顶点两种常见的最短路径问题：一、单源最短路径用Dijkstra（迪杰斯特拉）算法二、所有顶点间的最短路径用Floyd（弗洛伊德）算法任意两顶点之间最短路径最短路算法典型应用-计算机网络路由最短路算法典型应用机器人探路最短路算法典型应用游戏开发Dijistra算法A*算法+估价值估价值=0静态环境求解最短路最有效的方法 Dijistra算法的改进A*算法（静态环境）Di
39、jistra算法的改进D*算法（动态环境）D*算法典型应用火星探测器01234555403121006030101020500600201005005010030100从v0到其余各点的最短路径-按路径长度递增次序求解源 点终 点最 短 路 径路 径 长 度v0v2(v0,v2)10v4(v0,v4)30v3(v0,v4,v3)50v5(v0,v4,v3,v5)60v1无1.初始化：先找出从源点v0到各终点vk的直达路径（v0,vk），即通过一条弧到达的路径。2.选择：从这些路径中找出一条长度最短的路径（v0,u）。3.更新：然后对其余各条路径进行适当调整：Dijkstra算法的思想55403
40、12100603010102050若在图中存在弧（u,vk），且（v0,u）+（u,vk）（v0,vk）,则以路径（v0,u,vk）代替（v0,vk）。在调整后的各条路径中，再找长度最短的路径，依此类推。主：邻接矩阵Gnn(或者邻接表)辅：数组Sn：记录相应顶点是否已被确定最短距离 数组Dn：记录源点到相应顶点路径长度 数组Pathn：记录相应顶点的前驱顶点存储结构（顶点个数为n）5540312100603010102050v=0v=1v=2v=3v=4v=5StruefalsefalsefalsefalsefalseD01030100Path 110 100算法初始化结果 初始化：将源点v0
41、加到S中，即Sv0=true；将v0到各个终点的最短路径长度初始化为权值，即Di=G.arcsv0vi，(viV S)；如果v0和顶点vi之间有弧，则将vi的前驱置为v0，即Pathi=v0，否则Pathi=1。选择下一条最短路径的终点vk，使得：Dk=MinDi|viV S【算法思想】将vk加到S中，即Svk=true。更新从v0出发到集合V S上任一顶点的最短路径的长度，同时更改vi的前驱为vk。若Si=false 且 Dk+G.arcskiDi，则Di=Dk+G.arcski;Path i=k;。重复 n 1次，即可按照路径长度的递增顺序，逐个求得从v0到图上其余各顶点的最短路径。【算法
42、思想】sikDiDk初 始 化 各 类 结 构（辅 助 结 构）依 次 求 Vo到 Vi的 最 短 距 离i=1in找 Vj,Dj=minDj Vj加 入 S中修 改 其 它 顶 点 的 最 短 路 径i+结 束【算法思想】(v0,v2)+(v2,v3)(v0,v3)终点 从v0到各终点的长度和最短路径v1v2v3v4v5vjS之外的当前最短路径之顶点60v0,v2,v350v0,v4,v330v0,v490v0,v4,v560v0,v4,v3,v55540312100603010102050sv0,v2v0,v2,v4v0,v2,v4,v3 v0,v2,v4,v3,v510v0,v230v0
43、,v4100v0,v5例0600201005005010030100v2v4v3v5100v0,v5012345Dw0 1 2 3 4 510v0,v250v0,v4,v330v0,v4【算法思想】iG.vexnum初始化过程;(i=1;)EndNYw G.vexnummin=INFINTY;(w=0;)w G.vexnumNY!SwDw minv=w;min=Dw;YN+wN!Sw&(min+G.arcsv,wDw)Dw=min+G.arcsv,w;Pathw=v;+w;NNYYN +i;Sv=true;(w=0;)更新v0 到V-S 中顶点的Dist求最短路径长度Dist算法流程图void
44、 ShortestPath_DIJ(AMGraph G,int v0)/用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径 n=G.vexnum;/n为G中顶点的个数 for(v=0;vn;+v)/n个顶点依次初始化 Sv=false;/S初始为空集 Dv=G.arcsv0v;/将v0到各个终点的最短路径长度初始化 if(Dv MaxInt)Path v=v0;/v0和v之间有弧，将v的前驱置为v0 else Path v=-1;/如果v0和v之间无弧，则将v的前驱置为-1 /for Sv0=true;/将v0加入S Dv0=0;/源点到源点的距离为0【算法描述】时间复杂度：O(n
45、2)/*开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集*/for(i=1;in;+i)/对其余n1个顶点，依次进行计算 min=MaxInt;for(w=0;wn;+w)if(!Sw&Dwmin)v=w;min=Dw;/选择一条当前的最短路径，终点为v Sv=true;/将v加入S for(w=0;wn;+w)/更新从v0出发到集合VS上所有顶点的最短路径长度 if(!Sw&(Dv+G.arcsvwnextarc）;k=p-adjnexr;if（!（-indegree k）Push（S,k）;if（ve j+*（p-info）ve k ）ve k =ve j +*（p-info）
46、;if（count G.vexnum）return ERROR;else return OK;/栈 T 为求事件的最迟发生时间的时候用。实例：求事件结点的最早发生时间V1V3V2V5V6V413511222216、568V1V2V3V4V5V6逆向拓扑排序：利用逆向拓扑排序算法求事件结点的最迟发生时间的执行步骤：1、设每个结点的最迟发生时间为收点的最早发生时间。2、将栈中的结点V取出。3、根据逆邻接表找到结点V的所有的起始结点，将结点V的最迟发生时间-活动的权值得到的差同起始结点的原最迟发生时间进行比较；如果该值小，则用该值取代原最迟发生时间。4、反复执行 2、3；直至栈空为止。888888V
47、1V3V2V5V6V413511222216、4、40、0、03实例：求事件结点的最迟发生时间V1V3V2V5V6V4 实例的事件结点的最迟发生时间1351122221304568V1V3V2V5V6V4 实例的事件结点的最早发生时间1351102222113568V1V2V1V3V1V4V2V3V3V4V3V6V4V5V4V6V5V6V2V5边最早发生时间Ve(j)最迟发生时间V l(k)-dut(j,k)00011335562103446566关键活动关键活动关键活动实例：求事件结点的最迟发生时间304568V1V3V2V5V6V4实例的关键路径（粗大的黑色箭头所示）13511022221
48、13568注意：关键路径可有多条缩短工期必须缩短关键活动所需的时间目 录 导 航6.16.26.36.46.56.66.7图的定义和基本术语案例引入图的类型定义图的存储结构图的遍历图的应用案例分析与实现Contents【案例分析】把六度空间理论中的人际关系网络图抽象成一个不带权值的无向图G 用图G中的一个顶点表示一个人，两个人“认识”与否，用代表这两个人的顶点之间是否有一条边来表示。这样六度空间理论问题便可描述为：在图G中，任意两个顶点之间都存在一条路径长度不超过7的路径。在实际验证过程中，可以通过测试满足要求的数据达到一定的百分比（比如99.5%）来进行验证。这样我们便把待验证六度空间理论问
49、题描述为：在图G中，任意一个顶点到其余99.5%以上的顶点都存在一条路径长度不超过7的路径。比较简单的一种验证方案是：利用广度优先搜索方法，对任意一个顶点，通过对图G的“7层”遍历，就可以统计出所有路径长度不超过7的顶点数，从而得到这些顶点在所有顶点中的所占比例。案例6.1：六度空间理论【算法步骤】案例6.1：六度空间理论 完成系列初始化工作：设变量Visit_Num用来记录路径长度不超过7的顶点个数，初值为0；Start为指定的一个起始顶点，置visitedStart的值为true，即将Start标记为六度顶点的始点；辅助队列Q初始化为空，然后将Start进队。当队列Q非空，且循环次数小于7
50、时，循环执行以下操作（统计路径长度不超过7的顶点个数）：队头顶点u出队；依次检查u的所有邻接点w，如果visitedw的值为false，则将w标记为六度顶点；路径长度不超过7的顶点个数Visit_Num加1；将w进队。退出循环时输出从顶点Start出发，到其他顶点长度不超过7的路径的百分比。【算法描述】案例6.1：六度空间理论void SixDegree_BFS(Graph G,int Start)/通过广度优先搜索方法遍历G来验证六度空间理论，Start为指定的一个起点 Visit_Num=0;/记录路径长度不超过7的顶点个数 visitedStart=true;/置顶点Start访问标志数
