数据结构-第7章图hsh2014给学生版

7.17.1★图的结构定义Graph=(V,R)VR＝{<v,w>|v,w∈VP(v,w<v,w>表示从顶点v到顶点w的一条弧P(v,w)定义了弧<v,w>的意义或信息,表示v和w之间有特定的关联属性P。}3★★图的抽象数据类型的定义ADTGraphR={VRVR＝{<vw>|v,w∈VP(v,w),<v,w>表示从顶点vw一条弧P(v,w)v,w表示v和w之间有特定的结构的建立LocateVex(G,对顶点操,则4对邻接点和删除5InsertAcr(&G,InsertAcr(&G,v,和删除 }ADT6★图的基本术语★图的基本术语若<v，w>VR，则<v，w>表示从顶点v到顶点w的一条弧(arc),并称v为弧尾(tail)或起始点,称w为弧头(head)或终端点。由于此时图中的“弧”是有方向的因此由ABECDG1=(V1,V1={A,B,C,D,E}<B,C>,<C,D>,<D,A>,<E,C>7无无向若<v,w>∈VR,且有<w,v>∈VR,即VR是对称关系,则以无序对(v,w)代替这两个有序对v和w之间的一条边(edge顶点集合和边集合构成的图称作无向BCADFEV2={A,B,C,D,E,VR2={(A,B),(A,(B,E),(C,D),(D,(B,F),(C,F)8设n表示图中顶点数目，用e表示图的边或弧的数目，且对于无向图，其边数e的取值范围是0~n(n-1)/2。称有n(n-1)/2条边(即图中每个顶点和其余n-1个顶点都有边对于有向图，其弧数e的取值范围是0~n(n-1)。称n(n-1)条弧(即图中每个顶点和其余n-1个顶点都有弧相连的有向图为有向完全图对于有很少条边或弧(如e<nlogn)的图称为稀疏图之称为稠密图 14234 9权权与125A9663B7E6354C2F’’子子假设有两个图G=(V{E})和图G’=(V’E’}),如果V且EE则称图G’为G的子图12111123433434有向图G1及其子图1211 22333 545无向图G2及其子图邻邻接对于无向图G=(V,{E}),如果边(v,v’)∈E,则称顶点v和互为邻接点,即vv’相邻接。边(v,v’)依附于顶点v和v’,或者说边(v,v’)与顶点v和v’相关联。对于有向图G=(V,{A}),如果弧v,v>∈A,则称顶点邻接到顶点v’,顶点v’邻接自顶点v,或者说弧<v,v’>与顶 对于无向图，顶点v的度是指与顶点v相关联的边的记作TD(v)BCADTD(B)=TD(A)=FE对于有向图，顶点v的度有出度和入度两部分，其中以以顶点v为弧尾的弧的数目称为该顶点的出度，记作OD(v),顶点v的度为TD(v)=ID(v)+OD(v)。AID(B)= CFOD(B)=TD(B)=一般地，若图G中有n个顶点，e条边或弧，则图中的度与边的关系e TD(vi1n2无向图G=(VE})中从顶点v到v’的路径是一个顶点序列(v=vi0,vi1,vi2,…,vim=v’),其中(vij-1,vij)∈E,1≤j≤m。如果图G是有向图,则路径也是有向的,顶点序列路径的长度是指路径上经过的弧或边的数目。在一个路连连通图、连通分量、强连通图、强连通在无向图G=(VE})中，若从顶点vi到顶点vj有路径相通vj∈V，vi和vj都是连通的，则称该无向图G为连通图。1G2345①任何连通图的连通分量只有一个ABABCC GHFF DEIKIKJJLMLM(a)无向图(b)无向图G3的3个43432121有向图G=(V,{A})中,若对于每一对顶点vi,vj∈V且vi≠vj，注意①强连通图只有一个强连通分量 即是其自身②非强连通的有向图有多个强连通分量通图的生成树是一个极小连通子图,它含有图中全部n个顶点,但是只有足以构成一棵树的n-1条边,如下 一棵有n个顶点的生成树有且仅有n-1 入度均为1,则是一棵有向树。 图的结 链表表基本思想 数据元用一个一维数 顶点的信息 数据关—二维数组(邻接矩阵 顶点之间的关系邻接矩阵:表示顶点之间相互关系(边或弧的信息)的矩阵。以二维数组表示有n个顶点的图时，需要存放n个顶点信息和n2个弧或边的信息。对于无向图,它的邻接矩阵是对称矩阵,可只其邻接 #defineMAX_NAME5//顶点名称字符串的最大长度+1typedefint typedefchartypedefcharVertexType[MAX_NAME];//对应的一维字符数组用 顶点名#defineINFINITYINT_MAX #defineMAX_VERTEX_NUM20 G1.arcs[i][j].adji,typedefstructArcCell VRType //对无权图,用1或0表示相邻否;对带权图,则为权值类型InfoType }ArcCell, //弧(二维数组元素)的类型ArcCell定义,二维数组类型AdjMatrix定义typedefstruct{ 可使用scanf(“%s”,G.vexs[i]);输入各个顶点名字(字符串)VertexTypevexs[MAX_VERTEX_NUM];//顶点向量(顶点信息,一维数组) GraphKind }课堂练习:画出Mgraph型变量的内存分配示意#define TC umandminimumvaluesforints.#defineGCC是使用ANSIC标准头文件limits.h中的预定义值。该文件包要判断某种特定类型可以容纳的最大值或最小值，一种简便的方邻接矩阵的元素:A[i][j]=0<i,j>或(i,j01<ij>或(ijG1.arcsV1V2V3V2G2.arcsV3V410001010110000101100V4V101010100011V500无向图的邻接矩阵一定是对称有向图有向图:顶点Vi的出度是邻接矩阵A中第i行元 和; 无向图:顶点Vi的度TD(Vi)是邻接矩阵A中第i行(或第i列) 网(带权的图)的邻接矩阵的元素A[i][j]={Wi,∞(i,j)或<i,5347189V1V2 16V35V495V6V56有向网及其★★算法讲解补u是顶点 字)-是字符intLocateVex(MGraphG,VertexType//操作结果:若G中存在顶点u返回该顶点在图中的位置;返回-intfor(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)returni;return-1;}//调用形式LocateVex(Gv):找到v在图的一维数组vexs中的序号iStatusStatusCreateGraph(MGraph&G //采用数组（邻接矩阵）表示法，构造图 {caseDG: returnCreateDG(G); case return //构造有向网caseUDN:return caseUDG:return //构造无向图} return}基本思想 StatusCreateUNDMGraph&G构造无向网 for(i=0i<G.vexnum; for(i=0;i<G.vexnum;for(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};//{adj,{scanf(&v1,&v2,i=LocateVex(G,v1j=LocateVex(G,v2确定v1和v2在G)][);//}return 算法算法采用采用数组(邻接矩阵表示图的便于找顶点的邻接点等缺点n个顶点需要n2个单 边(弧 空间效率为O(n2)对稀疏图而言尤其空间V1 V1 V2无向图的表7.2.2的基本思想：是图的一种链向图的顶点列好,使之构成一个一维数组(顺序表)，之后对图中每个顶点建立结构,它克服了邻接矩阵的弊病。先把个单链表，第i个单链表中的结点表示依附于顶点Vi(单链表的头结点)的边。每单链表的头结点又构成一个表头结点表BC01D341034455AFE无向图的邻接表01123在无向图的邻接表中，顶点vi的度恰好就是第i个单链表上结点的个数ABCDEF03114202431320421V1V1 V2021123有向图的邻接表03建立一个单链表，第i个单链表中的结点表示以顶点Vi为弧尾的弧。每个单链表以顶点A为弧尾的0AABECD有向图1234E21032DCB41在有向图的邻接表中不易找到指向该顶点的弧解决的方法是逆邻接表法也就是，在逆邻接表中，对每个顶 的是指向该顶点的弧以为弧头的 A 012334 32有向图的逆邻接4003102032有向图G1的逆邻接表链表链表中的结点结构(相关弧的结点结构 typedef{该弧的弧头的顶点的ode*nextarc//指向下一条弧的 //该弧相关信息的 typedefchar顶点的结点结构

01234typedefchartypedefstruct{VertexTypedata; ode* //指向第一条依附该顶点的弧}VNode, 基于基于typedef{AdjListvertices; }结构的图的类型定义um;//图的当前顶点数和01234DE在在有向图链表每一条弧用一个结点表示每一个顶点也用一个结点表示7.2.3是有向图的另一种链 结构的和得。 同弧尾的弧结 指向下一个同弧头的弧结 指向下一个邻接表以顶点1为弧尾0 ∧1∧ 3 0 1 2图7.11有向图链02链表链表中的弧的结点结typedeftypedefstruct//弧的结构{inttailvex,headvex;//该弧的弧尾和弧头的顶点位置structArcBox*hlink,*tlink;//含义见上面框内InfoType*info; }ArcBox //弧结点的类型定链表链表中的顶点的结点typedefstruct{VertexType//顶点的结构ArcBox in, //分别指向该顶点第一条入弧和出 //顶点结点的指向该顶点的出指向该顶点的入typedeftypedefstruct um;//有向图的当前顶点数和}StatusStatusCreateDG(OLGraph&G{//采 链 表示，构造有向图G(G.kind=DG) 算法 scanf( um,&IncInfo//IncInfo为0则各弧不含for(i=0;i<G.vexnum;{//构造} in=NULL; out=NULL;//初始化for(k=0;k<G.vexnum;++k)//输入各弧{scanf(&v1,//输入一条边依附的顶点及链 p=(ArcBox*)malloc(sizeof(ArcBox) *p={i,j, in out,NULL}//对弧结点//{tailvex,headvex,hlink,tlink, out=p;//完成在入弧和出弧,;,}}7.2.47.2.4的是无向图的另一种链结构在无向图的邻接多重表每一条边用一个结点表示每一个顶点也用一个结点表示邻邻接多重表中的边的结点其中:mark为标志域,可用以标记该条边是否被搜索过;ilink用于指向下一条依附于顶点ivex的边；typedefstruct{ ivex,structEBox*ilink,//该边依附的两个顶点的位 邻邻接多重表中的顶点的结点结构其中 data与该顶点相关的信edge用于指向第一条依附于该顶点的边typedefstruct{VertexType //用 顶点的名EBox//用于指向第一条依附该顶点typedeftypedef{VexBox 01234图7.12无向图的邻接多重V32^3^01210jlink4141^2^4^01234^4^2^143212^3^0107.37.3并且使图中的每个顶点仅被一次的过程。图中还可能有回路存在，因此在了某个顶点后，可能沿着某条为了保证图中的各顶点在遍历过程中且仅一次，必须标记每个已过的顶点，为此，需要为每个顶点设立一个标志。为图设置一 标志数组visitedn，用于标示图中每个顶点是否被过，它的初始值为0(“假”,”false”)，表示顶点均未被；一旦某个顶点vi被过，则置标志数组中的visited[i]为1(“真”,“true”)，表示该顶点已。 通常有两条遍历图的路径：深度优先搜索和搜索。它们对无向图和有向图都适用7.3.17.3.1图的深度优先搜索深度优先搜索遍历图的过程是指按照深度方向搜索它类似于树的先根遍历，是树的先根遍历的推广采用递归的形式说明深度优先搜索遍历图的基本思想(1)从图的某一个顶点V0出发(2)然后依次从v0的的邻接点出发深度此顶点v0被若此时图中还有顶点未，则另选图中一个未直至图中所有顶点的顶点作为起始点，重复上述深度优先搜索过程到为止例例起深度优先搜索v1→v2→v4→v8→v5→v3→v6→v7例例A GB EHC FI其中：实箭头代图的深度优先搜索虚箭头代表回溯方向方向箭头旁边的数字代表搜索顺A为起始顶点例例ABCFDGIEHKJLM一般图的深度优先搜 算法 typedefint,Boolean voidDFSTraverse(GraphG,Status(*Visit)(intv)次。一旦Visit()失败,则操作失败int 使for(v=0;v<G.vexnum;++v) 标志数组初始化(开始都未被 for(v=0;v<G.vexnum;if(!visited[v])DFS(G, //对尚 的顶点调用 算法连通图的深度优先搜索遍voidDFS(GraphG,int 算法 {//从第v个顶点出发递归地深度优先遍历图Gint //设 VisitFuncG.vexs[v } AdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)）if(!visited[w])DFS(G,w);//对v的尚未 初始条件：图G存在,v是G中某个顶点,w是v7.3.27.3.2广度优先搜索的基本思想是(1)从图中某个顶点v0出发，(2)依此顶点v0的重复(3)分别从这些邻接点出发，依v0的所有各个未曾，则vi的所有未时应保证：如果vi和vk为当前端结它们的各的邻接点应的邻接点之。直到所有端结点均没有的邻接被若此时图中尚有顶点未，则另选图中一个未例例A GBEHCFI其中：箭头方向例2例2：起BFS起例BFSv3→v2→v1→→v4→v5→v9→v8→一般一般图的广度优先搜索 算法 voidBFSTraverse(MGraphG,:从 intv,u, VertexTypew1,u1;LinkQueue ①fst;{ Visit(G.vexs[v]);EnQueue(&Q,v{DeQueue(&Q, }{visited[w]=TRUE;Visit(G.vexs[w]);EnQueue(&Q,w);}}7.47.4图的连通性问题7.4.3最小生成 (连通网的)最小生成1、普里姆算法构造最小生成2 算法构造最小生成假设要n之间建立通讯联络网，则n需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网构造网的一棵最小生成树，e条带权的边中选取n-条边（不构成回路），使“权值之和”为最小1、1、普里姆算法构造基本思想 取有n个顶点的图中的v作为生成树的根，之后往生成树上添加新的顶点w。在待添加的顶点w和已经在生成树上的顶点v之间必定有一条连通顶v和w的权值取值最小的边。之后继续往生成树上添加顶点，直至生成树上含有n-1条边为止。注意：所添加的顶点应满足下列条件已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U