数据结构第7章图.

1第7章图已经学习的数据结构线性结构：线性表、栈、队列、串、数组、广义表树形结构：二叉树、树、森林图更一般、更复杂图中的结点(即：顶点)之间的关系是任意的，即结点的前驱和后继结点个数不再限制。2计算机网络交通网络电话网络人际关系网……ABCFDE2342/31/1,21学生选课网37.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第7章图47.1图的定义和术语一．图的定义图是由顶点集合及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V---顶点集E---关系的集合图的抽象数据类型定义：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={v，w|v，w∈V且P(v，w)，v，w表示从v到w的弧，谓词P(v，w)定义了弧v，w的意义或信息}基本操作P：CreateGraph(&G，V，VR)；初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DestroyGraph(&G)；初始条件：图G存在。操作结果：销毁图G。LocateVex(G，u)；初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。GetVex(G，v)；初始条件：图G存在，v是G中某个顶点。操作结果：返回v的值。PutVex(&G，v，value)；初始条件：图G存在，v是G中某个顶点。操作结果：对v赋值value。FirstAdjVex(G，v)；初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”。NextAdjVex(G，v，w)；初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的(相对于w的)下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。InsertVex(&G，v)；初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v。DeleteVex(&G，v)；初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧。InsertArc(&G，v，w)；初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧v，w，若G是无向的则还增添对称弧w，v。DeleteArc(&G，v，w)；初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧v，w，若G是无向的则还删除对称弧w，v。DFSTraverse(G，v，Visit())；初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数。操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。BFSTraverse(G，v，Visit())；初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数。操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。}ADTGraph10二．有关图的常用术语边(v,w)弧v,wＶＷＶＷ边弧弧头弧尾有向图与无向图在有向图中，顶点对x,y是有序的。在无向图中，顶点对(x,y)是无序的。v1v2v4v3v4v5v3v2v1G1=(V1,A1)其中：V1={v1,v2,v3,v4}A1={v1,v2,v1,v3,v3,v4,v4,v1}G2=(V2,A2)其中V2={v1,v2,v3,v4,v5}A2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}1100001111222265433完全图若有n个顶点的无向图有n(n-1)/2条边,则此图为无向完全图。有n个顶点的有向图有n(n-1)条边,则此图为有向完全图。12邻接顶点若(v,w)是E(G)中的一条边，则称v与w互为邻接顶点。若v,w是E(G)中的一条弧，则称顶点v邻接到顶点ｗ，顶点w邻接自顶点v。子图设有两个图G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,则称图G’是图G的子图。权某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。0123子图013012302313顶点的度一个顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。ABECFTD(B)=OD(B)+ID(B)=3思考：边数与顶点的度的和之间有什么关系？TD(v)=ID(v)+OD(v)14路径是一个顶点序列，并且相邻的两个顶点有边或弧相连。路径长度非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径若路径上各顶点均不互相重复,则称这样的路径为简单路径。回路第一个顶点与最后一个顶点相同的路径简单回路除第一个顶点与最后一个顶点外，其余顶点不重复出现的回路。01230123012315无向图,若图中任意两个顶点之间都有路径相通，则称此图为连通图;若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。BACDFEBACDFE16有向图,若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。否则，其各个极大强连通子图称作它的强连通分量。ABECFABECF17一个有n个顶点和e条边的连通图的生成树:是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。BACDFEBACDFE在极小连通子图中增加一条边，则一定有环。在极小连通子图中去掉一条边，则成为非连通图。有n个顶点，n-1条边的图必定是生成树吗？18有向树：如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1。一个有向图的生成森林：由若干个有向树组成，含有图中全部顶点，但只有足以构成若干棵互不相交的有向树的弧。BACDFEBACDFE19若无向图中有21条边，则：1)保持该图不连通至少应具有多少个顶点？2)保持该图连通至少有多少个顶点，至多有多少个顶点？思考题1)m个顶点形成完全图，另一个顶点与这m个顶点不连通½m(m-1)=21m=7n=m+1=82)至少有7个顶点(完全图)，至多有22个顶点(生成树)207.2图的存储结构设图G=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A[n][n]，定义：一、邻接矩阵(AdjacencyMatrix),),(,,]][[否则或若01AEjiEjiji顶点表--------记录各个顶点信息邻接矩阵---------记录各个顶点之间的关系21无向图的邻接矩阵是对称的;有向图的邻接矩阵一般是不对称的。01230101101001011010A[][]012000101010A[][]22在有向图中,统计第i行1的个数可得顶点i的出度，统计第j列1的个数可得顶点j的入度。在无向图中,统计第i行(列)1的个数可得顶点i的度。23186329542031068053290410A[][]网络的邻接矩阵jiji,ji,jiji,ji,jijiji若或且若或且若,)(,)(),,(]][[0EEEEWA24#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向图，无向网}typedefstructArcCell{VRTypeadj;//VRType表示顶点关系类型，无权图：0或1；//有权图，权值，InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//关系集（即邻接矩阵）intvexnum,arcnum;//顶点数、边/弧数GraphKindkind;//图的种类}MGraph;用邻接矩阵表示的结构定义25二、邻接表(AdjacencyList)邻接表:是图的一种链式存储结构。adjvexnextarcinfo顶点的结点结构(头结点)datafirstarcdata;//顶点信息firstarc;//指向第一条依附该顶点的边/弧adjvex;//该边/弧所指向的顶点的位置nextarc;//指向下一条边/弧指针info;//该边/弧相关信息的指针边/弧的结点结构(表结点)26无向图的邻接表同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边(表结点),所有的头结点放在一个一维数组里。ABCDdatafirstarcABCD0123adjvexnextarc13021027有向图的邻接表和逆邻接表ABCABC012邻接表(出边表)ABC012逆邻接表(入边表)10201128网络(带权图)的邻接表BACD69528ABCD01231536283219(出边表)(顶点表)AD5BCADBCAD29图的邻接表存储表示#defineMAX_VERTEX_NUM20typedefstructArcNode{//表结点intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧指针InfoType*info;//该弧相关信息的指针}ArcNode;typedefstructVNode{//头结点VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];30typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数GraphKindkind;//图的种类标志}ALGraph;31邻接表的构造算法（有向带权图）voidCreateGraph(ALGraphG){cinG.vexnumG.arcnum;//输入顶点数和边数for(inti=0;iG.vexnum;i++){cinG.vertices[i].data;//输入顶点信息G.vertices[i].firstarc=NULL;}for(i=0;iG.arcnum;i++){//逐条边输入cintailheadweight;ArcNode*p=newArcNode;p-adjvex=head;p-info=weight;p-nextarc=G.vertices[tail].firstarc;//链入第//tail号链表的前端G.vertices[tail].firstarc=p;}}32三、十字链表---有向图有向图:邻接表-出边表,求入度不方便;逆邻接表-入边表,求出度不方便tailvexheadvexhlinktlinkinfotailvex和headvex分别指示弧尾和弧头这两个顶点在图中的位置，链域hlink指示弧头相同的下一条弧，而链域tlink指示弧尾相同的下一条弧.info指向该弧的相关信息。弧结点数==弧数十字链表—每一条弧对应一个结点，每个顶点对应一个结点33datafirstinfirstout顶点结点data存放和顶点相关的信息；firstin和firstout分别指向以该顶点为弧头或弧尾的第一个弧结点。34BCADABCD01230131031223十字链表举例35四、邻接多重表---无向图边结点数==边数m