清华名师数据结构考研辅导课件附带考试大纲第七章图

1、图2022/7/22考研辅导四、图图 （一） 图的概念 （二） 图的存储及基本操作 1. 邻接矩阵法 2. 邻接表法 （三） 图的遍历 1. 深度优先搜索 2. 广度优先搜索2022/7/22考研辅导四、图（四） 图的基本应用及其复杂度分析 1. 最小（代价）生成树 2. 最短路径 3. 拓扑排序 4. 关键路径2022/7/22考研辅导图的概念ADT graph数据对象V： V是具有相同特性的数据元素的集合，称顶点集数据关系R： R=VR VR| v,wV 且 P(v,w) 表示从 v 到 w 的弧 谓词 P(v,w)定义了弧 的意义或信息基本操作P： 结构的建立和销毁 对顶点的访问操作 插

2、入或删除顶点 插入和删除弧 对邻接点的操作 遍历ADT graph2022/7/22考研辅导图的概念一组概念：有向图，弧，弧头，弧尾，子图/无向图，边/网，有向网，无向网完全图，稀疏图 (边或弧的个数enlogn)，稠密图邻接点(邻接到，邻接自/关联)/度、入度、出度路径，路径长度，简单路径，简单回路连通图、连通分量/强连通图、强连通分量生成树(连通图)/生成森林(非连通图)returnABECDACDFEBABECD65473152022/7/22考研辅导图的邻接矩阵存储及操作邻接矩阵用两个数组分别存储：数据元素（顶点）数据元素之间的关系（边或弧）的信息。存储边信息的数组用邻接矩阵表示，邻接

3、矩阵的元素定义为：Aij=0 (Vi ,Vj)VR1 (Vi ,Vj)VR2022/7/22考研辅导图的邻接矩阵存储及操作无向图的邻接矩阵一定是对称矩阵。010010100011000101001001110000011100ACDFEB2022/7/22考研辅导图的邻接矩阵存储及操作有向图的邻接矩阵不一定是非对称矩阵。ABECD01001001000001011000001002022/7/22考研辅导图的邻接矩阵存储及操作网的邻接矩阵可定义为：ABECD6547315065010547030Aij=Wi,j 若(Vi ,Vj)或 VR 反之2022/7/22考研辅导图的邻接矩阵存储及操作图

4、的数组（邻接矩阵）存储表示#define INFINITY INF_MAX /最大值#define MAX_VERTEX_NUM 20 /最大顶点个数typedef enumDG,DN,UDG,UDN GraphKind; / 有向图,有向网,无向图,无向网/定义弧typedef struct ArcCell VRType adj; /表示顶点关系的值的类型.无权图:adj为1或0; 带权图:adj为权值,VRType为权值类型 InfoType *info; / 该弧相关信息的指针ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; / 定义邻接矩阵

5、AdjMatrix为ArcCell类型的二维数组2022/7/22考研辅导图的邻接矩阵存储及操作图的数组（邻接矩阵）存储表示/定义图typedef struct VertexType vexsMAX_VERTEX_NUM; /顶点向量,存储顶点 AdjMatrix arcs; /邻接矩阵,存储边或弧。AdjMatrix为二维数组类型 int vexnum,arcnum; /图的当前顶点数和弧数 GraphKind kind; /图的种类标志MGraph2022/7/22考研辅导图的邻接矩阵存储及操作图的邻接矩阵存储表示法的操作：构造图 算法7.1Status CreateGraph( MGra

6、ph &G ) scanf(&G.kind); /获取图的种类标志 switch(G.kind) case DG:return CreateDG(G); /构造有向图G case DN:return CreateDN(G); /构造有向网G case UDG:return CreateUDG(G); /构造无向图G case UDN:return CreateUDN(G); /构造无向网G default:return ERROR; 2022/7/22考研辅导图的邻接矩阵存储及操作图的邻接矩阵存储表示法的操作：构造无向网 算法7.2Status CreateUDN(MGraph &G) sca

7、nf(&G.vexnum,&G.arcnum,&IncInfo); /读取图的顶点数,边数,弧信息IncInfo为0则各弧不含其他信息 for(i=0;iG.vexnum;+i) scanf(&G.vexsi); /构造顶点向量 for(i=0;iG.vexnum;+i) /初始化邻接矩阵 for(j=0;jG.vexnum;+j) G.arcsij=INFINITY,NULL; /adj,infoadj为2022/7/22考研辅导图的邻接矩阵存储及操作 for(k=0;kG.vexnum;+k) /构造邻接矩阵 scanf(&v1,&v2,&w); /输入一条边依附的顶点及权值 i=Loca

8、teVex(G,v1); j=LocateVex(G,v2); /确定v1和v2在G中位置 G.arcsij.adj=w; /弧的权值 if(IncInfo) Input(*G.); /若该弧含有相关信息，则输入它 G.arcsji=G.arcsij；/置的对称弧 return OK; return2022/7/22考研辅导图的邻接表存储邻接表是图的一种链式存储结构。在邻接表中，为图的每个顶点建立一个单链表：第i个单链表中的结点表示依附于顶点vi的边(对有向图是以vi顶点为尾的弧)/定义弧typedef struct ArcNodeint adjvex; /该弧所指向的顶

9、点的位置 struct ArcNode *nextarc; /指向下一条弧的指针 InfoType *info; /该弧相关信息的指针ArcNode;infoadjvexnextarc2022/7/22考研辅导图的邻接表存储/定义顶点typedef struct VNode VertexType data; /顶点信息 ArcNode *firstarc; /指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM;/定义图typedef struct AdjList vertices; /顶点向量 int vexnum,arcnum; /图的当前顶点数和弧数 int

10、 kind; /图的种类标志 ALGraph;datafirstarc2022/7/22考研辅导图的邻接表存储无向图的邻接表14ACDFEBABCDEF0123453525015041232022/7/22考研辅导图的邻接表存储有向图的邻接表14ABCDE01234201ABECD23return2022/7/22考研辅导图的遍历深度优先搜索 从图中某个顶点V0出发，访问此顶点; 然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到； 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到

11、为止。如图：设各顶点在数组中存储顺序为： v1,v2 ,v3 ,v4 ,v5 ,v6 ,v7 ,v8则该图深度优先搜索的序列为：v1v2 v4 v8 v5 v3 v6 v7V1V2V6V3V4V5V7v82022/7/22考研辅导图的遍历ABCDEFG访问序列：ABCEDFG231414231ABCDEF012345G6652022/7/22考研辅导图的遍历如何判别V的邻接点是否被访问？解决方法：为每个顶点设立一个访问标志:visitedw，其初值为false，一旦某个顶点被访问，将该值置为true。/从第v个顶点出发，深度优先遍历图G 算法 7.5void DFS(Graph G,int v

12、) visitedv=TRUE; VisitFunc(v); /访问第v个顶点 for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w); /对v的尚未访问的邻接顶点w，递归调用DFS 2022/7/22考研辅导图的遍历/深度优先遍历图G 算法 7.4/VisitFunc,visited为全局变量void DFSTraverse(Graph G,Status(*Visit)(int v) VisitFunc=Visit; for(v=0;vG.vexnum;+v) visitedv=FALSE; /访问标志数组初

13、始化 for(v=0;vG.vexnum;+v) if(!visitedv) DFS(G,v); /对尚未访问的顶点调用DFS2022/7/22考研辅导图的遍历广度优先搜索 从图中某个顶点V0出发，访问此顶点; 然后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到; 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。如图：设各顶点在数组中存储顺序为： v1,v2 ,v3 ,v4 ,v5 ,v6 ,v7 ,v8则该图广度优先搜索的序列为：v1v2

14、v3 v4 v5 v6 v7 v8V1V2V6V3V4V5V7v82022/7/22考研辅导图的遍历ABCDEFG访问序列：ABCDEFG231414231ABCDEF012345G6652022/7/22考研辅导/广度优先非递归遍历图G，使用辅助队列Q和访问标志数组visited 算法7.6void BFSTraverse(Graph G,Status(*Visit)(int v) for(v=0;vG.vexnum;+v) visitedv=FALSE; /初始化访问标志 InitQueue(Q); /置空的辅助队列Q,P59队列定义 for(v=0;v=0;w=NextAdjVex(G,

15、u,w) if(!visitedw) /W为u的尚未访问的邻接顶点 visitedw=TRUE;Visit(w); EnQueue(Q,w); /访问的顶点w入队列 return2022/7/22考研辅导最小生成树生成树一个有n个顶点的连通图的生成树是一个极小连通子图，它包含图中的全部顶点，但只有足以构成一棵树的n-1条边。最小生成树一个有n个顶点，e条边的连通网的最小生成树是： 它包含图中的全部顶点; 它包含图中的n-1条边，且n-1条边的“权值之和”为最小; 它无回路。生成最小生成树的方法方法一：普里姆算法 方法二：克鲁斯卡尔算法 2022/7/22考研辅导最小生成树普里姆算法基本思想（加

16、顶点法） 设生成树的顶点集合为U，边集合为TE，连通网的顶点集合为V; 则未加入生成树的顶点集合为V-U。取连通网中任意一个顶点u作为生成树的根;U=u然后往生成树上添加新的顶点w，该顶点满足： wV-U UV-U存在多条边，权值最小的边在V-U中对应的顶点即为顶点w;同时将对应边加入TE；重复直至U=V。在寻找UV-U的权值最小的边时，需设置一个辅助数组closedge：对VU中的某顶点Vx，可能U中有多个顶点与Vx关联，在这些边中取权最小的边：故数组元素closedgei需存储两个信息，最小权、与该最小权边相连的U中某顶点。在数组closedge中查找”最小权”最小的元素，便可找到顶点w。

17、2022/7/22考研辅导6155563426V1V2V6V3V5V4V1V2V3V4V6V5012354V10V16V11V15V1V1V1-：closedge 变化过程：V10V35V10V15V34V36V1，V3-：V10V35V10V42V30V36V1，V3，V6-： 0000002022/7/22考研辅导/用普里姆算法从顶点u出发构造网G(邻接矩阵表示法:P161)的最小生成树 算法7.9void MiniSpanTree_P(MGraph G,VertexType u) k=LocateVex(G,u); /确定第一个顶点u的存储位置 for(j=0;jG.vexnum;+j)

18、 /closedge数组初始化:从u顶点发向各顶点 if(j!=k) closedgej=u,G.arcskj.adj;/每个顶点的关联顶点为u closedgek.lowcost=0; /初始,U=u.每并入一个顶点,将权置0 for(i=0;iG.vexnum;+i) /大循环：将剩余所有顶点依次加入生成树 k=minimum(closedge); /求:加入生成树的下一个顶点w的存储位置k printf(closedgek.adjvex,G.vexsk); /输出新加入生成树的边 closedgek.lowcost=0; /顶点w并入U集 for(j=0;jG.vexnum;+j) /更

19、新closedge数组 if(G.arcskj.adjclosedgej.lowcost) /从w发向V-U集各顶点的边的权更小时，更新closedgej closedgej=G.vexsk,G.arcskj.adj; /j的关联点变为w 本算法时间复杂度：O(n2)-循环i嵌套循环j2022/7/22考研辅导最小生成树克鲁斯卡尔算法基本思想（加边法） 设连通网为N=V,E，生成树为T。将n个顶点看成n个集合;按权值由小到大的顺序选择边，且边的两个顶点不在同一顶点集内。将该边加入生成树，并将该边的两个顶点所在集合合并；重复直至所有顶点都在同一集合内。6155563426V1V2V6V3V5V4

20、V1V251V6V3V5V4342return2022/7/22考研辅导拓扑排序AOV-网 用顶点表示活动，弧表示活动间的优先关系的有向图称为顶点表示活动的网（Activity On Network），简称AOV-网。拓扑排序由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。从有向图中选取一个没有前驱的顶点，并输出它；从有向图中删除该顶点和所有以它为尾的弧。重复直至所有顶点均已输出或当前图中不存在无前驱的顶点。后者说明有向图中存在环。V1V2V6V3V5V4拓扑排序序列：V1 V2 V4 V6 V3 V52022/7/22考研辅导/有向图G采用邻接表存储结构。若G无回路，则

21、输出G的顶点的一个拓扑序列并返回OK，否则ERROR。 算法7.12 Status Topologicaisort(ALGraph G) FindInDegree(G,indegree); /对各顶点求入度,indegree为数组 InitStack(S); /为零入度顶点建立栈S for(i=0;iNextarc) /对i号顶点的每个邻接点的入度减1,即删除由i号顶点发出的各条弧 k=p-adjvex; if(!(-indegreek) Push(S,k); /若入度为零，则入栈 if(countG.vexnum) return ERROR ; /图中有回路 else return OK;本

22、算法时间复杂度：O(n+e)return2022/7/22考研辅导关键路径关键路径有向网中，顶点表示事件，弧表示活动，弧上的权值表示活动的持续时间。该网络称之为AOE-网(Activity On Edge)。 假设以AOE-网表示一个施工流图，则有待研究的问题是： 完成整项工程至少需要多少时间？ 哪些子工程是影响整个工程进度的关键？整个工程完成的时间为：从有向图的源点到汇点的最长路径。“关键活动”指的是：该活动的持续时间的增加会使有向图上的最长路径的长度增加。2022/7/22考研辅导关键路径如何求关键路径？“事件(顶点vi)”的最早发生时间ve(i)：指事件最早也得在以它为汇点的所有子工程完

23、成后才能开始。 ve(i)=从源点到顶点Vi的最长路径长度；“事件(顶点vi)”的最晚发生时间vl(i)：表示在不推迟整个工程完成的前提下，事件最晚发生的时间。即事件无论发生多晚，最后也得保证它后面的子工程中最长工期的子工程要按时完成。vl(i)=工程完成时间-从顶点Vi到汇点的最长路径长度。 活动的最早开始时间e(i)：取决于该活动前的事件的最早发生时间。 活动的最晚开始时间l(i)：取决于该活动后的事件的最晚发生时间。关键活动：e(i)=l(i)的那些活动。关键路径：由关键活动组成的路径。2022/7/22考研辅导关键路径事件发生时间的计算：如图：假设事件为vi,vj，弧为，活动为a： 事件最早开始时间: ve(源点)=0； ve(j)=Maxve(i)+dut() T,j=1,2,n-1 其中，T是所有以第j个顶点为头的弧的集合。 说明：在求某个ve(j)时，可能有多个i存在，即Vj有多个前驱顶点。 事件最晚开始时间 vl(汇点)=ve(汇点)； vl(i)=Minvl(j)dut() S,i=n-2,0 其中，S是所有以第i个顶点为尾的弧的集合。 说明：在求某个vl(i)时，可能有多个j存在，即Vi有多个后继顶点。 求ve(j)的顺序应该是按拓扑有序的次序。 求vl(i)的顺序应该是按拓扑逆序的次序。活