数据结构 罗吴蔓 电子科大 PPT 考研chapt7'

第七章图•图的定义•图的存储结构•图的遍历•图的连通性问题•有向无环图•最短路径7.1图的定义和术语一.图的有关概念1.图Graph=(V,R)V={x|xdataobject}R={VR}VR={x,y|P(x,y)AND(x,yV)}V是顶点的有穷非空集合;VR是两个顶点之间的关系的集合。7.1图的定义和术语•有向图（Digragh）G=（V，{A}）其中，V为顶点的有穷非空集合{A}为顶点之间的关系集合G1=（V，{A}）V={v1,v2,v3,v4}A={v1,v2,v1,v3,v3,v4,v4,v1}其中x,y表示从x到y的一条弧（arc），A为弧集合，x为弧尾（tail），y为弧头（head)①②③④G17.1图的定义和术语•无向图（Undigraph）G=(V,{E})其中，V同有向图，{E}为顶点之间的关系集合，E为边集合G2=（V，{A}）V={v1,v2,v3,v4,v5}E={(v1,v2),(v1,v3),(v2,v3),(v3,v4),(v2,v5),(v3,v5)}其中，(x,y)表示x与y之间的一条连线，称为边（edge）①②G2③④⑤7.1图的定义和术语设n为顶点数，e为边或弧的条数对无向图有：0=e=n(n-1)/2有向图有：0=e=n(n-1)证明：每个顶点至多有n-1条边与其它的n-1个顶点相连，则n个顶点至多有n(n-1)条边。但每条边连接2个顶点，故最多为n(n-1)/27.1图的定义和术语2.完全图边达到最大值的图•无向完全图：边数为n(n-1)/2的无向图•有向完全图：弧数为n(n-1)的有向图权：与图的边或弧相关的数网：边或弧上带有权值的图7.1图的定义和术语3.顶点的度TD（V）无向图：为依附于顶点V的边数有向图：等于以顶点V为弧头的弧数（称为V的入度，记为ID（V））与以顶点V为弧尾的弧数（称为V的出度，记为OD（V））之和。即：TD（V）=ID（V）+OD（V）•无向图ne=1/2（∑TD(vi)）i=1结论：•有向图nne=∑ID(vi)=∑OD(vi)i=1i=1无向图的度数为依附于顶点v的边数；有向图的度数等于以顶点v为弧头的弧数与以顶点v为弧尾的弧数之和7.1图的定义和术语4.路径无向图：顶点v到v’的路径是一个顶点序列（v=vi0,vi1,…,vim=v’）其中，（vij-1,vij）∈E,1=j=m有向图：顶点v到v’的路径是有向的顶点序列（v=vi0,vi1,…,vim=v’）其中，vij-1,vij∈A,1=j=m几个概念：路径长度：路径上边或弧的数目回路或环：首尾顶点相同的路径，称为回路或环。即：（v=vi0,vi1,…,vim=v’=v）简单路径：路径中不含相同顶点的路径简单回路：除首尾顶点外，路径中不含相同顶点的回路7.1图的定义和术语5.连通顶点连通：若顶点v到顶点v’有路径，则称顶点v与v’是连通的连通图：包括无向连通图和有向连通图无向图：若图中任意两个顶点vi,vj都是连通的，则称该图是连通图(vivj)有向图：若图中任意两个顶点vi,vj，都存在从vi到vj和从vj到vi的路径，则称该有向图为强连通图(vivj)连通分量：无向图：无向图中极大连通子图，称为连通分量有向图：有向图中极大强连通子图，称为强连通分量7.1图的定义和术语5.连通连通分量：①②G1③④①②③④G1有两个强连通分量7.1图的定义和术语6.生成树定义：设无向图G是含有n个顶点的连通图，则图G的生成树是含有n个顶点，且只有n-1条边的连通子图三要素：n个顶点n-1条边连通极小连通子图，若再加一条边，必构成环生成树n-1条边7.1图的定义和术语二.图的基本操作“顶点在图中的位置”:对图中顶点进行人为任意排列,顶点在这个排列中的位置(或序号)。“邻接点的位置”:对某个顶点的邻接点也可进行人为任意排列,邻接点在这个排列中的序号。7.1图的定义和术语LOC_VERTEX(G,v)顶点定位函数GET_VERTEX(G,i)取顶点函数FIRST_ADJ(G,v)求第一个邻接点函数NEXT_ADJ(G,v,w)求下一个邻接点函数7.2图的存储结构图有数组表示，邻接表，邻接多重表和十字链表等表示方法一、数组表示法（邻接矩阵）设图G=（V，{E}）有n个顶点，则G的邻接矩阵定义为n阶方阵A。其中：A[i，j]=1若（vi，vj）或vi，vj∈E，i≠j0其它例如：G1的邻接矩阵┌0110┐A1＝│0000││0001│1000①②G2③④⑤┌01010┐A2＝│10101││01011│1010001100无向图的邻接矩阵为对称矩阵7.2图的存储结构特点:判定两个顶点Vi与Vj是否关联，只需判A[i，j]是否为1;顶点的度容易求得:•有向图中：TD(Vi)=OD(Vi)+ID(Vi)nn=∑A[i,j]+∑A[j,i]j=1j=1nn•无向图中：TD(Vi)=∑A[i,j]=∑A[j,i]j=1j=1即顶点Vi的度等于邻接矩阵中第i行（或第i列）的元素之和（非0元素个数之和）。即顶点Vi的出度为邻接矩阵中第i行元素之和顶点Vi的入度为邻接矩阵中第i列元素之和7.2图的存储结构网的邻接矩阵定义为：A[i，j]=Wij，若（Vi，Vj）或Vi，Vj∈E，其它V1V2V3V435214┌324┐A＝│││51如图：7.2图的存储结构二、邻接表（adjacencylist）1.无向图邻接表对图中每个顶点Vi建立一个单链表，链表中的结点表示依附于顶点Vi的边，每个链表结点为两个域：adjvexnextarc其中：邻接点域（adjvex）记载与顶点Vi邻接的顶点信息；链域（nextarc）指向下一个与顶点Vi邻接的顶点的链表结点每个链表附设一个头结点，头结点结构为：vexdatafirstarc其中：vexdata存放顶点信息（姓名、编号等）；fristarc指向链表的第一个结点。7.2图的存储结构二、邻接表（adjacencylist）如图G2的邻接表为：2534154353341221212345特点：设无向图中顶点数为n，边数为e，则它的邻接表需要n个头结点和2e个表结点。顶点Vi的度TD（Vi）=链表i中的表结点数。7.2图的存储结构二、邻接表（adjacencylist）2.有向图邻接表与无向图的邻接表结构一样。只是在第i条链表上的结点是以Vi为弧尾的各个弧头顶点234143121234特点：1.n个顶点，e条弧的有向图，需n个表头结点，e个表结点2.第i条链表上的结点数，为Vi的出度（求顶点的出度易，求入度难）如图G1的邻接表为：7.2图的存储结构二、邻接表（adjacencylist）3.有向图逆邻接表与无向图的邻接表结构一样。只是在第i条链表上的结点是以Vi为弧头的各个弧尾顶点123411431234此时，第i条链表上的结点数，为Vi的入度如图G1的逆邻接表为：7.3图的遍历从图中某个顶点出发，沿路径使图中每个顶点被访问且仅被访问一次的过程，称为遍历图。两种常用遍历图的方法深度优先搜索广度优先搜索7.3图的遍历一、深度优先搜索（depth-first-search)1.深度优先搜索法遍历图的过程为：(1)访问指定的某顶点V，将V作为当前顶点(2)将该顶点作为当前顶点，访问当前顶点的下一未被访问过的邻接点(3)重复(2)，直到当前顶点的所有邻接点都被访问过。(4)沿搜索路径回退，退到尚有邻接点未被访问过的某顶点，将该顶点作为当前顶点，重复以上步骤，直到所有顶点被访问过为止7.3图的遍历一、深度优先搜索（depth-first-search)如图G4：V1V2V3V4V5V6V7V8深到底回退深到底V1V2V4V8V5（V2V8均已访问）深到底V3V6V7回退访问7.3图的遍历一、深度优先搜索（depth-first-search)2.深度优先搜索递归过程：PROCtraver(g:Graph;VARvisited;ARRAY[vtxptr]OFboolean);FORVi:=1TOvexmumDOvisited[Vi]:=false;FORVi:=1TOvexnumDOIFNOTvisited[Vi]THENdfs(g,Vi){dfs是以Vi为出发点，遍历一个连通分量}ENDP;{traver}PROCdfs(g:Graph;V0:vtxptr);visite(V0);visited[V0]:=tuue;w:=FIRSTADJ(g,V0);{找V0的第一个邻接点}WHILEw0do[IFNOTvisited[w]THENdfs(g,w);w:=NEXTADJ(g,V0,w){找V0的w之后的下一邻接点}]ENDP:{dfs}7.3图的遍历一、深度优先搜索（depth-first-search)2.深度优先搜索递归过程：几点说明：•visited[1..n]是一个辅助数组，记载顶点是否被访问过visited[Vi]=true,已访问过false,未访问过（初值）•FIRSTADJ(g,Vo)和NEXTADJ（g,Vo,w）等函数的实现与图的基本存储结构有关7.3图的遍历一、深度优先搜索（depth-first-search)2.深度优先搜索递归过程：例如：图若采用邻接表存储则:FUNCFIRSTADJ(g,v0):integer;p:=adjlist[v0].firstarc;IFp=NILTHENRETURN(0)ELSERETURN(p↑.adjvex)ENDF;{FIRSTADJ}FUNCNEXTADJ(g,vo,w);p:=adjlist[vo].firstarc;WHILEpNILANDp↑.adjvexwDOp:=p↑.nextarc;IFp=NILCORp↑.nextarc=NILTHENRETURN(0)ELSERETURN(p↑.nextarc↑.adjvex)ENDP;{NEXTADJ}思考：traver调用dfs的次数由什么决定？7.3图的遍历二、广度优先搜索（breadth-first-search)(1)首先访问指定顶点v0，将v0作为当前顶点(2)访问当前顶点的所有未访问过的邻接点，并依次将访问的这些邻接点作为当前顶点(3)重复(2)，直到所有顶点被访问为止对图4广度优先搜索，访问顶点序列为：V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V87.3图的遍历二、广度优先搜索（breadth-first-search)广度优先搜索算法：PROCbfs(g,vo);visited(vo);visited[vo]:=true;INIQUEUE(Q);ENQUEUE(Q,vo);WHILENOTEMPTY(Q)DO[v:=DLQUEUE(Q);w:=FIRSTADJ(g,v);WHILEw0DO[IFNOTvisited[w]THEN[visite(w);visited[w]:=true;ENQUEWE(Q,w)];w:=NEXTADJ(g,v,w)]]ENDP;{bfs}7.4最小生成树一、最小生成树概念1.设无向连通图G=（V，{E}），其子图G’=（V，{T}）满足：①V(G’)=V(G)n个顶点②G’是连通的③G’中无回路则G’是G的生成树7.4最小生成树具有n个顶点的无向连通图G•其任一生成树G’恰好含n-1条边•生成树不一定唯一，如4个顶点选择3条边有如下5种形状(5×4=20种):其中16种为生成树,（保证了连通）生成树代价对图中每条边赋于一个权值（代价），则构成一个网，网的生成树G’=(V,{T})的代价是T中各边的权值之和，最小生成树就是网上所有可能的生成树中，代价最小的一类生成树。最小生成树也不一定唯一。7.4最小生成树最小生成树的实用例子很多例1：N台计算机之间建立通讯网顶点表示computer边表示通讯线权值表示通讯线的代价（通讯线长度，computer间距离等）要求：①n台计算机中的任何两台能通过网进行通讯；②使总的代价最小。--