资源描述：
《数据结构第7章图和广义表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构的内容1图的特点顶点的前驱和后继个数无限制图的应用顶点之间的关系是任意的图中任意两个顶点之间都可能相关图（Graph）是一种非线性结构。语言学逻辑学物理化学电信工程数学计算机科学多对多北京西安南京杭州开封洛阳27.1基本术语7.2存储结构7.3图的遍历7.4连通网的最小生成树7.5单源最短路径7.6拓朴排序7.7关键路径7.8广义表第7章图和广义表37.1图的基本术语图：记为G＝(V,E)其中：V是G的顶点集合，是有穷非空集；E是G的边集合，是有穷集。问：当E(G)为空时，图G存在否？答：还存在！但此时图G只有顶点而没有边。有向图：无向图：完全图：图
2、G中的每条边都是有方向的；图G中的每条边都是无方向的；图G任意两个顶点都有一条边相连接；若n个顶点的无向图有n(n-1)/2条边,称为无向完全图若n个顶点的有向图有n(n-1)条边,称为有向完全图V=vertexE=edge4例：判断下列4种图形各属什么类型？无向图无向图(树)有向图有向图n(n-1)/2条边n(n-1)条边完全图完全图5设有两个图G＝(V,E)和G’＝(V’,E’)。若V’V且E’E,则称图G’是图G的子图。子图：带权图：即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。＝带权图（带权的有向图与无向图）网络：
3、6顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？答：是树！而且是一棵有向树！度入度出度7简单路径：路径上各顶点v1,v2,...,vm均不互相重复。回路：例：若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。路径：在图G＝(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm，到达
4、顶点vj。则称顶点序列(vivp1vp2...vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应当是属于E的边。路径长度：非带权图的路径长度是指此路径上边的条数；带权图的路径长度是指路径上各边的权之和。8在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连
5、通分量。强连通图：连通图：生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。如果在生成树上添加1条边，必定构成一个环。若图中有n个顶点，却少于n-1条边，必为非连通图。生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。97.2图的存储结构图的特点：非线性结构（m:n）邻接表邻接多重表十字链表设计为邻接矩阵链式存储结构：顺序存储结构：无！（多个顶点，无序可言）但可用数组描述元素间关系。可用多重链表重点介绍：邻接矩阵(数组)表示法邻接表(链式)表示法107.2.1邻接矩阵（数组）表示法一个有n个顶点的图，可用两个数组存储。其中一
6、个一维数组存储数据元素（顶点）的信息，另一个二维数组（邻接矩阵）存储数据元素之间的关系（边或弧）的信息。设图G=(V,E)有n个顶点，则图的邻接矩阵是一个二维数组A[n][n]，定义为：v1v2v3v5v4v4G例1：邻接矩阵：A=（v1v2v3v4v5）v1v2v3v4v50000000000000000000000000分析1：无向图的邻接矩阵是对称的；分析2：顶点i的度＝第i行(列)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。01010101010101110101011100101010101010111010101110顶点表：1
7、1例2：有向图的邻接矩阵分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点的出度=第i行元素之和，OD(Vi)=A[i][j]顶点的入度=第i列元素之和。ID(Vi)=A[j][i]顶点的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(Vi)+ID(Vi)v1v2v3v4G邻接矩阵：A=(v1v2v3v4)v1v2v3v40000000000000000注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。顶点表：0110000000011000011000000001100012
8、容易实现图的操作，如：求某顶点的度、判断顶点之间是否
