数据结构图

第1页7.1图的术语与定义图的定义图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对或有序对。图的分类有向图无向图第2页7.1图的术语与定义图的定义有向图——有向图G是由两个集合V(G)和E(G)组成的。其中：V(G)是顶点的非空有限集。E(G)是有向边（也称弧）(的有限集合，弧是顶点的有序对，记为v,w，v,w是顶点，v为弧尾，w为弧头。第3页7.1图的术语与定义例如：G1=V2,E2V1={A,B,C,D,E}E1={A,B,A,E,B,C,C,D,D,B,D,A,E,C}EACBD第4页7.1图的术语与定义图的定义无向图——无向图G是由两个集合V(G)和E(G)组成的。其中：V(G)是顶点的非空有限集。E(G)是边的有限集合，边是顶点的无序对，记为(v,w)或(w,v)，并且(v,w)=(w,v)。第5页7.1图的术语与定义例如：G2=V1,E1V2={v0,v1,v2,v3,v4}E2={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4)}V0V4V3V1V2第7页7.1图的术语与定义图的应用举例例1、交通图（公路、铁路）顶点：地点边：连接地点的路例2、电路图顶点：元件边：连接元件之间的线路例3、通讯线路图顶点：地点边：地点间的连线例4、各种流程图如产品的生产流程图。顶点：工序边：各道工序之间的顺序关系第8页7.1图的术语与定义图的基本术语1邻接点及关联边邻接点：边的两个顶点关联边：若边e=(v,u),则称顶点v、u关连边e2顶点的度、入度、出度顶点V的度=与V相关联的边的数目在有向图中：顶点V的出度=以V为起点有向边数顶点V的入度=以V为终点有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n，边数为e图的所有顶点的度数和=2*e（每条边对图的所有顶点的度数和“贡献”2度）V0V4V3V1V2eV0V1V2V3第9页7.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，则称该序列为回路。第10页7.1图的术语与定义例如在图G1中，V0,V1,V2,V3是V0到V3的路径；V0,V1,V2,V3,V0是回路。在图G2中，V0,V2,V3是V0到V3的路径；V0,V2,V3,V0是回路。无向图G1有向图G2V0V4V3V1V2V0V1V2V3第11页7.1图的术语与定义连通图（强连通图）在无（有）向图G=V,E中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）非连通图连通图强连通图非强连通图V0V1V2V3V0V4V3V1V2V0V1V2V3V0V2V3V1V5V4第12页7.1图的术语与定义子图设有两个图G=（V，E），G1=（V1，E1），若V1V，E1E，E1关联的顶点都在V1中，则称G1是G的子图；例(b)、(c)是(a)的子图(a)(b)(c)V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2第13页7.1图的术语与定义连通分图（强连通分量）无向图G的极大连通子图称为G的连通分量。极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。连通分图非连通图V0V2V3V1V5V4第14页7.1图的术语与定义连通分图（强连通分量）有向图D的极大强连通子图称为D的强连通分量。极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。强连通分量V0V1V2V3V0V2V3V1第15页7.1图的术语与定义生成树包含无向图G所有顶点的极小连通子图称为G生成树。极小连通子图意思是：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通，若T是G的生成树当且仅当T满足如下条件：T是G的连通子图T包含G的所有顶点T中无回路连通图G1G1的生成树V0V4V3V1V2V0V4V3V1V2第16页V0V1V2V37.2图的存储结构一、数组表示法（邻接矩阵表示）邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：A[i][j]=1若(vi,vj)E或vi,vjE0否则0101010101010111010001100在数组表示法中，用邻接矩阵表示顶点间的关系V0V4V3V1V20110000000011000第17页7.2图的存储结构二、邻接表邻接表是图的链式存储结构1、无向图的邻接表顶点：通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边：用线性链表存储。V0V4V3V1V2201234m-1V0V1V2V3V413422110034该结点表示边(V2,V4)，其中的4是V4在一维数组中的位置第18页7.2图的存储结构结点typedefstructArcNode{intadjvex;//邻接点域，//存放与Vi邻接的点在表头数组中的位置structArcNode*next;//链域，下一条边或弧}ArcNode;表头结点typedefstructtnode{VertexTypevexdata;//存放顶点信息ArcNode*firstarc;//指向第一个邻接点}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//顶点数和弧数intkind;//图的种类}adjvexnextvexdatafirstarc第19页7.2图的存储结构无向图的邻接表的特点1）在G邻接表中，同一条边对应两个结点；2）顶点v的度：等于v对应线性链表的长度；3）判定两顶点v，u是否邻接：要看v对应线性链表中有无对应的结点。4）在G中增减边：要在两个单链表插入、删除结点；5）设存储顶点的一维数组大小为m（m图的顶点数n），图的边数为e，G占用存储空间为：m+2*e。G占用存储空间与G的顶点数、边数均有关；适用于边稀疏的图。第20页7.2图的存储结构二、邻接表2、有向图的邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储1234v0v2v3v1vexdatafirstarc3241^^^^adjvexnext类似于无向图的邻接表，所不同的是：以同一顶点为起点的弧：用线性链表存储V0V1V2V3第21页7.2图的存储结构二、邻接表3、有向图的逆邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储。1234v0v2v3v1vexdatafirstarc4113^^^^类似于有向图的邻接表，所不同的是：以同一顶点为终点弧：用线性链表存储V0V1V2V3第22页7.2图的存储结构三、有向图的十字链表表示法弧结点：typedefstructArcBox{inttailvex,headvex;//弧尾、弧头在表头数组中位置structarcnode*hlink；//指向弧头相同的下一条弧structarcnode*tlink;//指向弧尾相同的下一条弧}ArcBox;tailvexheadvexhlinktlink顶点结点：typedefstructVexNode{VertexTypedata;//存与顶点有关信息ArcBox*firstin；//指向以该顶点为弧头的第一个弧结点ArcBox*firstout;//指向以该顶点为弧尾的第一个弧结点}VexNode;VexNodeOLGraph[M];datafirstinfirstout第23页7.2图的存储结构三、有向图的十字链表表示法例bdacabcd123413123431434241^^^^^^^^相同弧尾相同弧头第24页7.2图的存储结构四、无向图的邻接多重表表示法顶点结点：typedefstructVexBox{VertexTypedata;//存与顶点有关的信息EBox*firstedge;//指向第一条依附于该顶点的边}VexBox;VexBoxAMLGraph[M];datafirstedge边结点：typedefstructEBox{VisitIfmark;//标志域，记录是否已经搜索过intivex,jvex;//该边依附的两个顶点在表头数组中位置structEBox*ilink,*jlink;//分别指向依附于ivex和jvex的下一条边}EBox;markivexilinkjvexjlink第25页7.2图的存储结构四、无向图的邻接多重表表示法例aecbd1234acdb5e121434323552^^^^^第26页7.3图的遍历连通图的深度遍历（DFS）从图中某顶点v出发：1）访问顶点v；2）对v的每个未被访问的邻接点wj，从wj出发，继续对图进行深度优先遍历。深度遍历：V1,V2,V4,V5,V8,V3,V6,V7例V1V8V7V6V5V4V3V2V1V2V4V3V8V7V6V5深度遍历：V1,V3,V6,V7,V2,V5,V8,V4第27页7.3图的遍历图的深度遍历（DFS）Vw1SG1SG2SG3w2w3w2W1、W2和W3均为V的邻接点，SG1、SG2和SG3分别为含顶点W1、W2和W3的子图。访问顶点V：for(W1、W2、W3)若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。第28页7.3图的遍历图的深度遍历（DFS）Vw1SG1SG2SG3w2w3w2从图解可见：1.从深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点设立一个“访问标志visited[w]”。2.如何判别V的邻接点是否被访问？第29页7.3图的遍历Booleanvisited[MAX];//访问标志数组Status(*VisitFunc)(intv);//访问函数voidDFS(GraphG,intv){//从顶点v出发，深度优先搜索遍历连通图Gvisited[v]=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w//递归调用DFS}//DFS第30页7.3图的遍历非连通图的深度优先搜索遍历首先将图中每个顶点的访问标志设为FALSE，之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。第31页7.3图的遍历voidDFSTraverse(GraphG,Status(*Visit)(intv)){//对图G作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;++v)visited[v]=FALSE;//访问标志数组初始化for(v=0;vG.vexnum;++v)if(!visited[v])DFS(G,v);//对尚未访问的顶点调用DFS}第32页7.3图的遍历例如：abchdekfgFFFFFFFFFTTTTTTTTTachdkfebgachkfedbg访问标志:访问次序:012345678第33页7.3图的遍历图的深度遍历（DFS）——算法7.4和7.5开始访问V，置标志求V邻接点有邻接点w求下一邻接点W访问过结束NYNYDFS(G,w)开始标志数组初始化V=0V访问过?DFS(g,v)V=V+1VVexNum结束NYYN第34页7.3图的遍历图的深度遍历（DFS）——递归算法V1V2V4V5V3V7V6V8例12341342vexdatafirstarc2783^^^a