数据结构第七章-图演示(1)

结束第1页结束第2页第七章图第七章图7.1图的概念7.2图的存储结构7.3图的遍历7.4遍历的应用7.5有向无环图及应用结束第3页第七章图本章介绍另一种非线性数据结构——图图：是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继；结束第4页第七章图学习要点1．熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系；2．熟练掌握图的两种遍历：深度优先遍历和广度优先遍历的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略3．理解课件中讨论的各种图的算法；结束第5页第七章图7.1图的概念一图的概念二图的应用三图的基本操作四图的基本术语结束第6页7.1图的基本概念一图的概念图G由两个集合构成，记作G=V,E其中V是顶点的非空有限集合，E是边的有限集合，其中边是顶点的无序对或有序对集合。例G1=V1,E1V1={v1,v2,v3,v4,v5}E1={(v1,v2),(v1,v3),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}G1图示无序对(vi,vj)：用连接顶点vi、vj的线段表示，称为无向边；V5V1V2V4V3结束第7页7.1图的基本概念例G2=V2,E2V2={v1,v2,v3,v4}E2={v1,v2,v1,v3,v3,v4,v4,v1}G2图示有序对vi,vj：用以为vi起点、以vj为终点的有向线段表示，称为有向边或弧；无向图：在图G中，若所有边是无向边，则称G为无向图；有向图：在图G中，若所有边是有向边，则称G为有向图；混和图：在图G中，即有无向边也有有向边，则称G为混合图；V1V2V3V4结束第8页7.1图的基本概念二图的应用举例例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系V5V1V2V4V3结束第9页7.1图的基本概念三图的基本术语网、子图完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林结束第10页ABECFAEABBC设图G=(V,{VR})和图G=(V,{VR}),且VV,VRVR,则称G为G的子图。1597211132弧或边带权的图分别称作有向网或无向网。7.1图的基本概念结束第11页7.1图的基本概念子图设有两个图G=（V，E）、G1=（V1，E1），若V1V，E1E，E1关联的顶点都在V1中，则称G1是G的子图；例图2、图3是图1的子图V5V1V2V4V3V5V1V2V3V5V1V2V4V3图1图2图3结束第12页假设图中有n个顶点，e条边，则含有e=n(n-1)/2条边的无向图称作完全图;含有e=n(n-1)条弧的有向图称作有向完全图;若边或弧的个数enlogn，则称作稀疏图，否则称作稠密图。7.1图的基本概念结束第13页假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，ACDFE例如:ID(B)=3ID(A)=2边(v,w)和顶点v和w相关联。和顶点v关联的边的数目定义为边的度。B7.1图的基本概念结束第14页顶点的出度:以顶点v为弧尾的弧的数目;ABECF对有向图来说，顶点的入度:以顶点v为弧头的弧的数目。顶点的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=37.1图的基本概念结束第15页推论：如果顶点Vi的度为TD（Vi），那么有n个顶点，e条边或弧的图，满足如下关系niivTDe1)(21结束第16页设图G=(V,{VR})中的一个顶点序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,则称从顶点u到顶点w之间存在一条路径。路径上边的数目称作路径长度。ABECF如:从A到F长度为3的路径{A,B,C,F}简单路径:指序列中顶点不重复出现的路径。简单回路:指序列中第一个顶点和最后一个顶点相同的路径。结束第17页若图G中任意两个顶点之间都有路径相通，则称此图为连通图;若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通；BACDFEBACDFE结束第18页强连通图：在有向图中，如果对每一对Vi，VjV，ViVj，从Vi到Vj和从Vj到Vi都存在路径，则称G是强连通图。有向图G的极大强连通子图称为强连通分量。12341234不是强连通图两个强连通分量结束第19页假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。BACDFE结束第20页7.1图的基本概念V5V1V2V4V3V5V1V2V4V3生成树（包含无向图G所有顶点的的极小连通子图称为G生成树极小连通子图意思是：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通，若T是G的生成树当且仅当T满足如下条件T是G的连通子图T包含G的所有顶点T中无回路结束第21页结构的建立和销毁插入或删除顶点对邻接点的操作对顶点的访问操作遍历插入和删除弧基本操作图的基本操作结束第22页CreatGraph(&G,V,VR)://按定义(V,VR)构造图DestroyGraph(&G)://销毁图结构的建立和销毁结束第23页对顶点的访问操作LocateVex(G,u);//若G中存在顶点u，则返回该顶点在//图中“位置”；否则返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//对v赋值value。结束第24页对邻接点的操作FirstAdjVex(G,v);//返回v的“第一个邻接点”。若该顶点//在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);//返回v的（相对于w的）“下一个邻接//点”。若w是v的最后一个邻接点，则//返回“空”。结束第25页插入或删除顶点InsertVex(&G,v);//在图G中增添新顶点v。DeleteVex(&G,v);//删除G中顶点v及其相关的弧。结束第26页插入和删除弧InsertArc(&G,v,w);//在G中增添弧v,w，若G是无向的，//则还增添对称弧w,v。DeleteArc(&G,v,w);//在G中删除弧v,w，若G是无向的，//则还删除对称弧w,v。结束第27页遍历DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图G，并对每//个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历图G，并对每//个顶点调用函数Visit一次且仅一次。结束第28页第七章图7.2图的存储结构一数组表示法二邻接表结束第29页7.2图的存储结构图是多对多的结构，比线性结构、树结构复杂，所以其存储结构也要复杂些。与线性结构、树结构一样，图的存储结构至少要保存两类信息：1)顶点的数据2)顶点间的关系顶点的编号为了使图的存储结构与图一一对应，在讨论图的存储结构时，首先要给图的所有顶点编号。本课程介绍两类图的存储结构数组表示法邻接表（邻接表，逆邻接表）设G=V,E是图,V={v1,v2,v3,…vn},设顶点的的角标为它的编号如何表示顶点间的关系？结束第30页7.2图的存储结构邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：一数组表示法数组表示法是图的一种顺序存储结构在数组表示法中，用邻接矩阵表示顶点间的关系A[i][j]=1若(vi,vi+1)E或vi,vi+1E0否则V5V1V2V4V301010101010101110100011000110000000011000V1V2V3V4结束第31页7.2图的存储结构数组表示法顶点的存储：用一维数组存储（按编号顺序）顶点间关系：用二维数组存储图的邻接矩阵；012345m-1V1V2V3V4V5存储顶点的一维数组存储邻接矩阵的二维数组010101010101234mm+1m+2m+3m+4结束第32页7.2图的存储结构数组表示法类型定义#defineMAX_VERTEX_NUMm//最大顶点个数typedefenum{DG,DN,AG,AN}GraphKind;//{有向图，有向网，无向图，无向网}typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型。对无权图，用1或0//表示相邻否；对带权图，则为权值类型。}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//存储顶点的一维数组AdjMatrixarcs;//存储邻接矩阵的二维数组intvexnum,arcnum;//图的当前顶点数和弧数GraphKindkind;//图的种类标志}Mgraph;此处省略了*info域结束第33页7.2图的存储结构设G是Mgraph类型的变量，用于存储无向图，该图有n个顶点，e条边G的图示如下：G.vexsG.arcsG.vexnumG.arcnuG.kindV10neAG顶点数组存储邻接矩阵的二维数组结束第34页7.2图的存储结构无向图数组表示法特点：1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；2）顶点v的度：等于二维数组对应行（或列）中1的个数；3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1；4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；5）设存储顶点的一维数组大小为m(m图的顶点数n),G占用存储空间：m+m2；G占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图；对有向图的数组表示法可做类似的讨论结束第35页njijiAVTD1),()(图的邻接矩阵完全表示了一个图，运算可借助其实现：无向图顶点Vi的度是矩阵中第i行元素之和有向图顶点Vi的出度是矩阵中第i行元素之和njijiAVOD1),()(无向图顶点Vi的入度是矩阵中第i列元素之和njijiAVID1),()(网的邻接矩阵设图G=(V,{E})含有n(n=1)个顶点V={V1,V2,…,Vn},则元素为：7.2图的存储结构结束第36页之反，或，若VRvvvvwjiAijjiji,,),(,的n*n矩阵A，称为网G的邻接矩阵。例：求下面的网的邻接矩阵。12345642732019509110015330420003300735000000500091000190000001500010000邻接表若无向图G=(V,{E})含有n个结点，则可用n个链表表示图G：头结点：datafirstarc表结点：adjvexnextarcinfo7.2图的存储结构结束第37页请看书162页算法7。1算法7。1是在邻接矩阵存储结构MGraph上对图的构造操作的实现框架，它根据图G的种类调用具体构造算法。如果G是无向网，则调用算法7.1构造一个具有n个顶点和e条边的无向网的时间复杂度是O（n2+e.n）,其中对邻接矩阵G.arcs的初始化耗费了O(n2)的时间.7.2图的存储结构结束第38页7.2图的存储结构二邻接表邻接表是图的链式存储结构1无向图的邻接表顶点：通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边：用线性链表存储V5V1V2V4V3例01234m-1V1V2V3V4V513422110043该结点表示边（V1V2）,其中的1是V2在一维数组中的位置结