《数据结构第7章(3).ppt》由会员分享，可在线阅读，更多相关《数据结构第7章(3).ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数 据 结 构 第第7 7章章 图图北华航天工业学院计算机系 制作目目 标标理解图的基本概念及术语；理解图的基本概念及术语；掌握图的两种存储结构掌握图的两种存储结构(邻接矩阵和邻接表邻接矩阵和邻接表)；熟练掌握图的两种遍历的算法思想、步骤；熟练掌握图的两种遍历的算法思想、步骤；掌握按掌握按PrimPrim和和KruskalKruskal算法构造最小生成树的步骤；算法构造最小生成树的步骤；领会并掌握求拓扑排序、关键路径、最短路径的领会并掌握求拓扑排序、关键路径、最短路径的过程。过程。北华航天工业学院计算机系 制作本章内容本章内容7.1 图的定义和术语图的定义和术语7.2 图的存储结构图的存储结构
2、7.3 图的遍历图的遍历7.4 图的连通性问题图的连通性问题7.5 有向无环图及其应用有向无环图及其应用7.6 最短路径最短路径北华航天工业学院计算机系 制作7.4 7.4 图的连通性问题图的连通性问题7.4.1 图的连通性图的连通性7.4.2 生成树和生成森林生成树和生成森林7.4.3 Prim算法算法7.4.4 kruskal算法算法 北华航天工业学院计算机系 制作7.4.1 图的连通性图的连通性对无向图进行遍历对无向图进行遍历 对对于于连连通通图图，从从图图中中任任一一顶顶点点出出发发，进进行行深深度度优优先先搜搜索索或或广广度度优优先先搜搜索索，便便可可访访问问到到图图中中所所有顶点。
3、有顶点。对对非非连连通通图图，需需从从多多个个顶顶点点出出发发进进行行搜搜索索，而而每每一一次次从从一一个个新新顶顶点点出出发发进进行行搜搜索索，访访问问到到的的序列为其连通分量中的顶点集。序列为其连通分量中的顶点集。北华航天工业学院计算机系 制作7.4.1 图的连通性图的连通性对有向图进行遍历时对有向图进行遍历时 强连通：双向强连通：双向 深深度度优优先先搜搜索索是是求求有有向向图图的的强强连连通通分分量量的的一一个有效方法。个有效方法。北华航天工业学院计算机系 制作7.4.1 图的连通性图的连通性确定有向图的强连通分量确定有向图的强连通分量 在在有有向向图图上上，从从某某个个顶顶点点出出发
4、发沿沿以以该该顶顶点点为为尾尾的的弧弧进进行行深深度度优优先先搜搜索索遍遍历历，并并按按其其搜搜索索完完成成顺顺序序将将顶点排列起来。顶点排列起来。从从最最后后完完成成搜搜索索的的顶顶点点出出发发，沿沿着着以以该该顶顶点点为为头头的的弧弧作作逆逆向向的的深深度度搜搜索索遍遍历历，若若此此次次遍遍历历不不能能访访问问到到所所有有顶顶点点，则则从从余余下下顶顶点点中中最最后后完完成成搜搜索索的的那那个个顶顶点点出出发发，继继续续作作逆逆向向的的深深度度优优先先搜搜索索遍遍历历。直直到所有顶点都被访问到为止。到所有顶点都被访问到为止。北华航天工业学院计算机系 制作7.4.1 图的连通性图的连通性确定
5、有向图的强连通分量确定有向图的强连通分量 在在有有向向图图上上，从从某某个个顶顶点点出出发发沿沿以以该该顶顶点点为为尾尾的的弧弧进进行行深深度度优优先先搜搜索索遍遍历历，并并按按其其搜搜索索完完成成顺顺序序将将顶点排列起来。顶点排列起来。从从最最后后完完成成搜搜索索的的顶顶点点出出发发，沿沿着着以以该该顶顶点点为为头的弧作逆向的深度搜索遍历。头的弧作逆向的深度搜索遍历。每每一一次次作作逆逆向向深深度度优优先先遍遍历历所所访访问问到到的的顶顶点点集集便是有向图中一个强连通分量的顶点集。便是有向图中一个强连通分量的顶点集。北华航天工业学院计算机系 制作7.4 7.4 图的连通性问题图的连通性问题7
6、.4.1 图的连通性图的连通性7.4.2 生成树和生成森林生成树和生成森林7.4.3 Prim算法算法7.4.4 kruskal算法算法 北华航天工业学院计算机系 制作7.4.2 生成树和生成森林生成树和生成森林画出给定图的深度和广度优先遍历的顶点序列画出给定图的深度和广度优先遍历的顶点序列保留遍历过程中经过的边和所有顶点！保留遍历过程中经过的边和所有顶点！北华航天工业学院计算机系 制作7.4.2 生成树和生成森林生成树和生成森林画出给定图的深度和广度优先遍历的顶点序列画出给定图的深度和广度优先遍历的顶点序列深度优先搜索遍历过程深度优先搜索遍历过程深度优先遍历生成树深度优先遍历生成树北华航天工
7、业学院计算机系 制作7.4.2 生成树和生成森林生成树和生成森林画出给定图的深度和广度优先遍历的顶点序列画出给定图的深度和广度优先遍历的顶点序列深度优先搜索遍历过程深度优先搜索遍历过程广度优先遍历生成树广度优先遍历生成树非连通图？非连通图？北华航天工业学院计算机系 制作7.4.2 生成树和生成森林生成树和生成森林生成树（连通图）生成树（连通图）n个顶点；个顶点；n-1条边；条边；不构成回路。不构成回路。生成森林（非连通图）生成森林（非连通图）多个连通分量的生成树。多个连通分量的生成树。无向连通图的生成树不唯一。无向连通图的生成树不唯一。最小生成树：边上权值之和最小的生成树。最小生成树：边上权值
8、之和最小的生成树。北华航天工业学院计算机系 制作7.4 7.4 图的连通性问题图的连通性问题7.4.1 图的连通性图的连通性7.4.2 生成树和生成森林生成树和生成森林7.4.3 Prim算法算法7.4.4 kruskal算法算法 北华航天工业学院计算机系 制作7.4.3 Prim算法算法MST性质性质 设设G G(V(V，E E）是一个连通网络，）是一个连通网络，U U是顶点集是顶点集V V的一的一个真子集。若个真子集。若(u(u，v v）是）是G G中所有的一个端点在中所有的一个端点在U(U(即即uUuU）里、另一个端点不在）里、另一个端点不在U(U(即即vVvVU U）里的边中，）里的边
9、中，具有最小权值的一条边具有最小权值的一条边，则一定存在，则一定存在G G的一棵最小生的一棵最小生成树包括此边成树包括此边(u(u，v)v)。北华航天工业学院计算机系 制作7.4.3 Prim算法算法基本思想基本思想 假假设设G=G=（V V，E E）是是一一个个具具有有n n个个顶顶点点的的连连通通网网，T=T=（U U，TETE）是是G G的的最最小小生生成成树树，U U和和TETE的的初初始始值值均均为为空空，以顶点以顶点v v0 0为初始点。为初始点。构造过程：构造过程：初初始始化化U=vU=v0 0。v v0 0到到其其它它生生成成树树外外的的顶顶点点的的所所有边为候选边；有边为候选
10、边；从从候候选选边边中中选选权权值值最最小小并并且且一一个个端端点点i i在在U U中中，另另一一个个端端点点j j在在V VU U中中的的边边，将将该该边边加加入入到到TETE中中，同同时时将将端端点点j j也也加加入入到到U U中中。重重复复n n1 1次次，直直到到所所有有顶顶点都被加入到点都被加入到U U中。中。北华航天工业学院计算机系 制作7.4.3 Prim算法算法例：例：用用Prim算法求带权图的最小生成树。算法求带权图的最小生成树。北华航天工业学院计算机系 制作7.4.3 Prim算法算法实现算法实现算法 一一维维数数组组lowcost：保保存存集集合合V-U中中各各顶顶点点与
11、与集集合合U中各顶点构成的边中具有最小权值的边的权值。中各顶点构成的边中具有最小权值的边的权值。一一维维数数组组adjvex：保保存存依依附附于于该该边边的的集集合合U中中的顶点。的顶点。初始状态：初始状态：V0 U，则，则lowcost0=0。北华航天工业学院计算机系 制作7.4.3 Prim算法算法实现算法实现算法 struct VertexType adjvex;/依附的顶点依附的顶点 VRType lowcost;/权值权值 closedgeMAX_VERTEX_NUM;选选取取权权值值最最小小的的边边，将将边边的的另另一一个个顶顶点点加加入入到到U中中，重复此过程共重复此过程共n-1
12、次。（图有次。（图有n个顶点）个顶点）北华航天工业学院计算机系 制作7.4.3 Prim算法算法实现算法实现算法（邻接矩阵存储）邻接矩阵存储）void Prim(MGraph G,VertexType u)int mincost,i,j;int k=LocateVex(G,u);for(i=0;iG.vernum;i+)if(j!=k)closedgei.lowcost=G.arcski.adj;closedgei.adjvex=u;closedgek.lowcost=0;closedgek.adjvex=u;北华航天工业学院计算机系 制作7.4.3 Prim算法算法实现算法实现算法（邻接矩阵
13、存储）邻接矩阵存储）for(i=1;iG.vexnum;i+)int mincost=MAXCOST;j=1;k=1;while(jG.vexnum)if(closedgej.lowcostmincost&closedgej.adjvex!=0)mincost=closedgej.lowcost;k=j;j+;北华航天工业学院计算机系 制作7.4.3 Prim算法算法实现算法实现算法（邻接矩阵存储）邻接矩阵存储）cout顶点的序号点的序号:k+1权值:mincostendl;closedgek.lowcost=0;for(j=0;jG.vexnum;j+)if(G.arcskjclosedge
14、j.lowcost)closedgej.lowcost=G.arcskj.adj;closedgej.adjvex=G.vexsk;北华航天工业学院计算机系 制作7.4 7.4 图的连通性问题图的连通性问题7.4.1 图的连通性图的连通性7.4.2 生成树和生成森林生成树和生成森林7.4.3 Prim算法算法7.4.4 kruskal算法算法 北华航天工业学院计算机系 制作7.4.4 Kruskal算法算法 KruskalKruskal算算法法是是一一种种按按照照网网中中边边的的权权值值递递增增顺顺序序构造最小生成树的方法。构造最小生成树的方法。基本思想基本思想：设设无无向向连连通通网网为为G
15、 G（V V，E E），令令G G的的最最小小生生成成树树为为T T。开开始始时时，最最小小生生成成树树T T由由图图G G中中的的n n个个顶顶点点构构成成，顶顶点点之之间间没没有有一一条条边边，这这样样T T中中各各顶顶点点各各自自构构成成一一个个连通分量。连通分量。然然后后，查查找找两两个个顶顶点点属属于于T T的的两两个个不不同同连连通通分分量量的的权权值值最最小小的的边边，将将此此边边加加入入到到T T中中，同同时时把把两两个个连连通通分量连接为一个连通分量；分量连接为一个连通分量；重复此过程，至重复此过程，至T T中的连通分量个数为中的连通分量个数为1 1。北华航天工业学院计算机系
16、 制作7.4.4 Kruskal算法算法例例：用用Kruskal算算法法求求带带权权图图的的最最小小生生成成树。树。北华航天工业学院计算机系 制作7.4.4 Kruskal算法算法实现算法实现算法 无向带权图以边集数组形式存储。无向带权图以边集数组形式存储。如如何何判判断断连连接接边边的的两两个个顶顶点点属属于于不不同同的的连连通通分量？分量？树的集合表示树的集合表示(P140)用用father 存储集合，初值全为存储集合，初值全为-1。用用Find()函数求顶点所在树的根结点。函数求顶点所在树的根结点。北华航天工业学院计算机系 制作7.4.4 Kruskal算法算法实现算法实现算法边集数组类
17、型定义边集数组类型定义#define MaxVexNum#define MaxArcNum typedef int VertexType;typedef struct int v1,v2,w;ArcType;typedef struct VertexType vexsMaxVexNum;ArcType arcsMaxArcNun；int vexnum,arcnum;EAGraph;北华航天工业学院计算机系 制作7.4.4 Kruskal算法算法实现算法实现算法Find函数定义函数定义(P141 算法算法 6.8)int Find（MFSet s，int v）/v是需要查找其根结点的图顶点序号是
18、需要查找其根结点的图顶点序号/树的双亲表示法定义树的双亲表示法定义(P135 PTree)int t=v;while(s.nodest.parent0)t=s.nodest.father;return t;北华航天工业学院计算机系 制作7.4.4 Kruskal算法算法实现算法实现算法Kruskal算法算法 void Kruskal（EAGraph G）MFSet s;int i,j,vf1,vf2;for(i=0;iG.vexnum;i+)s.nodesi.parent=-1;i=0;j=0;while(iG.arcnum&jG.vexnum-1)vf1=Find(s,G.arcsi.v1)
19、;vf2=Find(s,G.arcsi.v2);北华航天工业学院计算机系 制作7.4.4 Kruskal算法算法实现算法实现算法Kruskal算法算法 if(vf1!=vf2)s.nodesvf2.parent=vf1;j+;coutG.arcsi.v1“,”G.arcsi.v2);coutendl;i+;北华航天工业学院计算机系 制作小小 结结掌掌握握求求最最小小生生成成树树的的PrimPrim算算法法的的思思想想和和KruskalKruskal算法的思想（算法的思想（解题解题）理解理解PrimPrim算法和算法和KruskalKruskal算法的实现算法算法的实现算法北华航天工业学院计算机系 制作练练 习习 题题利利用用PrimPrim算算法法和和KruskalKruskal算算法法求求最最小小生生成成树树，并并画画出相应的最小生成树。出相应的最小生成树。