数据结构图的基本概念本

第七章图图与其它结构对比图是一种比线性表和树更为复杂的数据结构。线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。树形结构中，数据元素之间有着明显的层次关系，并且每一层的数据元素可能和下一层中的多个元素有关，但只能和上一层中一个元素有关。图形结构中，结点之间的关系是任意的，图中任意两个数据元素之间都可能相关。本章内容1.图的基本概念2.图的存储结构3.图的遍历4.图的连通性和最小生成树问题5.图的拓扑排序和关键路径6.图的最短路径图的结构定义图G是由两个集合V和R组成。其中V是顶点的有穷非空集合，R是V中顶点偶对的有穷集合。Graph=(V,R)V={图中所有顶点}R={图中各个顶点之间的关系VR}其中，VR＝{v,w|v,w∈V且P(v,w)}v,w表示从v到w的一条弧，并称v为弧尾，w为弧头。谓词P(v,w)定义了弧v,w的意义或信息。由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。EACBD例如:G1=(V1,VR1)其中V1={A,B,C,D,E}VR1={A,B,A,E,B,C,C,D,D,B,D,A,E,C}若v,wVR必有w,vVR,则称(v,w)为顶点v和顶点w之间存在一条边。BCADFE由顶点集和边集构成的图称作无向图。例如:G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}图的基本术语网、子图完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林ABECFAEFBC设图G=(V,{VR})和图G=(V,{VR}),且VV,VRVR,则称G为G的子图。1597211132弧或边带权的图分别称作有向网或无向网。假设图中有n个顶点，e条边，则：含有e=n(n-1)/2条边的无向图称作无向完全图；含有e=n(n-1)条弧的有向图称作有向完全图；若边或弧的个数enlogn，则称作稀疏图，否则称作稠密图。对于无向图G，顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，ACDFE例如:TD(B)=3TD(A)=2边(v,w)和顶点v和w相关联。和顶点v关联的边的数目定义为顶点的度。B顶点的出度:以顶点v为弧尾的弧的数目；ABECF对有向图来说，顶点的入度:以顶点v为弧头的弧的数目。顶点的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3一般地，如果顶点vi的度记为TD(vi)，那么一个有n个顶点，e条边或弧的图，满足如下关系：11()2niieTDv设图G=(V,{VR})中的一个顶点序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,则称从顶点u到顶点w之间存在一条路径。路径上边的数目称作路径长度。ABECF如:长度为3的路径{A,B,C,F}简单路径:序列中顶点不重复出现的路径。回路或环:序列中第一个顶点和最后一个顶点相同的路径。简单回路或简单环：除第一个和最后一个顶点外，其余顶点不出现重复的回路。若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图；若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。BACDFEBACDFE若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。ABECFABECF对有向图，否则，其各个极大强连通子图称作它的强连通分量。假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。BACDFE图的基本操作1.图的建立和销毁CreatGraph(&G,V,VR)DestroyGraph(&G)2.图的遍历DFSTraverse(G,v)深度优先遍历图GBFSTraverse(G,v)广度优先遍历图G3.对顶点的操作LocateVex(G,u)GetVex(G,v)PutVex(&G,v,value)InsertVex(&G,v)DeleteVex(&G,v)4.对邻接点的操作FirstAdjVex(G,v)NextAdjVex(G,v,w)5.对图中弧的操作InsertArc(&G,v,w)DeleteArc(&G,v,w)