数据结构课件第5章12

第五章图5.1图的基本概念5.2图的存储结构5.3图的遍历5.4连通图与生成树5.5有向无环图及应用第五章图5.1图的概念一图的概念二图的应用三图的基本术语四图的基本操作§5.1图的基本概念一图的概念图的定义：图G由两个集合V,E构成，记作G=<V,E>其中V是顶点的非空有限集合，E是边的有限集合（边是顶点的无序对或有序对集合）。G1=<V1,E1>V1={v0,v1,v2,v3,v4}E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}G1图示无序对(vi,vj)：用连接顶点vi、vj的线段表示，称为无向边；例§5.1图的基本概念G2图示有序对<vi,vj>：用以vi为起点、vj为终点的有向线段表示，称为有向边或弧；无向图：在图G中，若所有边是无向边，则称G为无向图；有向图：在图G中，若所有边是有向边，则称G为有向图；G2=<V2,E2>V2={v0v1,v2,v3}E2={<v0,v1>,<v0,v2>,<v2,v3>,<v3,v0>}§5.1图的基本概念 图的应用举例例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系§7.1图的基本概念1邻接顶点及关联边邻接顶点：边e=(v,u)，则称顶点v、u相邻接关联边：边e=(v,u),则称边e关连顶点v、u2顶点的度、入度、出度顶点V的度=与V相关联的边的数目在有向图中：顶点V的出度=以V为起点的有向边数顶点V的入度=以V为终点的有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n，边数为e图的所有顶点的度数和=2*e（每条边对图的所有顶点的度数和“贡献”2度）e 图的基本术语§5.1图的基本概念 路径、回路无向图G=（V，E）中的顶点序列v1,v2,…,vk,若(vi,vi+1)E(i=1,2,…k-1),v=v1,u=vk,则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；有向图D=（V，E）中的顶点序列v1,v2,…,vk,若<vi,vi+1>E(i=1,2,…k-1),v=v1,u=vk,则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；在图1中，V0,V1,V2,V3是V0到V3的路径；V0,V1,V2,V3,V0是回路；在图2中，V0,V2,V3是V0到V3的路径；V0,V2,V3,V0是回路；无向图G1有向图G2例 简单路径和简单回路 在一条路径中,若除起点和终点外,所有顶点各不相同,则称该路径为简单路径； 由简单路径组成的回路称为简单回路； 在图1中，V0,V1,V2,V3是简单路径；V0,V1,V2,V4,V1不是简单路径；在图2中，V0,V2,V3,V0是简单回路；无向图G1有向图G2例 连通图（强连通图）在无（有）向图G=<V,E>中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）非连通图连通图强连通图非强连通图 子图设有两个图G=（V，E）、G1=（V1，E1），若V1V，E1E，E1关联的顶点都在V1中，则称G1是G的子图；例(b)、(c)是(a)的子图(a)(b)(c)§5.1图的基本概念 连通分量（强连通分量）无向图G的极大连通子图称为G的连通分量极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通；连通分量非连通图非连通分量有向图D的极大强连通子图称为D的强连通分量极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的；§5.1图的基本概念连通图G1G1的生成树四图的基本操作P156第五章图5.2图的存储结构一邻接矩阵二邻接表§5.2图的存储结构图的存储结构至少要保存两类信息： 1)顶点的数据2)顶点间的关系约定:G=<V,E>是图,V={v0,v1,v2,…vn-1},设顶点的数据为它的编号如何表示顶点间的关系？一、邻接矩阵图的邻接矩阵表示法（AdjacencyMatrix）也称作数组表示法。采用两个数组来表示图：一个是用于存储顶点信息的一维数组；另一个用于存储图中顶点之间关联关系的二维数组----邻接矩阵。若图G是一个具有n个顶点的无权图，G的邻接矩阵是n×n矩阵A：若<vi,vj>或(vi,vj)∈E反之§5.2图的存储结构邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：邻接矩阵表示在数组表示法中，用邻接矩阵表示顶点间的关系若图G是一个有n个顶点的网，则它的邻接矩阵是具有如下性质的n×n矩阵A：若<vi,vj>或(vi,vj)∈E反之例如：一个有向网N,其邻接矩阵?§5.2图的存储结构无向图邻接矩阵表示法特点：1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；2）顶点vi的度：等于二维数组i行（或列）中1的个数；3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1；4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；数组表示法的空间代价只与图的顶点数有关§5.2图的存储结构图的基本操作：1）求无向图某顶点vi的度(或有向图中vi的出度)。A[I,0]到A[I,n-1]中的非0个数，即数组A中第i行的非0元素的个数；2）求有向图某顶点vi的入度。：A[0,i]到A[n-1,i]中的非0个数，即数组A中第i列的非0元素的个数；3） 检测 工程第三方检测合同工程防雷检测合同植筋拉拔检测方案传感器技术课后答案检测机构通用要求培训 图中的总边数。扫描整个数组A，统计出数组中非0元素的个数。无向图的总边数为非0元素个数的一半，而有向图的总弧数为非0元素个数；§5.2图的存储结构 邻接表邻接表是图的链式存储结构1无向图的邻接表顶点：通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边：用线性链表存储该结点表示边（ViVj）,其中的1是Vj在一维数组中的位置例下标编号link§5.2图的存储结构图的邻接表类型定义(p163)typedefstructLnode//边（弧）结点的类型定义{intver;//边（弧）的另一顶点的在数组中的位置structLnode*link;//指下一条边（弧）结点的指针};structLnodeadjlist[MAX];//邻接点链表的头指针所对应的数组§5.2图的存储结构无向图的邻接表的特点1）在G邻接表中，同一条边对应两个结点(0->1,1->0)；2）顶点v的度：等于v对应线性链表的长度；3）判定两顶点v，u是否邻接：要看v对应线性链表中有无对应的结点u4)适用于边稀疏的图邻接表的空间代价与图的边及顶点数均有关2§5.2图的存储结构2有向图的邻接表和逆邻接表1）有向图的邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储类似于无向图的邻接表，所不同的是：以同一顶点为起点的弧：用线性链表存储下标编号link0123m-1例§5.2图的存储结构2）有向图的逆邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储类似于有向图的邻接表，所不同的是：以同一顶点为终点弧：用线性链表存储例§5.2图的存储结构建立无向图邻接表的算法intcreate(structLnode*adjlist[]){intnum,i,v1,v2;scanf(“%d\n”,&num);//读入顶点数for(i=0;i<num;i++)//初始化空关系图{adjlist[i].link=NULL;adjlist[i].ver=i;}§5.2图的存储结构for(i=0;i<E;i++)//E为边数{scanf(“%dto%d\n”,&v1,&v2);//读入一条边if(v1<0||v2<0)break;//数据输入的终止条件p=(LNODE*)malloc(sizeof(LNODE));p->ver=v2;p->link=adjlist[v1].link;adjlist[v1].link=p;//插入在链表首部p=(LNODE*)malloc(sizeof(LNODE));p->ver=v1;p->link=adjlist[v2].link;adjlist[v2].link=p;}return(num);//返回图的顶点数}§5.2图的存储结构在不同的存储结构下，实现各种操作的效率可能是不同的。所以在求解实际问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 时，要根据求解问题所需操作，选择合适的存储结构。第五章图§5.3图的遍历一深度优先遍历二广度优先遍历§5.3图的遍历图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。为保证每一个顶点只被访问一次，必须对顶点进行标记，当顶点vi未被访问，值为0；当vi已被访问，则值为1。图的遍历有两种遍历方法（对无向图，有向图都适用）深度优先遍历广度优先遍历§5.3图的遍历从图中某顶点v出发：1）访问顶点v；2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历；（1）V0,V1,V3,V7,V4,V2,V5,V6,由于没有规定访问邻接点的顺序，深度优先序列不是唯一的这是序列（1）在遍历过程中所经过的路径例一深度优先遍历求图G以V0为起点的的深度优先遍历序列：（2）V0,V1,V4,V7,V3,V2,V5,V6§5.3图的遍历如果将图顶点的邻接点看作二叉树结点的左、右孩子深度优先遍历与先序遍历是不是很类似？深度优先遍历从图中某顶点v出发：（1）访问顶点v；（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；先序遍历（DLR）若二叉树非空（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；§5.3图的遍历结点定义typedefstructLnode{intver;//边（弧）的另一顶点在数组中的位置structLnode*link;//指向下一条边（弧）结点的指针};structLNODEadjlist[MAX];//邻接链表的头指针所对应的数组深度优先遍历算法§5.3图的遍历voiddepthfirst(structLnode*adjlist,intV0){adjlist[V0].VEX=1;printf(“…”,v0);p=adjlist[v0].link;while(p!=null){if(adjlist[p->vex].vex==0)depthfirst(adjlist,p->vex);p=p->link;}}图深度优先遍历算法(邻接表)深度优先遍历§5.3图的遍历调用深度优先遍历算法的主函数main(){num=create(adjlist);//建立图G的邻接表for(i=0;i<num;i++)adjlist[i].vex=0;for(i=0;i<num;i++)depthfirst(adjlist,vi);//调用对图G深度优先搜索算法}深度优先遍历算法§5.3图的遍历图深度优先遍历§5.3图的遍历从图中某个未被访问过的顶点vi出发：1）访问顶点vi；2）访问vi的所有未被访问的邻接点w1,w2,…wk；3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；二广度优先遍历（类似于树的按层遍历）这是序列（1）在遍历过程中所经过的路径由于没有规定访问邻接点的顺序，广度优先序列不是唯一的例求图G的以V0起点的的广度优先序列V0,V1,V2,V3,V4,V5,V6,V7§5.3图的遍历从图中某顶点vi出发：1）访问顶点vi；（容易实现）2）访问vi的所有未被访问的邻接点w1,w2,…wk；（容易实现）3）依次从这些邻接点（在步骤2）访问的顶点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；为实现3），需要保存在步骤2）中访问的顶点，而且访问这些顶点邻接点的顺序为：先保存的顶点，其邻接点先被访问。广度优先遍历算法在广度优先遍历算法中，需设置一队列Q，保存已访问的顶点，并控制遍历顶点的顺序。广度优先遍历V0V1V2V3V4V5V6V7V1V2V3V0V4V5V6V7从图中某顶点v出发：1）访问顶点v；2）访问v的所有未被访问的邻接点w1,w2,…wk；3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；§5.3图的遍历voidBFS(structLnode*adjlist,intV0){iniqueue(q);adjlist[V0].VEX=1;printf(“…”,v0); enqueue(q,v0);while(notempty(q)){v0=dlqueue(q);p=adjlist[v0].link; while(p!=null) {if(adjlist[p->vex].vex==0) {adjlist[p->vex].vex=1; printf(“…”,p->vex); enqueue(q,p->vex); }p=p->link;}}//notempty}§5.3图的遍历深度优先遍历广度优先遍历两种遍历的比较P169算法7-4，7-6§5.4连通图与生成树1无向图的生成树生成树是一个连通图G的一个极小的连通子图。包含图G的所有顶点，但只有n-1条边，并且是连通的。生成树可由遍历过程中所经过的边组成。深度优先遍历得到的生成树称为深度优先生成树；广度优先遍历得到的生成树称为广度优先生成树。V0深度优先生成树广度优先生成树§5.4生成树§5.4生成树 要在n个城市间建立交通网，如何在保证n点连通的前题下最节省经费?例求解:连通6个城市且代价最小的交通线路?最小生成树若有一个连通的无向图G，有n个顶点，并且它的边是有权值的。在G上构造最小生成树G’–它的n-1条边的权值之和最小。§5.4最小的生成树普鲁姆算法基本步骤设G=（V，E）为一个具有n个顶点的带权的连通网络，T=（U，TE）为构造的生成树。（1）初始时，U={u0}，TE=；（2）在所有uU、vV-U的边（u,v）中选择一条权值最小的边，设为（u,v)；（3）如(u,v)加入T后不构成环，(u,v)加入TE，同时将u加入U；（4）重复(2)、（3），直到U=V为止；二普鲁姆算法---加顶点算法P175算法7-9§5.4最小的生成树U={V0}U={V0,V2}U={V0,V2,V5}U={V0,V2,V5,V3}U={V0,V2,V5,V3,V1}U={V0,V2,V5,V3,V1,V4}§5.4最小的生成树基本步骤设G=（V，E）为一个具有n个顶点的带权的连通网络，最小生成树的初始状态为有n个顶点但无边的非连通图T=（V，）。（1）将E中的边按权值的递增顺序排序，选择权值最小的边，若不构成环，则将其加入T中，否则，将其弃舍。（2）循环至有N-1条边。三克鲁斯卡尔算法----加边的算法§5.5最短路径交通咨询系统、通讯网、计算机网络常要寻找两结点间最短路径交通咨询系统：A到B最短路径计算机网发送Email节省费用A到B沿最短路径传送路径长度：路径上边数路径上边的权值之和最短路径：两结点间权值之和最小的路径例：求V0到V4最短路径V0到V4路径：V0V445V0V1V460V0V2V3V460V0V2V3V1V455最短路径问题第五章图§5.5有向无环图及应用一AOV网二拓扑排序三关键路径§5.6有向无环图的应用有向无环图：没有回路的有向图例某 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 可分为7个子工程，若用顶点表示子工程（也称活动），用弧表示子工程间的顺序关系。工程流程可用如下AOV网表示一AOV网------（activityonvertexnet)用顶点表示活动，边表示活动的顺序关系的有向图称为AOV网应用：工程流程、生产过程中各道工序的流程、程序流程、课程的流程§5.6有向无环图的应用对工程问题，人们至少关心如下两类问题：1）工程能否顺序进行，即工程流程是否“合理”2）完成整项工程至少需要多少时间，哪些子工程是影响工程进度的关键子工程为求解工程流程是否“合理”，通常用AOV网的有向图表示工程流程二拓扑排序1拓扑排序§5.6有向无环图的应用例课程流程图某校计算机专业课程流程可AOV网表示。其中顶点：表示课程（也称活动），弧：表示课程间的先修关系；如何安排施工 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 ？如何安排教学计划？§5.6有向无环图的应用一个可行的施工计划为：V0,V1,V2,V4,V3,V5,V6,一个可行的学习计划为：C1,C9,C4,C2,C10,C11,C12,C3,C6,C5,C7,C8可行的计划的特点：若在流程图中顶点v是顶点u的前趋，则在计划序列中顶点v也是u的前趋。§5.6有向无环图的应用拓扑序列：有向图D的一个顶点序列称作一个拓扑序列------如果该序列中任两顶点v、u，若在D中v是u前趋，则在序列中v也是u前趋。拓扑排序：将有向图中顶点排成拓扑序列。拓扑排序的应用安排施工计划（如上）判断工程流程的是否合理如何判断AOV网（有向图）是否存在有向回路？AOV网（有向图）不存在有向回路当且仅当能对AOV网进行拓扑排序§5.6有向无环图的应用2拓扑排序方法：1）在有向图选一无前趋的顶点v，输出；2）从有向图中删除v及以v为尾的孤；3）重复1、2、直接全部输出全部顶点或有向图中不存在无前趋顶点；例：V0,V1,V2,V3,V4,V5,V6拓扑排序算法P182算法7-12§5.6有向无环图的应用对工程人们关心两类问题：1）工程能否顺序进行，即工程流程是否“合理”2）完成整项工程至少需要多少时间，哪些子工程是影响工程进度的关键子工程？三AOE网与关键路径AOE网：用边表示活动，顶点表示事件，权表示活动持续的时间的网。顶点表示事件边表示活动事件Vj发生表示ak已结束事件Vi发生表示ak可以开始AOE网§5.5有向无环图及应用AOV网，AOE网，都能表示工程各子工程的流程，一个用顶点表示活动，一个用边表示活动，但AOV网侧重表示活动的前后次序，AOE网除表示活动先后次序，还表示了活动的持续时间等，因此可利用AOE网解决工程所需最短时间及哪些子工程拖延会影响整个工程按时完成等问题。完成工程的最短时间是从开始点到完成点的最长路径的长度。关键路径：最长的路径V1->V3->V4->V6实际应用中采用那一种图，取决于要求解的问题。§5.5最短路径 从某源点到其余各点的最短路径带权值的有向图的单源最短路径问题如何求从某源点到其余各点的最短路径？ Dijkstra算法的基本思想按路径长度递增顺序求最短路径算法。与求最小生成树的普里姆算法类似1迪杰斯特拉算法（Dijkstra） Dijkstra算法的基本步骤设V0是起始源点，U=已求得最短路径终点集合。V-U=未确定最短路径的顶点的集合初始时U={V0}1）长度最短的最短路径是边数为1的长度最小的路径。2）下一条长度最短的路径：①ViV-U，先求出V0到Vi中间只经U中结点的最短路径；②上述最短路径中长度最小者即为下一条长度最短的路径；③将所求最短路径的终点加入U中；3）重复2）直到求出所有的最短路径§5.5最短路径§5.6最短路径§5.6最短路径有关数据的存储结构有向连通网络:G，采用带权邻接矩阵cost[][]存储具体步骤：（1）初始U={v0},用辅助数组dist[N]。对已经找到最短路径终点的顶点vi(iU)，vi所对应的数组分量dist[i]的值为负数；对从v0出发，尚未确定为最短路径终点的顶点vj（jV-U)，vj所对应的数组分量dist[j]的值为Wvj，而Wvj为从v0出发，考虑途经已确定为终点的顶点，到达vj(V-U)的最短路径。初始时，对jV-U，有dist[j]=cost[v][j];而对U={v},则有dist[v]=-cost[v][v]。（2）扫描dist[]数组，找出非0、非负且最小的dist[j]（jV-U)，即从v0出发到vj（jV-U)的路径是最短的。（3）vj并入U，则dist[j]=-dist[j].（4）调整dist[k](kV-U)，考虑从v0出发，途经vj到达vk是否更短。比较：若-dist[j]+cost[j][k]<disk[k]则dist[k]=-disk[j]+cost[j][k](5)重复（2）（3）（4）。共n-1次。迪杰斯特拉算法涉及的数据和操作：§5.6最短路径求解步骤迪杰斯特拉算法的求解过程1220358303410(a)一个有向网点(b)源点0到其它顶点的初始距离21025430(334(210302583342104128334210(c)第一次求得的结果(d)第二次求得的结果44128334210128334210(e)第三次求得的结果(f)第四次求得的结果图5-27迪杰斯特拉算法求最短路径过程及结果§5.6最短路径voiddijstra(intcost[][N],intv){{intdist[N],i,j,wfor(i=0;i<N;i++)dist[i]=cost[v][i];//初始化dist[v]=-dist[v];for(i=0;i<N;i++){j=mincost(dist);//找非0、非负且最小的dist[j]if(j==0);break;dist[j]=-dist[j];//vj并入U中for(k=0;k<N;k++)//调整dist[k]if(dist[j]>0)//vk是尚未到达的终点if(-dist[j]+cost[j][k]<dist[k])dist[k]=-dist[j]+cost[j][k];//途经vj到达vk的距离更短}for(i=0;i<N;i++)if(dist[j]<0)printf(“%d,%d:%d\n”,v,i,-dist[i]);}Dijkstra算法intmincost(intdist[])//在V-U集合中找顶点j，dist[j]是dist[]中的最小值{inti,min,j;min=MAX;j=0;for(i=0;i<N;i++)if(dist[i]>=0&&dist[i]<min){min=dist[i];j=i;}return(j);}§5.6最短路径所有顶点对之间的最短路径1．顶点对之间的最短路径概念 所有顶点对之间的最短路径是指：对于给定的有向网G=(V,E),要对G中任意一对顶点有序对u、v(u≠v),找出u到v的最短距离和v到u的最短距离。解决此问题的一个有效方法是:轮流以每一个顶点为源点,重复执行迪杰斯特拉算法n次,即可求得每一对顶点之间的最短路径,总的时间复杂度为O(n3)。 2．弗洛伊德算法的基本思想弗洛伊德算法仍然使用前面定义的图的邻接矩阵cost[N][N]来存储带权有向图。算法的基本思想是:设置一个NxN的矩阵A[N][N]，其中除对角线的元素都等于0外，其它元素A[i][j]的值表示顶点i到顶点j的最短路径长度，运算步骤为：开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为∞，此时,A[i][j]=cost[i][j],以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为：第一步，让所有边上加入中间顶点0，取A[i][j]与A[i][0]+A[0][j]中较小的值作A[i][j]的值.因此，弗洛伊德算法可以描述为: A(0)[i][j]=cost[i][j];//cost为图的邻接矩阵 A(k)[i][j]=min{A(k-1)[i][j],A(k-1)[i][k]+A(k-1)[k][j]}其中k=0,1,2,…,n-1第二步，让所有边上加入中间顶点1，取A[i][j]与A[i][1]+A[1][j]中较小的值，完成后得到A[i][j]…，如此进行下去，当第n步完成后，得到A[i][j],即为我们所求结果,A[i][j]表示顶点i到顶点j的最短距离。3．弗洛伊德算法实现Voidfloyd(intcost[][N]){inta[N][N],i,j,k;for(i=0;i<N;i++)for(j=0;j<N;j++)a[i][j]=cost[i][j];//初始化for(k=0;k<N;k++)//考虑途经vk(k=0,1,..n-1)for(i=0;i<N;i++)for(j=0;j<N;j++)//图中每对顶点if(a[i][k]+a[k][j]<a[i][j])a[i][j]=a[i][k]+a[k][j];for(i=0;i<N;i++)//输出路径长度及路径for(j=0;j<N;j++)printf(“(%d,%d):%d”,i,j,a[i][j]);}算法的时间复杂度为O（N3),N为图的顶点数。§5.6有向无环图的应用1）拓扑排序方法的另一种描述(等价描述)（1）选择一入度为0顶点v，输出；（2）将v邻接到的顶点的入度减1；（3）重复1、2直到输出全部顶点或有向图没有入度为0的顶点；2）拓扑排序涉及的数据和操作：数据：有向图，顶点的入度；操作：（1）选择一入度为0顶点v，输出；（2）将v邻接到的顶点u的入度减1；structnode{intdegree;structnode*link;};typedefstructnodeNODE;3拓扑排序算法P182算法7-12§5.6有向无环图的应用3）有关数据的存储结构0123456有向图(AOV网)：G顶点的入度：intdegree整数栈intstack[]：用于存储入度为0的顶点的编号下标入度link0012232初始时，只有v0,v1两顶点的入度为0§5.6有向无环图的应用4）建立AOV网的邻接表算法intcreate(NODEadjlist[]){NODE*p;intnum,i,v1,v2;sanf(“%d\n”,&num);for(i=0;i<num;i++)//初始化空关系图{adjlist[i].link=NULL;adjlist[i].degree=0;}for(;;){scanf(“%dto%d\n”,&v1,&v2);//读入一条弧if(v1<0||v2<0)break;//数据输入的终止条件p=(NODE*)malloc(sizeof(NODE));p->vertex=v2;p->link=adjlist[v1].link;adjlist[v1].link=p;//插入在链表首部adjlist[v2].degree++;//统计每个顶点的入度}return(num);//返回图的结点数}§5.6有向无环图的应用5）拓扑排序算法inttoposort(NODEadjlist[],intnum)//有向图G采用邻接表存储结构。//若G无回路，则输出G的顶点的一个拓扑序列并返回1，否则0。{intstack[MAX];//存放入度为0的顶点的栈inti,top,out,k;NODE*p;intnum1=0;top=0;for(i=0;i<num;i++)if(adjlist[i].vertex==0)//入度为0顶点的编号进栈{stack[top]=i;top++;}§5.6有向无环图的应用while(top>0){top--;out=stack[top];printf(“%d,”,out);num1++;p=adjlist[out].link;while(p!=NULL){k=p->vertex;adjlist[k].vertex--;//顶点入度减1，if(adjlist[k].vertex==0)//若入度减为0，则入栈{stack[top]=k;top++;}p=p->link;}}if(num1<num)return(0);//该有向图有回路elsereturn(1);}§5.6有向无环图的应用V1开始事件,V6结束事件事件vj的最早发生时间ve[j]:事件vj的最迟发生时间vl[i]:指在不推迟整个工期的前提下，事件vj的最晚发生时间活动ak的最早开始时间e[k]活动ak的最晚开始时间1[i]:指在不推迟整个工期的前提下，事件akj的最晚发生时间活动ak的延迟时间diff[k]§5.6有向无环图的应用1事件vj的最早发生时间ve[j]ve[1]=0ve[j]=Max{ve(i)+dut(<i,j>)}ve[j]=从源点到顶点vj的最长路径的长度i2事件vj的最迟发生时间vl[i]ve[j]=从顶点vj终点到的最长路径的长度。vl[n]=ve[n]vl[j]=Min{vl(k)-dut(<j,k>)}vli]=vl[n]-从顶点vj终点到的最长路径的长度k3活动ak的最早开始时间e[k]设ak=<i,j>,e[k]=ve[i]4活动ak的最晚开始时间1[i]1[k]=vl[j]-dur(<i,j>)5活动ak的延迟时间diff[k]diff[k]=1[k]-e[k]把活动ai的最晚开始时间1[i]与最早开始时间e[i]之差定义为活动ai的延迟时间§5.6有向无环图的应用6关键活动对于活动ai，若有1[i]-e[i]=0为关键活动，由关键活动组成的路径就是关键路径。§5.3图的遍历voiddfs(intv){intw;printf(“%d,“,v);visit[v]=1;//访问此结点while(ptr[v]！=NULL）{w=ptr[v]->vertex;取结点的邻接顶点wif(visit[w]==0;)dfs(w);ptr[v]=ptr[v]->link;//记住顶点v的邻接顶点位置，}该邻接点在w之后}从第v个顶点出发，递归地深度优先遍历图G。图的十字链表弧结点、顶点结点结构图十字链表有向图G1的十字链表图的十字链表结构形式化定义如下：＃defineMAX-VERTEX-NUM10/*最多顶点个数*/typedefenum{DG,DN,UDG,UDN}GraphKind;/*图的种类*/typedefstructArcNode{inttailvex,headvex;structArcNode*hlink,*tlink;}ArcNode;typedefstructVertexNode{VertexDatadata;/*顶点信息*/ArcNode*firstin,*firstout;}VertexNode;typedefstruct{VertexNodevertex［MAX-VERTEX-NUM］;intvexnum,arcnum;/*图的顶点数和弧数*/GraphKindkind;/*图的种类*/}OrthList;/*图的十字链表表示法(OrthogonalList)*/建立一个有向图的十字链表的算法如下：voidCrtOrthList（OrthListg）/*从终端输入n个顶点的信息和e条弧的信息，以建立一个有向图的十字链表*/{scanf(″%d,%d″,&n,&e);/*从键盘输入图的顶点个数和弧的个数*/for(i=0;i<n;i++){scanf(″%c″,g.vertex［i］.data）；g.vertex［i］.firstin=NULL；g.vertex［i］.firstout=NULL；}for(k=0;k<e;k++){scanf(″%c,%c″,&vt,&vh);i=LocateVertex（g，vt）；j=LocateVertex（g，vh）；p=alloc(sizeof(ArcNode));p->tailvex=i；p->headvex=j；p->tlink=g.vertex［i］.firstout；g.vertex［i］.firstout=p；p->hlink=g.vertex［j］.firstin；g.vertex［j］.firstin=p；}}/*CrtOrthList*/邻接多重表邻接多重表的结点结构邻接多重表的结构类型说明如下：typedefstructEdgeNode{intmark,ivex,jvex;structEdgeNode*ilink,*jlink;}EdgeNode;typedefstruct{VertexDatadata;EdgeNode*firstedge;}VertexNode;typedefstruct{VertexNodevertex［MAX-VERTEX-NUM］;intvexnum,arcnum;/*图的顶点数和弧数*/GraphKindkind;/*图的种类*/}AdjMultiList;/*基于图的邻接多重表表示法(AdjacencyMulti-list)*/无向图的邻接多重表表示§5.3图的遍历如果将图顶点的邻接点看作二叉树结点的左、右孩子深度优先遍历算法与先序遍历算法的结构是不是很像？深度优先遍历算法voiddfs(intv){intw;printf(“%d,“,v);visit[v]=1;//访问此结点while(ptr[v]！=NULL）{w=ptr[v]->vertex;取结点的邻接顶点wif(visit[w]==0;)dfs(w);ptr[v]=ptr[v]->link;//记住顶点v的邻接点位置，}该邻接点在w之后}先序遍历递归算法 voidprev(NODE*root){if(root!=NULL){printf(“%d,”,root->data)；//访问此结点prev(root->lch);//访问孩子结点prev(root->rch);}}比较