数据结构讲义第7章

第七章图,在线性结构中，每个数据元素至多有一个直接前驱和一个直接后继。在树型结构中，每个数据元素至多有一个直接前驱，但可以有多个直接后继。在图结构中，每个结点可以和其它任何结点相关联。,7.1图的定义和术语,一、图的定义1、图由两个集合()和()所组成，记作（，）。其中，V是图中顶点的非空有限集合。E是图中顶点偶对（称为边）的有穷集合。若图G的每条边都是有方向的，则称G为有向图。有向图的边也称为弧，用尖括号括起的一对顶点表示:v,w若v,wE表示从v到w是一条弧，且称v为弧尾，称w为弧头,即有向图为每条边的顶点的有序对，在图示时都用箭头指明方向。,V=A，B，C，DE=,图的定义和术语,若v,wE必有w,vE即E是对称的，可用无序对（v,w）代替这两对有序对，表示v和w之间的一条边，此时的图称为无向图。无向图：每条边都是顶点的无序对。边用圆括号括起来的两个相关顶点来表示。,V=A，B，C，DE=（A，B）,（A，D），（B，C），（B，D），（C，D）,图的定义和术语,无向完全图：个顶点的无向图，每个顶点与其它-顶点之间都有边。边的总数为n*(n-1)/2。有向完全图：个顶点的有向图，每个顶点与其它-顶点之间都有边。边的总数为n*(n-1)（不考虑从自身引到自身的边）一般无向图:顶点数为n，边数为e，则0en(n-1)/2。一般有向图，顶点数为n，弧数为e，则0en(n-1)。当一个图接近完全图时，则称它为稠密图。当一个图中含有较少的边或弧时，则称它为稀疏图。,图的定义和术语,网：若G中的每一条边都有权值，称该图为网。权值可以是距离，时间，价格等。,子图：设有两个图和，且满足条件：（）（）（）（）则称是的子图,图的定义和术语,邻接：若（i,j）是图的一条边，则称i和j是邻接的。并称边（i,j）依附于顶点i和j。或者说边（i，j）和顶点i和j相关联，i与j互为邻接点。对有向图G,若是图G的一条弧，则称顶点Vi邻接到顶点Vj,顶点Vj邻接自顶点Vi。弧和顶点Vi,Vj相关联。无向图顶点v的度：依附于该顶点V的边数i，记为TD(V)。有向图顶点的入度:终止于该顶点V的弧的数目,记为ID(V)。有向图顶点的出度：始于该顶点v的弧的数目,记为OD(V)。有向图顶点的度：顶点的入度和出度之和。图的顶点的度与边的关系：(无论是有向图还是无向图),图的路径,路径：在图中，从顶点p到q的一条路径是顶点的序列(Vp,Vi1,Vi2,.,Vin,Vq)，且(Vp,Vi1),(Vi1,Vi2),.,(Vin,Vq)是E(G)中的边。若G是有向图：其路径也是有向的，路径由弧组成。路径长度：路径上边的数目。简单路径：一条路径上所有顶点除起点和终点外，彼此都是不同的。回路：起点和终点相同的路径。简单回路：简单路径的回路。,图的连通性,连通图：在无向图中，若从i到j有路径，则称i和j是连通的。若中任意两个顶点都是连通的，则称图是连通图。连通分量：无向图中的极大连通子图（包括子图中的所有顶点和所有边）。,图的连通性,强连通图：在有向图中，若每一对顶点i和j之间都有从i到j和从j到i的路径，则称图是强连通图。强连通分量：有向图中的极大强连通子图。,图的生成树,有根图：在一个有向图中，若从顶点V有路径可以到达图中其它所有顶点，则称此有向图为有根图，顶点V称作图的根。连通图的生成树：是一个极小连通子图（只包括连通图中最少的边，两个顶点之间只有唯一的一条路径），它含有图中全部顶点，但只有足以构成一棵树的n-1条边。在生成树中，只要在加一条边就必然构成环。有向树：在有向图中，如果有一个顶点的入度为0，其余顶点的入度为1，则是一棵有向树。有向图的生成森林：有向图的生成树的集合。由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵互不相交的有向树的弧。“顶点的位置”只是一个相对的概念，任何一个顶点都可被看成是第一个顶点。任何一个顶点的邻接点之间也不存在次序关系。所谓“顶点在图中的位置”指该顶点在使用该图的人根据自身的目的随意排列的位置（或序号）,图的基本操作,CreateGraph(/有向图、有向网、无向图、无向网typedefstruct/图结构VextypevexsMAX_VERTEX_NUM;/顶点数组ArctypearcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/边矩阵，/0,1或权值wijintvexnum,arcnum;/顶点数,边数Graphkindkind;/图种类Mgraph;,建立无向网的邻接矩阵,StatuscreateAN(MGraph,图的邻接矩阵表示法,邻接矩阵表示的特点：1、无向图的邻接矩阵是对称的。2、有向图的邻接矩阵不一定是对称的。优点：1、容易判定图中任意两个顶点之间是否有边相连。2、容易计算各顶点的度数。无向图：第行元素之和就是第个顶点的度数。有向图：第行元素之和是第个顶点的出度。第列元素之和是第个顶点的入度。若要求的边数，必须按行、按列对每个元素进行检测，所花时间较多。缺点：要使用用2个存储单元。存储各顶点相关的其它信息更不方便。,图的邻接矩阵表示法,若顶点不是用连续的编号表示，要求某个顶点的邻接点，先通过顶点名找到它在图中的位置（一维数组中的序号），再通过该序号找到相应行，其值为正常值的分量所对应的列号对应的顶点便为该顶点的邻接点。部分操作的实现：1、定位操作：对一维数组操作，依次比较。2、取顶点：VEXSi3、FIRSTADJ(G,v):v对应的行的第一个非零或非元素的列对应的顶点。4、NEXTADJ(G,v,w):v行第w列后面的第一个非零或非元素的列对应的顶点。,图的邻接表表示法,对图中每个顶点Vi，把所有邻接于Vi的顶点Vj（对有向图以顶点Vi为尾的弧）链接成一个单链表，这个单链表称为Vi的邻接表。,将所有头结点顺序存放在一个向量中,便于随机访问任一顶点的邻接表，由此构成图的邻接表表示。向量部分：用于存放个表头结点。向量的下标指示了顶点的序号。顶点和结点的区别：结点是表示边或弧的概念，它表示从表头结点所表示的顶点与表结点所指示的顶点之间有一条弧。,图的邻接表表示法,01234,图的邻接表表示法,01234,图的邻接表表示法,#defineMAX_VERTEX_NUM20/最大顶点数typedefstructArcnode/边结点类型intvjpos;/vj的位置structArcnode*nextarc;Arcnode;typedefstructVnode/顶点结点类型vextypedata;Arcnode*firsttarc;Vnode,AdjlistMax_V_num;typedefstructAdjlistvexs;intvexnum,arcnum;Graphkindkind;ALGraph,图的邻接表表示法,无向图：个顶点,条边,个表头结点,2e表结点。每个链表表结点的个数就是对应顶点的度,称无向图的邻接表为边表。有向图：表结点数等于边数。每个链表表结点的个数就是对应顶点的出度。称有向图的邻接表为出边表。若要求顶点Vi的入度，必须对邻接链表进行扫描统计。或再建立一逆邻接链表-以表头结点i为终点的单链表，也称入边表。建表的算法时间复杂度为O(n+e)：输入n个顶点e条边。空间复杂度s(n,e)=O(n+e)图的邻接矩阵表示是唯一的，但邻接表表示不唯一，与边表结点的链接次序和输入边的次序有关。,图的邻接表表示法,两种存储表示法的比较：1、空间复杂度：若图中边数远小于n2,（稀疏图），用邻接表比邻接矩阵节省存储空间，而对于稠密图，宜采用邻接矩阵表示法。2、求顶点的度对无向图，两种存储结构都容易做到。对有向图，用邻接矩阵比邻接表更方便。对应行列非0元素个数为顶点的度。用邻接表表示，求出度容易，求入度难；对逆邻接表，求入度容易，求出度难。3、判断两顶点之间是否有边：邻接矩阵容易；邻接表难，要扫描整个边表，时间复杂度为O(n)4、求边的数目的时间复杂度：邻接矩阵为O(n2)，邻接表为O(n+e)。,有向图的十字链表表示法,十字链表：用来表示有向图。在有向图中,每一条边用一个结点表示，每个顶点也用一个结点表示.,firstin:指向以该顶点为头的第一个边结点firstout:指向以该顶点为尾的第一个边结点hlink:指向头相同的下一条边tlink:指向尾相同的下一条边tvpos，hvpos:有向边两个顶点的位置,有向图的十字链表表示法,#defineMAX_VERTEX_NUM20/最大顶点数typedefstructArcnode/边结点类型inttvpos,hvpos;structArcnode*hlink,*tlink;Arcnode;typedefstructVnode/顶点结点类型vextypedata;Arcnode*firstin,*firstout;Vnode;typedefstructVnodevexsMAX_VERTEX_NUM;intvexnum,arcnum;Graphkindkind;OLGraph,有向图的十字链表表示法,例如:,有向图的十字链表表示法,操作：找以Vi为尾和找以Vi为头的弧容易，因而容易求顶点的入度和出度。算法：输入顶点信息的时间复杂度为O(n);输入弧信息，e条边，要定位顶点，时间复杂度为O(e*n),无向图的邻接多重表表示法,邻接多重表：表示无向图,每一条边用一个结点表示,每个顶点也用一个结点表示.类似十字链表。,firstedge:记录该顶点的第一个边结点mark:标记是否被搜索过vipos,vjpos:表示该边的两个顶点位置vilink:指向vi的下一条边vjlink:指向vj的下一条边,无向图的邻接多重表表示法,#defineMax_V_num20/最大顶点数typedefstructEbox/边结点类型intmark;intvipos,vjpos;structEBox*vilink,vjlink;Arcnode;typedefstructVnode/顶点结点类型vextypedata;EBox*firstedge;Vnode;typedefstructVnodevexsMax_V_num;intvexnum,arcnum;AMLGraph,无向图的邻接多重表表示法,例如:,无向图的邻接多重表表示法,邻接表和邻接多重表的差别：1、在邻接表中，同一条边用两个结点表示，在邻接多重表中只有一个结点。2、在邻接多重表中，除多一个标志域外，两个表所需存储空间相同。各种基本操作的实现与邻接表相同。图的存储结构有三种：邻接矩阵邻接表十字链表/邻接多重表,7.3图的遍历,一、定义图的遍历：从图的某一顶点出发访问图的所有顶点，且每个顶点仅被访问一次，这个过程称为图的遍历。图的遍历是求解图的连通性、拓扑排序和求关键路径等算法的基础。遍历图要比遍历树复杂得多，因为图中某一顶点都可能与其余顶点相邻接。所以在访问了某个顶点之后，可能沿着某条路径搜索之后，又回到该顶点。因此在遍历图时，必须对已访问过的顶点进行标记，以免重复地进行访问。标记方法：1、设置一辅助数组visited0.n-1,其初值为假或0。一旦访问了顶点Vi，就置visitedI为真或所访问的次序号。2、在表头结点增加标志域。,深度优先搜索,1、深度（纵向）优先搜索的基本思想：类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索遍历可定义如下：(1)首先访问给定顶点i，并将其访问标记置为访问过，即visitedi=1；(2)然后搜索与顶点i有边相连的下一个顶点j，若j未被访问过，则访问它，并将j的访问标记置为访问过，visitedj=1，然后从j开始重复此过程。（对j进行深度优先遍历）。(3)重复上述过程，直到图中所有顶点都被访问到。,深度优先搜索,例：,1,1,1,1,1,1,1,1,01234567,深度优先搜索,遍历走过的路径为：,访问的顶点序列为：v1、v2、v4、v8、v5、v3、v6、v7逻辑上还可有次序：v1、v2、v4、v8、v5、v3、v7、v6v1、v2、v5、v8、v4、v3、v6、v7v1、v2、v5、v8、v4、v3、v7、v6v1、v3、v6、v7、v2、v4、v8、v5v1、v3、v6、v7、v2、v5、v8、v4v1、v3、v7、v6、v2、v4、v8、v5v1、v3、v7、v6、v2、v5、v8、v4,当数据的存储结构选定后，遍历结构只有唯一的序列。,深度优先搜索,intvisitedMAX_VERTEX_NUN;Stutas(*VisitFunc)(intv);voidDFStraverse(GraphG,stutas(*visit)(intv)for(v=0;vG.vexnum;+v)visitedv=FALSE;for(v=0;vG.vexnum;+v)/保证非连通图的遍历if(!visitedv)DFS(G,v);voidDFS(GraphG,intv)/连通子图的遍历visit(v);visitedv=TRUE;for(w=First_Adj(G,V);w;w=Next_Adj(G,v,w)if(!visitedw)DFS(G,w);算法时间复杂度分析：与图的存储结构有关。邻接矩阵：时间复杂度为O(n2)。邻接表：查找邻接点的时间复杂度为O(e),所以整个算法的时间复杂度为O(n+e)。,广度优先搜索,广度（横向）优先搜索的基本思想：广度优先搜索遍历类似于树的按层次遍历。设无向图（，），从()中的任一顶点0出发，按广度优先搜索图G的步骤是：、访问0后，依次访问与0相邻接的各个未曾访问的顶点1，2，.，t；、再按1，2，.，t的顺序，访问其中每一个顶点的所有未访问过的邻接顶点。、再按刚才的访问次序，依次访问它们的所有未访问的邻接顶点，直到所有已被访问的邻接点都被访问过。4、若此时图中尚有顶点未被访问，则另选一个未被访问的顶点为起点，重复上述步骤，直到图中所有顶点都被访问到为止。,广度优先搜索,例：,1,1,1,1,1,1,1,1,01234567,广度优先搜索,遍历走过的路径为：,访问的顶点序列为：v1、v2、v3、v4、v5、v6、v7、v8逻辑上还可有次序：v1、v2、v3、v4、v5、v7、v6、v8v1、v2、v3、v5、v4、v6、v7、v8v1、v2、v3、v5、v4、v7、v6、v8v1、v3、v2、v6、v7、v4、v5、v8v1、v3、v2、v6、v7、v5、v4、v8v1、v3、v2、v7、v6、v4、v5、v8v1、v3、v2、v7、v6、v5、v4、v8算法时间复杂度为深度优先相同。空间复杂度O(n),广度优先搜索,要实现广度优先搜索，必须设置一个队列，每访问一个顶点，就把它的未访问的邻接点送入队列中。重复上述步骤，直到队列为空。voidBFStraverse(GraphG)for(v=0;vG.vexnum;+v)visitedv=FALSE;iniqueue(Q);for(v=0;vG.vexnum;+v)/保证非连通图的遍历if(!visitedv)Enqueue(Q,v);while(!Queueempty(Q)Dequeue(Q,u);visit(u);visitedu=TRUE;for(w=First_Adj(G,u);w;w=Next_Adj(G,u,w)if(!visitedw)Enqueue(Q,w);,7.4图的连通性,一、无向图的连通分量和生成树对无向图进行遍历时：1、对连通图：仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到所有顶点。2、对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起点出发进行搜索过程中得到的顶点序列为其各个连通分量中的顶点集。3、设E(G)为连通图G中所有边的集合，则从图中任一点出发遍历图时，必定将E(G)分成两个集合T(G)和B(G)，其中：B(G)为剩余边的集合；T(G)为遍历图过程中所经历的边的集合，它和G中所有顶点一起构成连通图G的极小连通子图，它是连通图的一棵生成树。,图的连通性,连通图的生成树：是连通图的极小连通子图，它包含图中所有顶点，但只有构成n个顶点的一棵树的n-1条边。由深度优先搜索得到的生成树为深度优先搜索树由广度优先搜索得到的生成树为广度优先搜索树。,图的连通性,对有向图，若G是强连通图，则从其中任一点出发都可以遍历G中所有顶点，从而得到以v为根的生成树；若G是有根的有向图，设根为v，则从v出发可以遍历G中所有顶点，生成G的以v为根的生成图。广度优先搜索生成树的高度不会超过深度优先搜索生成树的高度。由于BFS搜索过程是由近及远依次访问从源点s可达距离为1，2，的顶点，所以，BFS生成树中从源点（根）s到树中任一顶点v的路径是相应图中从s到v的最短路径（边的条数最少）。对于非连通图，每个连通分量中的顶点和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。,最小生成树,边赋以权值的图称为网或带权图。带权图的生成树也是带权的。生成树T各边的权值总和称为该树的权。最小生成树（MST）：权值最小的生成树。生成树和最小生成树的应用：要连通n个城市需要n1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。构造网的最小生成树必须解决下面两个问题：1、尽可能选取权值小的边，但不能构成回路。2、选取n1条恰当的边以连通n个顶点。MST性质：假设G(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中uU，vVU，则必存在一棵包含边(u,v)的最小生成树。,普里姆（Prim）算法,基本思想：假设G(V，E)是连通的，TE是G上最小生成树中边的集合。算法从Uu0（u0V）、TE开始。重复执行下列操作：在所有uU，vVU的边(u，v)E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到VU为止。此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。Prim算法的核心:始终保持TE中的边集构成一棵最小生成树。,普里姆（Prim）算法,例：,普里姆（Prim）算法,算法实现：设置一辅助数组closedge,记录从U到VU具有最小代价的边。对于每个顶点vVU,closedgev,它包含两个域：closedgev.vex:该边依附的在U中的顶点。closedgev.lowcost:mincost(u,v)|uU,初态：U=v1,012345,普里姆（Prim）算法,voidminispantree_PRIM(MgraphG；VertexTypeu)k=locateVex(G,ufor(j=0;jG.vexnum;j+)if(j!=k)closedgej=u,G.arcskj.adj;Closedgek.lowcost:=0;for(i=0;iG.vexnum;i+)k=minimum(closedge);printf(closedgek.adjvex,G.vexsk);closedgek.lowcost=0;for(j=0;j直到i=0求出Ve(i)，VL(i)后，就可以简单计算出e(i,j),L(i,j)。凡是e(i,j)=L(i,j)的边，即为关键路径上的边。,关键路径,计算示例:,关键路径为:v1v2v5v7v9v1v2v5v8v9最短工期为:17个时间单位,关键路径,算法实现：计算各顶点的ve值是在拓扑排序的过程中进行的，需对拓扑排序的算法作如下修改：1、在拓扑排序之前设初值：ve（i）=0(0）vek，则：ve（k）ve（j）+dut（）3、为了按逆拓扑排序的顺序计算各顶点的vL值，需记下在拓扑排序过程中求得的拓扑有序序列。可增设一个栈来记录拓扑有序序列-把输出顶点压入一栈中。拓扑排序执行完，从栈顶到栈底即为逆拓扑排序。,关键路径,StatusTopologicalSort(ALGraphG,stack,关键路径,StatusCriticalPath(ALGraphG)InitStack(T);if(!TopologicalSort(G,T)returnERROR;vl0.G.vexnum-1=veG.vexnun-1;while(!StackEmpty(T)for(Pop(S,j),p=G.verticalsj.firstarc;p;p=p-nextarc)k=p-adjvex;dut=p-info;if(vlk-dutnextarc)k=p-adjvex;dut=p-info;ee=vej;el=vlk-dut;tag=(ee=el)?*:;printf(j,k,dut,ee,el,tag);,关键路径,算法分析：拓扑排序和逆拓扑排序算法均为O(n+e)求e(i),l(i)的时间复杂度军委O(n)总的时间复杂度为O(n+e).结论：1、影响关键活动的因素是多方面的，任何一项活动持续时间的改变都会影响到关键活动的改变。2、若网中有几条关键路径，单是提高一条关键路径上的关键活动的速度，还不能导致整个工期的缩短，而必须提高同时在几条关键路径上的关键活动的速度。,7.6最短路径,假设：顶点表示城市，用边表示城市间的公路，则由这些顶点和边组成的图可以表示沟通各城市的公路网。若把两个城市之间的距离或该段公路的养路费等作为权值，赋于图中的边，就构成了一个带权的图。汽车司机关心的问题是：1、从甲地到乙地是否有公路？2、若从甲地到乙地有若干条公路，哪一条公路最短或花费最小。最短路径：指带权图中，两顶点间所经过的边上的权值之和为最小的路径。(不是指路径上经过的边的数目最小)。考虑到交通图的有向性，只考虑带权有向图。源点：路径上的第一个顶点。终点：路径上最后一个顶点。,单源点最短路径,单源点最短路径是指：给定一个出发点(单源点)和一个有向网G=(V，E),求出源点到其它各顶点之间的最短路径。迪杰斯特拉（Dijkstra）算法:按路径长度递增的次序产生最短路径。方法：设置辅助向量dist:disti:表示已找到的从v0到vi的最短路径。初值:若从v0到vi有弧,则disti为弧上权值,否则为。第一条最短路径是：从初态的dist中选一条值最小的distj，对应的顶点vj,显然有：distjMindisti|viV此路径为（v0，vj）。从v0到其它顶点的最短路径有可能通过vj得到改变。下一条次短路径是终点vk,则这条路径或者是（v，vk），或者是（v，vj，vk）。它的长度或者是从v到vk的权值，或者是distj与从vj到vk的权值之和,因此要修改dist的值。,单源点最短路径,设源点v0s=v0初值dist=,10,30,100第一条最短路径是:(v0,v1),长度为10s=v0,v1修改（v0,v1,v2）=60，即：dist=，10，60，30，10