数据结构(严蔚敏)课件第7章

第七章第七章图图8/6/20241精选课件【课前思考】【课前思考】1.同学们有没有发现现在的十字路口的交通灯已从过去的一对改为三对，同学们有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的对某个丁字路口的6条通路画出和第一章绪论中介绍的条通路画出和第一章绪论中介绍的五叉路口交通管理五叉路口交通管理示意图示意图相类似的图？相类似的图？同学们一定可以画出如下所示类似的图形。2.如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC)8/6/20242精选课件【学习目标】【学习目标】1领会图的类型定义。2熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。3熟练掌握图的两种遍历算法。4理解各种图的应用问题的算法。8/6/20243精选课件【重点和难点】【重点和难点】图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。【知识点】【知识点】图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径。8/6/20244精选课件【学习指南】【学习指南】离散数学中的图论是专门研究图性质的一个数学分离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效果。提高学习的效果。本章必须完成的算法设计题为本章必须完成的算法设计题为:7.7,7.9,7.10,7.12,7.14,7.15,7.228/6/20245精选课件7.1 图的定义与术语图的定义与术语7.2 图的存储表示图的存储表示7.3 图的遍历图的遍历7.4 最小生成树最小生成树7.5 重（双）连通图和关节点重（双）连通图和关节点7.6 两点之间的最短路径问题两点之间的最短路径问题7.7 拓扑排序拓扑排序7.8 关键路径关键路径8/6/20246精选课件 图图是由一个是由一个顶点集顶点集 V 和一个和一个弧集弧集 R构成构成的数据结构。的数据结构。Graph=(V,VR)其中，VR|v,wV 且 P(v,w)表示从 v 到 w 的一条弧，并称 v 为弧头弧头，w 为弧尾弧尾。谓词 P(v,w)定义了弧 的意义或信息。图的结构定义图的结构定义:7.1 图的定义与术语图的定义与术语8/6/20247精选课件 由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图有向图。AB E C D例如例如:G1=(V1,VR1)其中V1=A,B,C,D,EVR1=,8/6/20248精选课件若VR 必有VR,则称(v,w)为顶点v 和顶点 w 之间存在一条边边。B CA D F E由顶点集和边集构成的图称作无向图无向图。例如:G2=(V2,VR2)V2=A,B,C,D,E,FVR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)8/6/20249精选课件名词和术语名词和术语网、子图 完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林8/6/202410精选课件ABECFAEFBBC设图G=(V,VR)和图 G=(V,VR),且 VV,VRVR,则称 G 为 G 的子子图图。1597211132 弧或边带权的图分别称作有向网有向网或无向网无向网。C8/6/202411精选课件假设图中有 n 个顶点，e 条边，则 含有 e=n(n-1)/2 条边的无向图称作完全图完全图；含有 e=n(n-1)条弧的有向图称作 有向完全图有向完全图；若边或弧的个数 enlogn，则称作稀疏图稀疏图，否则称作稠密图稠密图。8/6/202412精选课件 假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点邻接点，ACDFE例如例如:ID(B)=3ID(A)=2 边(v,w)和顶点v 和w 相关联关联。和顶点v 关联的边的数目边的数目定义为顶点v的度度。B8/6/202413精选课件顶点的出度出度:以顶点v为弧尾的弧的数目；ABECF对有向图来说对有向图来说，顶点的入度入度:以顶点v为弧头的弧的数目。顶点的度度(TD)=)=出度出度(OD)+)+入度入度(ID)例如例如:ID(B)=2OD(B)=1TD(B)=38/6/202414精选课件设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1,vi,m=w中，(vi,j-1,vi,j)VR 1jm,则称从顶点u 到顶点w 之间存在一条路径路径。路径上边(或弧)的数目称作路径长度路径长度。ABECF如如:长度为3的路径A,B,C,F简单路径简单路径:序列中顶点不重复出现的路径。简单回路简单回路:序列中第一个顶点和最后一个顶点相同的路径而其余顶点不重复。8/6/202415精选课件若图G中任意两个顶点之间都有路径相通，则称此图为连通图连通图；若无向图为非连通图，则图中各个极大连通子图称作此图的连通连通分量分量。BACDFEBACDFE8/6/202416精选课件 若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图强连通图。ABECFABECF对有向图，对有向图，否则，其各个强连通子图称作它的强连通分量强连通分量。8/6/202417精选课件 假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林生成森林。BACDFE8/6/202418精选课件结构的建立和销毁结构的建立和销毁插入或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作对顶点的访问操作对顶点的访问操作遍历遍历插入和删除弧插入和删除弧基本操作基本操作8/6/202419精选课件CreatGraph(&G,V,VR):/按定义(V,VR)构造图DestroyGraph(&G):/销毁图结构的建立和销毁结构的建立和销毁8/6/202420精选课件对顶点的访问操作对顶点的访问操作LocateVex(G,u);/若G中存在顶点u，则返回该顶点在/图中“位置位置”；否则返回其它信息。GetVex(G,v);/返回 v 的值。PutVex(&G,v,value);/对 v 赋值value。8/6/202421精选课件对邻接点的操作对邻接点的操作FirstAdjVex(G,v);/返回 v 的“第一个邻接点第一个邻接点”。若该顶点/在 G 中没有邻接点，则返回“空”。NextAdjVex(G,v,w);/返回 v 的（相对于 w 的）“下一个邻接下一个邻接/点点”。若 w 是 v 的最后一个邻接点，则/返回“空”。8/6/202422精选课件插入或删除顶点插入或删除顶点InsertVex(&G,v);/在图G中增添新顶点v。DeleteVex(&G,v);/删除G中顶点v及其相关的弧。8/6/202423精选课件插入和删除弧插入和删除弧InsertArc(&G,v,w);/在G中增添弧，若G是无向的，/则还增添对称弧。DeleteArc(&G,v,w);/在G中删除弧，若G是无向的，/则还删除对称弧。8/6/202424精选课件遍遍 历历DFSTraverse(G,v,Visit();/从顶点v起深度优先深度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit();/从顶点v起广度优先广度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。8/6/202425精选课件7.2 图的存储表示图的存储表示一、一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示8/6/202426精选课件Aij=0 (i,j)VR1 (i,j)VR一、一、图的数组(邻接矩阵)存储表示BACDFE定义定义:矩阵的元素为矩阵的元素为8/6/202427精选课件有向图的邻接矩阵有向图的邻接矩阵为非对称矩阵为非对称矩阵ABECF8/6/202428精选课件typedef struct ArcCell /弧的定义弧的定义 VRType adj;/VRType是顶点关系类型。/对无权图，用1或0表示相邻否；/对带权图，则为权值类型。InfoType *info;/该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;8/6/202429精选课件typedef struct /图的定义图的定义 VertexType /顶点信息 vexsMAX_VERTEX_NUM;AdjMatrix arcs;/弧的信息 int vexnum,arcnum;/顶点数，弧数 GraphKind kind;/图的种类标志 MGraph;8/6/202430精选课件0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE二、图的邻接表二、图的邻接表 存储表示存储表示8/6/202431精选课件1 4230 120 1 2 3 4 A B C D E有向图的邻接表有向图的邻接表ABECD可见，在有向图的邻接表中不易找到指向该顶点的弧。8/6/202432精选课件ABECD有向图的逆邻接表有向图的逆邻接表A B C D E 303420 01234在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。8/6/202433精选课件typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条弧的指针 InfoType *info;/该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构弧的结点结构8/6/202434精选课件typedef struct VNode VertexType data;/顶点信息 ArcNode *firstarc;/指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;data firstarc顶点的结点结构顶点的结点结构8/6/202435精选课件typedef struct AdjList vertices;int vexnum,arcnum;int kind;/图的种类标志 ALGraph;图的结构定义图的结构定义8/6/202436精选课件三、有向图的十字链表存储表示三、有向图的十字链表存储表示 弧的结点结构弧的结点结构弧尾顶点位置 弧头顶点位置 弧的相关信息指向下一个有相同弧尾有相同弧尾的结点指向下一个有相同弧头有相同弧头的结点typedef struct ArcBox /弧弧的结构表示的结构表示 int tailvex,headvex;InfoType *info;struct ArcBox *hlink,*tlink;VexNode;8/6/202437精选课件顶点的结点结构顶点的结点结构顶点信息数据 指向该顶点的第一条入弧第一条入弧指向该顶点的第一条出弧第一条出弧typedef struct VexNode /顶点的结构表示顶点的结构表示 VertexType data;ArcBox *firstin,*firstout;VexNode;8/6/202438精选课件typedef struct VexNode xlistMAX_VERTEX_NUM;/顶点结点(表头向量)int vexnum,arcnum;/有向图的当前顶点数和弧数 OLGraph;有向图的结构表示有向图的结构表示(十字链表十字链表)8/6/202439精选课件四、无向图的邻接多重表存储表示typedef struct Ebox VisitIf mark;/访问标记 int ivex,jvex;/该边依附的两个顶点的位置 struct EBox *ilink,*jlink;/分别指向依附这两个顶点的下一条边 InfoType *info;/该边信息指针 EBox;边的结构表示边的结构表示8/6/202440精选课件typedef struct /邻接多重表邻接多重表 VexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;AMLGraph;顶点的结构表示顶点的结构表示typedef struct VexBox VertexType data;EBox *firstedge;/指向第一条依附该顶点的边 VexBox;无向图的结构表示无向图的结构表示8/6/202441精选课件7.3 图的遍历图的遍历 从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。深度优先搜索深度优先搜索广度优先搜索广度优先搜索遍历应用举例遍历应用举例8/6/202442精选课件 从图中某个顶点V0 出发，访问此顶点，然后依次从依次从V0的各个未被访问的邻接的各个未被访问的邻接点出发深度优先搜索遍历图点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。一、深度优先搜索遍历图一、深度优先搜索遍历图连通图的深度优先搜索遍历连通图的深度优先搜索遍历8/6/202443精选课件Vw1SG1SG2SG3W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。访问顶点 V：for(W1、W2、W3)若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。w2w3w28/6/202444精选课件从上页的图解可见从上页的图解可见:1.从深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点设立一个“访问标志 visitedw”。2.如何判别V的邻接点是否被访问？8/6/202445精选课件void DFS(Graph G,int v)/从顶点从顶点v出发，出发，深度优先搜索遍历连通图深度优先搜索遍历连通图 G visitedv=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w /递归调用DFS/DFS8/6/202446精选课件 首先将图中每个顶点的访问标志设为 FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。非连通图的深度优先搜索遍历非连通图的深度优先搜索遍历8/6/202447精选课件void DFSTraverse(Graph G,Status(*Visit)(int v)/对图对图 G 作深度优先遍历。作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;vw1,V-w2,V-w8 的路径长度为1；V-w7,V-w3,V-w5 的路径长度为2；V-w6,V-w4 的路径长度为3。w1Vw2w7w6w3w8w5w48/6/202450精选课件 从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问未被访问过的邻接点，之后按这些顶点被访问的先后次按这些顶点被访问的先后次序依次访问它们的邻接点序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。8/6/202451精选课件 void BFSTraverse(Graph G,Status(*Visit)(int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化访问标志 InitQueue(Q);/置空的辅助队列Q for(v=0;vnext=Q.rear-next=NULLvoid EnQueue(LinkQueue&Q,QelemType e)p=(QueuePtr)malloc(sizeof(QNode);p-data=e;p-next=NULL;p-prior=Q.front Q.rear-next=p;Q.rear=p;void DeQueue(LinkQueue&Q,QelemType&e)Q.front=Q.front-next;e=Q.front-data8/6/202462精选课件7.4 (连通网的连通网的)最小生成树最小生成树 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前如何在最节省经费的前提下建立提下建立这个通讯网通讯网？问题：问题：8/6/202463精选课件 构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和权值之和”为最小。算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）该问题等价于：该问题等价于：算法一：（普里姆算法）算法一：（普里姆算法）8/6/202464精选课件 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在待添在待添加的顶点加的顶点 w 和已经在生成树上的顶点和已经在生成树上的顶点v 之之间必定存在一条边，并且该边的权值在所间必定存在一条边，并且该边的权值在所有连通顶点有连通顶点 v 和和 w 之间的边中取值最小之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n个顶点为止。普里姆算法的基本思想普里姆算法的基本思想:8/6/202465精选课件abcdegf例如例如:195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=678/6/202466精选课件 在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U，则应在所有连通在所有连通U中顶点和中顶点和V-U中中顶点的边中选取权值最小的边顶点的边中选取权值最小的边。一般情况下所添加的顶点应满足下列条件:8/6/202467精选课件 设置一个辅助数组，对当前设置一个辅助数组，对当前VU集集中的每个顶点，记录和顶点集中的每个顶点，记录和顶点集U中顶点中顶点相连接的代价最小的边：相连接的代价最小的边：struct VertexType adjvex;/U集中的顶点序号 VRType lowcost;/边的权值 closedgeMAX_VERTEX_NUM;8/6/202468精选课件abcdegf195141827168213ae12dcb7aaa19141814例如例如:e12ee8168d3dd7213c5 58/6/202469精选课件void MiniSpanTree_P(MGraph G,VertexType u)/用普里姆算法从顶点u出发构造网G的最小生成树 k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始，Uu for(i=0;iG.vexnum;+i)继续向生成树上添加顶点继续向生成树上添加顶点;8/6/202470精选课件 k=minimum(closedge);/求出加入生成树的下一个顶点(k)printf(closedgek.adjvex,G.vexsk);/输出生成树上一条边 closedgek.lowcost=0;/第k顶点并入U集 for(j=0;jG.vexnum;+j)/修改其它顶点的最小边 if(G.arcskj.adj closedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;8/6/202471精选课件具体做法具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。考虑问题的出发点考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：8/6/202472精选课件abcdegf195141827168213ae12dcbgf7148531621例如例如:71218198/6/202473精选课件算法描述算法描述:构造非连通图 ST=(V,);k=i=0;/k 计选中的边数 while(kadjvex;DFSArticul(G,v);/从第v顶点出发深度优先搜索 if(count nextarc)void DFSArticul(ALGraph G,int v0)/从第v0个顶点出发深度优先遍历图 G,/查找并输出关节点/DFSArticulmin=visitedv0=+count;/v0是第是第count个访问的顶点个访问的顶点,并设并设lowv0的初值为的初值为min/检查v0的每个邻接点lowv0=min;8/6/202485精选课件 w=p-adjvex;/w为v0的邻接顶点 if(visitedw=0)/w未曾被访问 DFSArticul(G,w);/返回前求得loww else /w是回边上的顶点if(loww=visitedv0)printf(v0,G.verticesv0.data);/输出关节点输出关节点if(visitedw min)min=visitedw;8/6/202486精选课件7.6 两点之间的两点之间的 最短路径问题最短路径问题 求从某个源点到其余各点的求从某个源点到其余各点的最短路径最短路径 每一对顶点之间的最短路径每一对顶点之间的最短路径 8/6/202487精选课件 求求从源点到其余各点的最短路径从源点到其余各点的最短路径的算法的基本思想的算法的基本思想:依依最短路径的长度最短路径的长度递增的次序求得各递增的次序求得各条路径条路径源点源点v1其中，从源点到从源点到顶点顶点v的最短路径的最短路径是所有路径中长度最短者。v28/6/202488精选课件 在这条路径上，必定只含一条弧，并且这条弧的权值最小。下一条路径长度次短的最短路径最短路径的特点：路径长度最短的最短路径最短路径的特点：它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。8/6/202489精选课件其余最短路径的特点：再下一条路径长度次短的最短路径最短路径的特点:它可能有三种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。8/6/202490精选课件求最短路径的迪杰斯特拉算法：一般情况下，Distk=或者=+。设置辅助数组Dist，其中每个分量Distk 表示 当前所求得的从源点到其余各顶点 k 的最短路径。8/6/202491精选课件1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的Distk值。假设求得最短路径的顶点为u，若若 Distu+G.arcsukDistk则将 Distk 改为 Distu+G.arcsuk。V0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度其中的最小值即为最短路径的长度。8/6/202492精选课件求每一对顶点之间的最短路径弗洛伊德算法的基本思想是：从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径。8/6/202493精选课件若存在，则存在路径vi,vj /路径中不含其它顶点若,存在，则存在路径vi,v1,vj /路径中所含顶点序号不大于1若vi,v2,v2,vj存在，则存在一条路径vi,v2,vj /路径中所含顶点序号不大于2 依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。8/6/202494精选课件7.7 拓扑排序拓扑排序 问题问题:假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序拓扑排序。8/6/202495精选课件何谓何谓“拓扑排序拓扑排序”？对有向图进行如下操作：按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。8/6/202496精选课件例如：对于下列有向图BDAC可求得拓扑有序序列：A B C D 或 A C B D由此所得顶点的线性序列称之为拓扑有序序列8/6/202497精选课件BDAC反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路 B,C,D8/6/202498精选课件如何进行拓扑排序？如何进行拓扑排序？一、从有向图中选取一个没有前驱没有前驱 的顶点，并输出之；重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。二、从有向图中删去此顶点以及所删去此顶点以及所 有以它为尾的弧有以它为尾的弧；8/6/202499精选课件abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念 没有前驱的顶点没有前驱的顶点 入度为零的顶点入度为零的顶点删除顶点及以它为尾的弧删除顶点及以它为尾的弧 弧头顶点的入度减弧头顶点的入度减18/6/2024100精选课件取入度为零的顶点v;while(v0)printf(v);+m;w:=FirstAdj(v);while(w0)inDegreew-;w:=nextAdj(v,w);取下一个入度为零的顶点v;if mn printf(“图中有回路”);算算法法描描述述8/6/2024101精选课件 为避免每次都要搜索入度为零的顶点，在算法中设置一个“栈栈”，以保存“入度为零”的顶点。CountInDegree(G,indegree);/对各顶点求入度InitStack(S);for(i=0;iG.vexnum;+i)if(!indegreei)Push(S,i);/入度为零的顶点入栈8/6/2024102精选课件count=0;/对输出顶点计数while(!EmptyStack(S)Pop(S,v);+count;printf(v);for(w=FirstAdj(v);w;w=NextAdj(G,v,w)-indegree(w);/弧头顶点的入度减一 if(!indegreew)Push(S,w);/新产生的入度为零的顶点入栈 if(countG.vexnum)printf(“图中有回路”)8/6/2024103精选课件7.8 关键路径关键路径问题问题:假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。8/6/2024104精选课件abcdefghk64521187244例如例如:“关键活动”指的是：该弧上的权值增加权值增加 将使有向图上的最长路径的长度增加。最长路径的长度增加。整个工程完成的时间为：从有向图的源点源点到汇点汇点的最长路径。源点汇点61748/6/2024105精选课件 如何求关键活动？如何求关键活动？“事件(顶点)”的 最早发生时间 ve(j)ve(j)=从源点到顶点j的最长路径长度；“事件(顶点)”的 最迟发生时间 vl(k)vl(k)=从顶点k到汇点的最短路径长度。8/6/2024106精选课件 假设第 i 条弧为 则 对第 i 项活动言 “活动(弧)”的 最早开始时间 ee(i)ee(i)=ve(j)；“活动(弧)”的 最迟开始时间 el(i)el(i)=vl(k)dut()；8/6/2024107精选课件 事件发生时间的计算公式：ve(源点)=0；ve(k)=Maxve(j)+dut()j为所有以k为弧头的顶点集 vl(汇点)=ve(汇点)；vl(j)=Minvl(k)dut()k为所有以j为弧尾的顶点集8/6/2024108精选课件abcdefghk645211872440000000006457115 715 14 1818181818181818181816 1486610807拓扑有序序列拓扑有序序列:a-d-f-c-b-e-h-g-k8/6/2024109精选课件06457715 14 181814161078660000645777 15 14141602366887 108/6/2024110精选课件 算法的实现要点算法的实现要点:显然，求ve的顺序应该是按拓扑有序拓扑有序的次序；而 求vl的顺序应该是按拓扑逆序拓扑逆序的次序；因为 拓扑逆序序列即为拓扑有序序列的 逆序列逆序列，因此 应该在拓扑排序的过程中，另设一个“栈栈”记下拓扑有序序列。8/6/2024111精选课件【本章小结】【本章小结】图是一种比线性表和树更复杂的数据结构。在线性表图是一种比线性表和树更复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间直接前驱和一个直接后继。在树形结构中，数据元素之间存在着明显的层次关系，并且每层的元素可能和下一层的存在着明显的层次关系，并且每层的元素可能和下一层的多个元素（即其孩子结点）相邻，但只能和上一层的一个多个元素（即其孩子结点）相邻，但只能和上一层的一个元素（即其双亲结点）相关。而在图形结构中，结点之间元素（即其双亲结点）相关。而在图形结构中，结点之间的关系可以是任意的，图中任意两个元素之间都可能相邻。的关系可以是任意的，图中任意两个元素之间都可能相邻。和树类似，图的遍历是图的一种主要操作，可以通过和树类似，图的遍历是图的一种主要操作，可以通过遍历判别图中任意两个顶点之间是否存在路径、判别给定遍历判别图中任意两个顶点之间是否存在路径、判别给定的图是否是连通图并可求得非连通图的各个连通分量，但的图是否是连通图并可求得非连通图的各个连通分量，但对于带权图（网），其最小生成树或最短路径都取决于弧对于带权图（网），其最小生成树或最短路径都取决于弧或边上的权值，则需要有特定的算法求解。或边上的权值，则需要有特定的算法求解。8/6/2024112精选课件重庆工商大学重庆工商大学计算计算机与信息工程学院机与信息工程学院8/6/2024113精选课件