图是一种比线性表和树更为复杂的数据结构解读课件

2019年6月30感谢你的观看1第七章 图n图是一种比线性表和树更为复杂的数据结构。在图中，元素间的关系是多对多的，即任何两个元素都有可能存在关系。n图的应用非常广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中(日常生活中的交通图等)。n在离散数学中，图论是专门研究图的性质的数学分支。n在数据结构中对图的讨论主要侧重于图在计算机中的存储方式和有关操作的算法。2019年6月30感谢你的观看1第七章 图图是一种比线性表和2019年6月30感谢你的观看2 图的基本内容n7.1 图的定义和术语n7.2 图的存储结构n7.3 图的遍历n7.4 图的连通性问题n7.5 有向无环图及其应用n7.6 最短路径2019年6月30感谢你的观看2 图的基本内容7.1 图2019年6月30感谢你的观看37.1 图的定义和术语抽象数据类型图的定义：ADT Graph 数据对象 V:V是具有相同特性的数据元素的集合，称为顶点集。数据关系 R:R=VR VR=|v,wV且P(v,w),表示从v到w的弧，谓词 P(v,w)定义了弧的意义或信息 基本操作 P:CreateGraph,DestroyGraph,LocateVex,GetVex,PutVex,FirstAdjVex,NextAdjVex,InsertVex,DeleteVex,InsertArc,DeleteArc,DFSTraverse,BFSTraverse ADT Graph2019年6月30感谢你的观看37.1 图的定义和术语抽象数2019年6月30感谢你的观看4图的定义(续)n图中的数据元素称为顶点(vertex),V是顶点的有穷非空集合；VR是V上顶点的序偶或无序对的集合。n若 VR，则 表示从v到w的一条弧(Arc),且称v为弧尾(Tail)或初始点(Initial node),称w为弧头(Head)或终端点(Terminal node),此时的图称为有向图(Digraph)。n若 VR必有 VR，即VR是对称的，则以无序对(v,w)代替两个有序对，表示 v和w之间的一条边(Edge),此时的图称为无向图(Undigraph)。可以说图由非空顶点集和边集所组成。2019年6月30感谢你的观看4图的定义(续)图中的数据元2019年6月30感谢你的观看5 图的示例无向图G1有向图G2图的二元组表示参见教材P1572019年6月30感谢你的观看5 图的示例无向图G1有向图2019年6月30感谢你的观看6图的基本术语n完全图、稠密图、稀疏图n约定：用n表示图中顶点的数目，用e表示边或弧的数目n若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。n当一个图接近完全图时，称为稠密图。n当一个图含有较少的边或弧(e0)for(i=1;i=num;i+)for(j=1;j=num;j+)adjarry ij=0;/*矩阵初始化*/do 2019年6月30感谢你的观看14产生无向图邻接矩阵算法vo2019年6月30感谢你的观看15 产生无向图邻接矩阵算法续 scanf(“%d,%d”,&v1,&v2);/*输入边*/adjarrayv1v2=1;adjarrayv2v1=1;while(v1!=0&v2!=0);else num=0;retrun num;2019年6月30感谢你的观看15 产生无向图邻接矩阵算法续2019年6月30感谢你的观看16 邻接表n邻接表是图的一种链式存储结构。n在邻接表结构中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于该顶点Vi的边，即对于无向图每个结点表示与该顶点相邻接的一个顶点；对于有向图则表示以该顶点为起点的一条边的终点。n一个图的邻接矩阵表示是唯一的，但其邻接表表示是不唯一的。因为在邻接表的每个单链表中，各结点的顺序是任意的。2019年6月30感谢你的观看16 邻接表邻接表是图的一种2019年6月30感谢你的观看17无向图、有向图 2019年6月30感谢你的观看17无向图、有向图 2019年6月30感谢你的观看18无向图的邻接表 2019年6月30感谢你的观看18无向图的邻接表 2019年6月30感谢你的观看19 有向图的邻接表2019年6月30感谢你的观看19 有向图的邻接表2019年6月30感谢你的观看20n邻接表中每个表结点均由两个域组成，其一是邻接点域（adjvex），用以存放与顶点Vi相邻接的顶点在图中的位置；其二是链域（next），用以指向依附于顶点Vi的下一条边所对应的结点。n如果用邻接表存放网络中的信息，则还需要在结点中增加一个存放权值的域。n在每个链表设一表头结点，一般这些表头结点本身以向量的形式存储。邻接表的若干说明2019年6月30感谢你的观看20邻接表中每个表结点均由两个2019年6月30感谢你的观看21n对于无向图的邻接表来说，一条边对应两个单链表结点，邻接表结点总数是边数的2倍。n在无向图的邻接表中，各顶点对应的单链表的结点数（不算表头结点）就等于该顶点的度数。n在有向图邻接表中，一条弧对应一个表结点，表结点的数目和弧的数目相同。n在有向图邻接表中，单链表的结点数就等于相应顶点的出度数。n要求有向图中某顶点的入度数，需扫视邻接表的所有单链表，统计与顶点标号相应的结点个数。邻接表的若干说明2019年6月30感谢你的观看21对于无向图的邻接表来说，一2019年6月30感谢你的观看22邻接表存储结构定义#define MAXVEX 30 struct edgenode int adjvex;/*邻接点域*/struct edgenode*next;/*链域*/;struct vexnode char data;/*顶点信息*/struct edgenode*link;typedef struct vexnode adjlistMAXVEX;2019年6月30感谢你的观看22邻接表存储结构定义#def2019年6月30感谢你的观看23生成无向图的邻接表算法void creategraph(adjlist g)int e,i,s,d,n;struct edgenode*p;printf(“请输入结点数(n)和边数(e):n”);scanf(“%d,%d”,&n,&e);for(i=1;i=n;i+)printf(“n请输入第%d个顶点信息：”,i);scanf(“%c”,&gi.data);gi.link=NULL;for(i=1;i=e;i+)2019年6月30感谢你的观看23生成无向图的邻接表算法vo2019年6月30感谢你的观看24生成无向图的邻接表算法续 printf(“n请输入第%d条边起点序号，终点序号：”,i);scanf(“%d,%d”,&s,&d);p=(struct edgenode*)malloc(sizeof(edgenode);padjvex=d;/*邻接点序号为d*/pnext=gs.link;gs.link=p;/*将新结点插入顶点Vs边表的头部*/p=(struct edgenode*)malloc(sizeof(edgenode);padjvex=s;/*邻接点序号为s*/pnext=gd.link;gd.link=p;/*将新结点插入顶点Vd边表的头部*/2019年6月30感谢你的观看24生成无向图的邻接表算法续 2019年6月30感谢你的观看25十字链表和邻接多重表简介n十字链表是将有向图的邻接表和逆邻接表结合起来得到的一种链表。n邻接多重表是无向图的另一种链式存储结构。在邻接多重表中，每一条边用一个结点表示，它由五个域组成；每一个顶点也用一个结点表示，它由两个域组成。2019年6月30感谢你的观看25十字链表和邻接多重表简介十2019年6月30感谢你的观看26 思考题n1.已知如下图所示的有向图，请给出该图的 （1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表。1562432019年6月30感谢你的观看26 思考题1.已知如下图所示2019年6月30感谢你的观看277.3 图的遍历n从图中某一顶点出发访遍图中其余结点，且使每一个顶点仅被访问一次，这一过程称为图的遍历(Traversing Graph).n图的遍历算法是求解图的连通性、拓扑排序和求关键路径等算法的基础。n为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。n图的遍历有两种：深度优先搜索和广度优先搜索。2019年6月30感谢你的观看277.3 图的遍历从图中某一2019年6月30感谢你的观看28 深度优先搜索(DFS)n类似于树的先根遍历，是树的先根遍历的推广。n首先访问图中某指定起始点Vi，然后由Vi出发访问它的任一相邻接顶点Vj,再从Vj出发访问Vj的任一未访问过的相邻接顶点Vk,再从Vk出发进行类似访问，如此进行下去，直到某顶点已没有未被访问过的相邻接顶点时，则退回一步，退到前一个顶点，找前一个顶点的其它尚未被访问的相邻接顶点。n如有未访问过的相邻接顶点，则访问此顶点后，再从该顶点出发向前进行与前述类似的访问；n如退回一步后，前一顶点也没有未被访问过的相邻接顶点，则再向回退一步进行搜索，重复上述过程，一直到所有顶点均被访问过为止。2019年6月30感谢你的观看28 深度优先搜索(DFS)2019年6月30感谢你的观看29 图的深度优先遍历例子深度优先遍历序列：1 2 4 8 5 3 6 72019年6月30感谢你的观看29 图的深度优先遍历例子深2019年6月30感谢你的观看30n由于图中的路径可能有环路，为了避免重复访问某些顶点，设计图的搜索算法时，可设置一个表示顶点是否被访问过的辅助数组visited，初始时将数组元素置零，一旦某顶点Vi被访问过，则令visitedVi=1，以后此顶点即不再访问。深度优先搜索算法2019年6月30感谢你的观看30由于图中的路径可能有环路，2019年6月30感谢你的观看31 深度优先搜索算法n深度优先搜索是一种递归的过程，可以简单地将其表示成递归的形式，其算法描述如下：DFS(V0)访问V0顶点;visitedV0=1;对所有与V0相邻接的顶点w if(visitedw=0)DFS(w);2019年6月30感谢你的观看31 深度优先搜索算法深度优2019年6月30感谢你的观看32邻接表表示的图的DFS算法 int visitedMAXVEX;void dfsgraph(adjlist adj,int n)int i;for(i=1;i=n;i+)visitedi=0;/*给visited数组赋初值*/for(i=1;i=n;i+)if(!visitedi)dfs(adj,i);2019年6月30感谢你的观看32邻接表表示的图的DFS算法2019年6月30感谢你的观看33邻接表存储结构定义#define MAXVEX 30 struct edgenode int adjvex;/*邻接点域*/struct edgenode*next;/*链域*/;struct vexnode char data;/*顶点信息*/struct edgenode*link;typedef struct vexnode adjlistMAXVEX;2019年6月30感谢你的观看33邻接表存储结构定义#def2019年6月30感谢你的观看34从Vi出发进行DFS的递归算法void dfs(adjlist adj,int v)struct edgenode*p;visitedv=1;printf(“%d”,v);p=adjvlink;while(p!=NULL)if(visitedpadjvex=0)dfs(adjlist,padjvex);/*从v未访问的邻接点出发进行DFS*/p=pnext;2019年6月30感谢你的观看34从Vi出发进行DFS的递归2019年6月30感谢你的观看35 时间复杂性分析n一个有n个顶点、e条边的图，在深度优先搜索图的过程中，找邻接点所需时间为O(e)。n对辅助数组初始化时间为O(n)。n因此，当用邻接表作为图的存储结构时，深度优先搜索图的时间复杂性为O(e+n)。2019年6月30感谢你的观看35 时间复杂性分析一个有n2019年6月30感谢你的观看36 非递归算法n从顶点Vi出发进行深度优先遍历的递归过程也可以写成非递归的形式，此时需借助一个堆栈保存被访问过的结点，以便回溯时查找已被访问结点的未被访问过的邻接点。n设堆栈由一个一维数组构成，数组名为stack，栈顶指针为top,假设此数组足够大,不必考虑溢出的可能。2019年6月30感谢你的观看36 非递归算法从顶点Vi2019年6月30感谢你的观看37非递归算法#define MAXVEX 100void dfs(adjlist g，int v,int n)/*从顶点v出发进行深度优先遍历*/struct vexnode *stackMAXVEX,*p;int visitedMAXVEX,top=0;for(i=1;i0|p!=NULL)2019年6月30感谢你的观看37非递归算法#define 2019年6月30感谢你的观看38非递归算法续 while(p!=NULL)if(visitedp-adjvex=1)p=p-next;else printf(“%d”,p-adjvex);visitedp-adjvex=1;top+;stacktop=p;p=gp-adjvex.link;2019年6月30感谢你的观看38非递归算法续2019年6月30感谢你的观看39非递归算法续 if(top0)top-;/*退栈，回溯查找已被访问结点的未被访问过的邻接点*/p=stacktop;p=p-next;2019年6月30感谢你的观看39非递归算法续 2019年6月30感谢你的观看40 广度优先搜索(BFS)n图的广度优先搜索（BFS）类似于树的按层次遍历。n广度优先搜索的基本思想是：首先访问图中某指定的起始点Vi并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、Vk，并均标记为已访问过，然后再按照Vj、Vk的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止。2019年6月30感谢你的观看40 广度优先搜索(BFS2019年6月30感谢你的观看41广度优先搜索(续)n在广度优先搜索中，若对顶点V1的访问先于顶点V2的访问，则对V1邻接顶点的访问也先于V2邻接顶点的访问。就是说广度优先搜索中对邻接点的寻找具有“先进先出”的特性。因此，为了保证访问顶点的这种先后关系，需借助一个队列暂存那些刚访问过的顶点。n设此队列由一个一维数组构成，数组名为Queue，队首指针和队尾指针分别为front和rear。假设数组足够大，不必考虑有溢出的可能性。n广度优先搜索不是递归过程，不能用递归形式。2019年6月30感谢你的观看41广度优先搜索(续)在广度优2019年6月30感谢你的观看42 图的广度优先遍历例子广度优先遍历序列：1 2 3 4 5 6 7 82019年6月30感谢你的观看42 图的广度优先遍历例子广2019年6月30感谢你的观看43 图的遍历举例n已知一有向图的邻接表存储结构如下页图所示，分别给出从顶点v1出发进行深度优先和广度优先遍历所得到的顶点序列。2019年6月30感谢你的观看43 图的遍历举例已知一有向2019年6月30感谢你的观看44 一个有向图的邻接表2019年6月30感谢你的观看44 一个有向图的邻接表2019年6月30感谢你的观看45例子解答n解：根据有向图的深度优先遍历算法，从顶点v1出发所得到的顶点序列是：v1，v3，v4，v5，v2 根据有向图的广度优先遍历算法，从顶点v1出发所得到的顶点序列是：v1，v3，v2，v4，v52019年6月30感谢你的观看45例子解答解：根据有向图的深2019年6月30感谢你的观看46BFS算法描述BFS(v0)BFS(v0)访问访问v0v0顶点；顶点；visitedv0=1;visitedv0=1;被访问过的顶点入队；被访问过的顶点入队；当队列非空时，进行下面的循环当队列非空时，进行下面的循环 （1 1）被访问过的顶点出队；）被访问过的顶点出队；（2 2）对所有与该顶点相邻接的顶点）对所有与该顶点相邻接的顶点w w if(visitedw=0)if(visitedw=0)(a)(a)访问访问w w顶点；顶点；(b)visitedw=1;(b)visitedw=1;(c)w (c)w入队入队;2019年6月30感谢你的观看46BFS算法描述BFS(v02019年6月30感谢你的观看47时间复杂性分析n一个有n个顶点、e条边的图，在广度优先搜索图的过程中，每个顶点至多进一次队列，图的搜索过程实质上是通过边来找顶点的过程，找邻接点所需时间为O(e)。n对辅助数组初始化时间为O(n)。n因此，当用邻接表作为图的存储结构时，广度优先搜索图的时间复杂性为O(e+n)。2019年6月30感谢你的观看47时间复杂性分析一个有n个顶2019年6月30感谢你的观看487.4 图的连通性问题 n无向图的连通分量和生成树n深度优先搜索或广度优先搜索在遍历无向图时，若无向图是连通图，则从图中任一顶点出发，便可访问到图中所有顶点。若无向图是非连通图，则需从多个顶点出发进行搜索，每次调用搜索过程得到的顶点访问序列恰为其各个连通分量中的顶点集。n遍历过程中经过的边的集合和图中所有顶点一起构成连通图的极小连通子图，为连通图的一棵生成树。分别有深度优先生成树和广度优先生成树。2019年6月30感谢你的观看487.4 图的连通性问题 无2019年6月30感谢你的观看49 生成树的进一步描述n在一个无向连通图G中，如果取它的全部顶点和一部分边构成一个子图G，若边集E(G)中的边刚好将图的所有顶点连通但又不形成环路，我们就称子图G是原图G的生成树（Spanning tree）。n生成树有如下特点：任意两个顶点之间有且仅有一条路径；如果再增加一条边就会出现环路；如果去掉一条边此子图就会变成非连通图。n一个有n 个顶点的完全图，一共存在n(n-2)种不同的生成树。2019年6月30感谢你的观看49 生成树的进一步描述在一个2019年6月30感谢你的观看50非连通图的生成森林n对于非连通图，每个连通分量中的顶点集，和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。n生成树和生成森林除依赖于遍历算法外，还依赖于采用的存储结构。2019年6月30感谢你的观看50非连通图的生成森林对于非连2019年6月30感谢你的观看51最小生成树n对于带权的连通图（连通网）G，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为最小生成树（Minimum Spanning Tree）。n具有n个顶点的连通图的生成树具有n-1条边（少于此边数不可能将各顶点连通，多于此边数则必然要出现环路）。2019年6月30感谢你的观看51最小生成树对于带权的连通图2019年6月30感谢你的观看52 无向连通图 G及其生成树n无向连通图无向连通图 G G 生成树生成树 2019年6月30感谢你的观看52 无向连通图 G及其生成2019年6月30感谢你的观看53 图G的其它生成树n生成树生成树最小生成树最小生成树2019年6月30感谢你的观看53 图G的其它生成树生成树最2019年6月30感谢你的观看54 普里姆(prim)算法描述n假设G=(V,E)是一个具有n 个顶点的连通网络，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空。n算法开始时，首先从V中任取一个顶点（假定为V1），将此顶点并入U中，此时最小生成树顶点集U=V1；n然后从那些其一个端点已在U中，另一个端点仍在U外的所有边中，找一条最短（即权值最小）的边，假定该边为(Vi,Vj),其中ViU，VjV-U,并把该边(Vi,Vj)和顶点Vj分别并入T的边集TE和顶点集U；2019年6月30感谢你的观看54 普里姆(prim)算法描2019年6月30感谢你的观看55普里姆(prim)算法描述续n如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后，把所有n 个顶点都并入生成树T的顶点集U中，此时U=V，TE中包含有（n-1）条边；n这样，T就是最后得到的最小生成树。n普里姆算法中每次选取的边两端，总是一个已连通顶点（在U集合内）和一个未连通顶点（在U集合外），故这个边选取后一定能将未连通顶点连通而又保证不会形成环路。2019年6月30感谢你的观看55普里姆(prim)算法描述2019年6月30感谢你的观看56普里姆算法例子2019年6月30感谢你的观看56普里姆算法例子2019年6月30感谢你的观看57普里姆算法n为了便于在顶点集合U和V-U之间选择权最小的边，建立两个数组closest和lowcost,closesti表示U中的一个顶点，该顶点与V-U中的一个顶点构成的边具有最小的权；lowcost表示该边对应的权值。n开始，由于U的初值为1，所以，closesti的值为1，i=2,n,而lowcosti为V1到各顶点的边中最小的权值。2019年6月30感谢你的观看57普里姆算法为了便于在顶点集2019年6月30感谢你的观看58算法分析n该算法中每一步执行都要扫描数组lowcost，在V-U顶点集中找出与U最近的顶点，令其为k，并打印边（k,closestk）。n然后将k加入U顶点集合中，并修改数组lowcost和closest。n这里用c表示图的邻接矩阵，cij和cji是边(i,j)的权。2019年6月30感谢你的观看58算法分析该算法中每一步执行2019年6月30感谢你的观看59克鲁斯卡尔（Kruskal）算法n假设G=（V，E）是一个具有n个顶点的连通网络，T=(U,TE)是G 的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空集。n基本思想：将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成环路，则把它并入TE中，保留作为生成树T的一条边，若选取的边使生成树T形成环路，则将其舍弃，如此进行下去，直到TE中包含n-1条边为止。此时的T即为最小生成树。2019年6月30感谢你的观看59克鲁斯卡尔（Kruskal2019年6月30感谢你的观看60 克鲁斯卡尔算法例子n(a)带权图2019年6月30感谢你的观看60 克鲁斯卡尔算法例子(a2019年6月30感谢你的观看61n(c)最小生成树2019年6月30感谢你的观看61(c)最小生成树2019年6月30感谢你的观看62克鲁斯卡尔算法续n在选取某边时如何判断是否与已保留的边形成环路？克鲁斯卡尔算法是通过将各顶点划分为集合的办法来解决的。n开始时假定n 个顶点分属于n个集合,即每个集合中有一个顶点,当确定某条边保留作为生成树的一条边时,就将该边两端点所属的两集合合并为一个,表示原来属于两个集合的各个顶点已被这条新的边连通.如果取到某条边,发现它的两个端点已属于同一集合时,此边则应当舍去.因为两个顶点属于同一集合说明它们已连通,若再添上这条边就会出现环路。n如此进行下去，到所有的顶点均已属于一个集合时，此最小生成树就构成了。2019年6月30感谢你的观看62克鲁斯卡尔算法续在选取某边2019年6月30感谢你的观看637.5 有向无环图及其应用n在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：n先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；n子项目之间无次序要求，即两个子项目可以同时进行，互不影响。n在工厂中，一件设备的生产包括许多工序，各工序之间也存在这两种关系。n学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。2019年6月30感谢你的观看637.5 有向无环图及其应用2019年6月30感谢你的观看64AOV网络n这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个个顶点称之为活动(Activity)。n如果从顶点Vi到Vj之间存在有向边,则表示活动i必须先于活动j进行。这种图称做顶点表示活动的网络(Activity On Vertex network,简称AOV网络)。n例如某校计算机专业的课程及其相互之间的关系，它对应的AOV网络如下页图所示。2019年6月30感谢你的观看64AOV网络这些类似的问题都2019年6月30感谢你的观看65 某专业课程设置2019年6月30感谢你的观看65 某专业课程设置2019年6月30感谢你的观看66 课程设置的AOV网络2019年6月30感谢你的观看66 课程设置的AOV网络2019年6月30感谢你的观看67 有向无环图描述n在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。nAOV网络中一定不能有有向环路。例如在下页图那样的有向环路中，V2是V3的前趋顶点，V1是V2的前趋顶点，V3又是V1的前趋顶点，环路表示顶点之间的先后关系进入了死循环。n因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环路网络在应用中才有实际意义。n一个无环的有向图称为有向无环图，它是一类较有向树更一般的特殊有向树。2019年6月30感谢你的观看67 有向无环图描述在AOV网2019年6月30感谢你的观看68 有向环路举例2019年6月30感谢你的观看68 有向环路举例2019年6月30感谢你的观看69拓扑排序n所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活动)排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得到满足。n由于AOV网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。n通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图G所有顶点都在拓扑排序序列中，则AOV网络必定不包含有有向环路。2019年6月30感谢你的观看69拓扑排序所谓“拓扑排序”就2019年6月30感谢你的观看70拓扑排序方法q(1)在网络中选择一个没有前趋(入度为0)的顶点，并把它输出；q(2)从网络中删去该顶点和从该顶点发出的所有有向边；q(3)重复执行上述两步，直到网中所有的顶点都被输出(此时，原AOV网络中的所有顶点和边就都被删除掉了)。q如果进行到某一步，无法找到无前趋的顶点，则说明此AOV网络中存在有向环路，遇到这种情况，拓扑排序就无法进行了。2019年6月30感谢你的观看70拓扑排序方法(1)在网络2019年6月30感谢你的观看71 拓扑排序过程nAOVAOV网络网络 输出输出V V3 3后后2019年6月30感谢你的观看71 拓扑排序过程AOV网络2019年6月30感谢你的观看72输出V4后输出输出V V2 2后后输出输出V V1 1后后输出输出V V5 5后后输出拓扑序列为：3 4 2 1 52019年6月30感谢你的观看72输出V4后输出V2后输出V2019年6月30感谢你的观看73关键路径法关键路径法是采用边表示活动(Activity On Edge)的网络，简称为AOE网络。AOE网络是一个带权的有向无环路图，其中，每个顶点代表一个事件(Event)，事件说明某些活动或某一项活动的完成，即阶段性的结果。离开某顶点的各条边所代表的活动，只有在该顶点对应的事件出现后才能开始。权值表示活动持续的时间。2019年6月30感谢你的观看73关键路径法关键路径法是采用2019年6月30感谢你的观看74一个AOE网络2019年6月30感谢你的观看74一个AOE网络2019年6月30感谢你的观看75AOE网络通常利用AOE网络可以研究以下两个问题：n(1)完成整个工程至少需要多少时间？n(2)哪些活动是影响工程进度的关键？2019年6月30感谢你的观看75AOE网络通常利用AOE网2019年6月30感谢你的观看76关键路径v完成工程所需的时间就是从开始点起进行到结束点止所需的时间。v路径长度是指沿路径各边的权值之和，也就是这些边所代表的活动所需时间之和。v完成整个工程所需的时间取决于从开始点到结束点的最长路径长度，此长度最大的路径叫做关键路径。v分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的效率，缩短整个工期。2019年6月30感谢你的观看76关键路径完成工程所需的时间2019年6月30感谢你的观看77求关键路径的算法描述n在描述关键路径的算法时，设活动ai由弧表示，要确定如下几个相关的量：n(1)事件Vj的最早出现时间和活动的最早开始时间：从源点V1到某顶点Vj的最长路径长度叫作事件j的最早出现时间，表示成vej。顶点Vj的最早出现时间 vej决定了从Vj指出的各条边所代表活动的最早开始时间，因为事件j不出现，它后面的各项活动就不能开始。我们以ei表示活动ai的最早开始时间。显然ei=vej。2019年6月30感谢你的观看77求关键路径的算法描述在描述2019年6月30感谢你的观看78求关键路径的算法描述(续)q(2)活动ai的最迟开始时间：在不影响整个工程按时完成的前提下，此项活动最迟的必须开始时间，表示成Li。q只要某活动ai有Li=ei的关系，我们就称ai为关键活动。关键活动只允许在一个确定的时间开始，再早，它前面的事件还没出现，尚不能开始；再晚，又会延误整个工程的按时完成。由于完成整个工程所需的时间是由关键路径上各边权值之和所决定的，显然关键路径上各条边所对应的活动都是关键活动。2019年6月30感谢你的观看78求关键路径的算法描述(续)2019年6月30感谢你的观看79求关键路径的算法描述(续)(3)事件j的最迟出现时间：即事件j在不延误整个工程的前提下允许发生的最迟时间，表示为vlj。对某条指向顶点Vk的边所代表的活动ai可得到：Li=vlk-(活动ai所需时间)也就是活动ai必须先于它后面事件的最迟出现时间开始，提前的时间为进行此活动所需的时间。下图所示为活动开始时间与事件出现时间的关系。VjaiVk2019年6月30感谢你的观看79求关键路径的算法描述(续)2019年6月30感谢你的观看80求关键路径的算法描述(续)v确定关键路径的方法就是要确定ei=Li的关键活动。v假设以wj,k表示有向边的权，即此边对应的活动所需的时间，为了求AOE网络中活动ai的最早开始时间ei和活动ai的最迟开始时间Li，先要求得顶点Vk的最早出现时间vek和最迟出现时间vlk。2019年6月30感谢你的观看80求关键路径的算法描述(续)2019年6月30感谢你的观看81nvek和vlk可以采用下面的递推公式计算：n(1)向汇点递推 由源点的ve1=0开始，利用公式：向汇点的方向递推，可逐个求出各顶点的ve。式中p表示所有指向顶点的边的集合。2019年6月30感谢你的观看81vek和vlk可以2019年6月30感谢你的观看82集合pn此式的意义为：从指向顶点Vk的各边的活动中取最晚完成的一个活动的完成时间作为Vk的最早出现时间vek。2019年6月30感谢你的观看82集合p此式的意义为：从指向2019年6月30感谢你的观看83n(2)向源点递推 由上一步的递推，最后总可求出汇点的最早出现时间ven。因汇点就是结束点，最迟出现时间与最早出现时间相同，即vln=ven。从汇点的最迟出现时间vln开始，利用下面公式：向源点的方向往回递推，可逐个求出各顶点的最迟出现时间vl。式中s表示所有由Vj点指出的边的集合，如下页图所示。2019年6月30感谢你的观看83(2)向源点递推2019年6月30感谢你的观看84 集合sn上述公式的意义为：由从Vj顶点指出的各边所代表的活动中取需最早开始的一个开始时间作为Vj的最迟出现时间。2019年6月30感谢你的观看84 集合s上述公式的意义2019年6月30感谢你的观看85n无论是向汇点递推还是向源点递推，都必须按一定的顶点顺序进行。n对所有的有向边，向汇点递推是先求出尾顶点的ve值，再求头顶点的ve值；向源点递推则相反，先求头顶点的vl值，再求尾顶点的vl值。n为此，可利用上节介绍的拓扑排序得到的顶点次序进行向汇点的递推，向源点的递推按相反的顺序进行即可，不必再重新排序。2019年6月30感谢你的观看85无论是向汇点递推还是向源点2019年6月30感谢你的观看86AOE网络中的关键活动2019年6月30感谢你的观看86AOE网络中的关键活动2019年6月30感谢你的观看87求关键路径的算法描述(续)n由表可知时间余量为零的活动都是关键活动，即为a1，a4，a7，a8，a10，a11。n这些关键活动构成两条关键路径，即关键路径(V1，V2，V5，V7，V9)和(V1，V2，V5，V8，V9)。n在安排工程时，对于关键活动和余量小的活动应重点保证，余量较大的活动可适当地放松些，对非关键活动加速进行，并不能使整个工程提前完成，只有提高关键路径上的活动的效率，才能缩短整个工程的工期。2019年6月30感谢你的观看87求关键路径的算法描述(续)2019年6月30感谢你的观看887.6 最短路径v所谓最短路径（shortest path）问题指的是：如果从图中某顶点出发（此点称为源点），经图的边到达另一顶点（称为终点）的路径不止一条，如何找到一条路径使沿此路径上各边的权值之和为最小。v设一有向网络G=（V,E），已知各边的权值，并设每边的权均大于零，以某指定V0为源点，求从V0到图的其余各点的最短路径。v以下页图为例，若指定以顶点V6为源点V0，该图比较简单，通过观察可得到从V6到其余各点的最短路径。2019年6月30感谢你的观看887.6 最短路径所谓最短路2019年6月30感谢你的观看89 最短路径例子2019年6月30感谢你的观看89 最短路径例子2019年6月30感谢你的观看90狄杰斯特拉算法o狄克斯特拉于1959年提出了一个按路径“长度”递增的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法。o假设我们以邻接矩阵cost表示所研究的有向图，costij表示有向边对应权值，如果两点之间无相应方向的边，则该元素取为无穷大。在计算机中此矩阵用一个（nn）二维数组表示（n为图的顶点数），无穷大元素则可用某很大的有限值（如32767）代替。2019年6月30感谢你的观看90狄杰斯特拉算法狄克斯特拉于2019年6月30感谢你的观看91 有向图对应的邻接矩阵 2019年6月30感谢你的观看91 有向图对应的邻接矩阵 2019年6月30感谢你的观看92狄克斯特拉算法n狄克斯特拉算法需要一个顶点集合，初始时集合内只有一个源点V0，以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程就结束了。n集合可用一维数组来表示，设此数组为S，凡在集合S以外的顶点，其相应的数组元素Si为0，否则为1。n还需要另一个一维数组dist，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为disti=cost0i，i=2n。数组dist中的数据随着算法的逐步进行要不断地修改。2019年6月30感谢你的观看92狄克斯特拉算法狄克斯特拉算2019年6月30感谢你的观看93n定义了S集合和dist数组并对其初始化后，狄克斯特拉算法在进行中，都是从S之外的顶点集合中选出一个顶点w，使distw的值最小。于是从源点到达w只通过S中的顶点，把w加入集合S中，并调整dist中记录的从源点到集合中每个顶点v的距离：从原来的distv和distw+costwv中，选择较小的值作为新的distv。n重复上述过程，直到S中包含V中其余各顶点的最短路径。2019年6月30感谢你的观看93定义了S集合和dist数组2019年6月30感谢你的观看94狄克斯特拉算法例子n以图所示的图为例来说明当指定以V6为源点V0后，用狄克斯特拉算法求最短路径的动态执行情况，其表示集合的数组S和表示距离的数组dist元素值的变化如图所示。2019年6月30感谢你的观看94狄克斯特拉算法例子以图所示2019年6月30感谢你的观看95 算法动态执行情况2019年6月30感谢你的观看95 算法动态执行情况2019年6月30感谢你的观看96 2019年6月30感谢你的观看96 2019年6月30感谢你的观看97小 结n图n图的存储结构n邻接矩阵n邻接表n图的遍历n深度优先搜索n广度优先搜索n图的应用n最小生成树n最短路径问题n利用AOV网络研究拓扑排序问题n利用AOE网络研究关键路径的方法2019年6月30感谢你的观看97小 结图2019年6月30感谢你的观看98图的应用实例n在地理信息系统中的应用n在“变电站故障定位及恢复处理智能系统”中的应用n在Internet路由器中的应用见：陈向群.数据结构.北京：人民邮电出版社，2001：174-182.2019年6月30感谢你的观看98图的应用实例在地理信息系统2019年6月30感谢你的观看99思考题1.用深度悠闲搜索和广度悠闲搜索对下图进行遍历(从顶点1出发),给出遍历序列.123645782019年6月30感谢你的观看99思考题1.用深度悠闲搜索2019年6月30感谢你的观看1002019年6月30感谢你的观看1002019年6月30感谢你的观看101思考题2.对下列所示的无向带权图，(1)写出它的邻接矩阵，并按普里姆算法求其最小生成树；(2)写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。abcdefgh493265355576542019年6月30感谢你的观看101思考题2.对下列所示的2019年6月30感谢你的观看1022019年6月30感谢你的观看102