资源描述：
《图基本概念及存贮课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图图的基本概念图的存贮图的遍历生成树和最小生成树最短路径拓扑排序关键路径图的基本概念顶点:图中的一个数据元素边:两个顶点之间的关系图:是n>0个顶点组成的顶点集合V与顶点之间的关系(边)的集合E构成G=(V,E) V={vi
2、vidataobject} E={(vi,vj)
3、vi,vjV}V(G):图G的顶点集合V(E):图G边的集合14253图的基本概念无向图:若(vi,vj)E必有(vj,vi)E,并且偶对中的顶点的前后顺序无关vi,vj为邻接点有向图:若E是顶点的有序偶对,...vi,为弧尾（始点）
4、Vj为弧头（终点）1425314253图的基本概念子图:设有两个图G和G’,G=(V,E)G’=(V’,E’),且满足V’V,E’E,则称G’是G的子图14253453253142534532541425图的基本概念完全无向图:每对顶点之间都有一条边的无向图 具有n个顶点的完全无向图有n*(n-1)/2条边完全有向图:每对顶点之间都有边和的有向图具有n个顶点的完全有向图有n*(n-1)条边213213图的基本概念无向图路径:顶点v到w的路径:是由不同顶点组成的顶点序列路径长度:路径上边的数目顶点v
5、和w连通:连通的无向图:1245314253253图的基本概念连通分量:无向图中极大连通子图12453671245367图的基本概念有向图的路径:顶点v到顶点w的路径路径长度强连通的有向图弱连通的有向图142534532131232541425123图的基本概念强连通分量:有向图的极大强连通子图弱连通分量:有向图的极大弱连通子图1425314253图的基本概念回路(环):如果图中有一条路径(v0,v1,…vk)且v0=vk则称这路径为一个回路无向回路:有向回路:1425314253图的基本概念无回路的图:如果图中没有回路……连通
6、图的生成树是G的包含其全部n个顶点的一个极小连通子图仅包括G的n-1条边142531425314253图的基本概念度:在无向图中,如vV(G),则与v邻接的顶点个数称为顶点v的度顶点v的入度:邻接到v的个数顶点v的出度:邻接于v的个数1425314253图的存贮结构邻接矩阵邻接表图的存贮结构邻接矩阵 如果G是具有n个顶点的无向图,则它的邻接矩阵A是一个n*n阶矩阵,定义A为a(i,j)=1若(i,j)E(G)且i!=j 0否则如果G是具有n个顶点的有向图,则它的邻接矩阵A是一个n*n阶矩阵,定义A为a(i,j)=1若7、>E(G)且i!=j 0否则14253A1=011101010111011101010111014253A2=0101010001010010010000010图的邻接矩阵表示法无向图的邻接矩阵定是一个对称矩阵有向图的邻接矩阵不一定是对称的无向图邻接矩阵的第i行(或第i列)非0元素的个数正好是第i个顶点的度有向图邻接矩阵的第i行(第i列)非0元素的个数正好是第i个顶点的出度(入度)可以容易确定图中任意两个顶点之间是否有边有一份电文中共使用五个字符:a,b,c,d,e,它们的出现频率依次为4,7,5,2,9,试画出对应的哈夫曼树
8、,求出每个字符的哈夫曼编码,并求出此哈夫曼树加权路径长度.1.一个无向图的邻接矩阵中各元素之和与图中边的条数相等A.正确B.错误2.在一个无向图中,所有顶点的度数之和等于所有边数的()倍.A.1/2B.1C.2D.43.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍A.1/2B.1C.2D.44.一个有N个顶点的无向图最多有()条边.A.NB.N(N-1)C.N(N-1)/2D.2N5.具有6个顶点的无向图至少应有()条边才能确保是一个连通图.A.5B.6C.7D.86.对于一个具有N个顶点和E条边的无向图,若
9、采用邻接表表示,则表头向量的大小为(),所有邻接表中的结点总数是().A.NB.N+1C.N-1D.N+EA.E/2B.EC.2ED.N+E图的存贮结构邻接表存贮由n个链表所组成,且第i个链表的结点是由与顶点i相邻接(或是由邻接于顶点i)的顶点所构成,n个链表的头指针通常按顺序方式进行存贮,构成一个顺序表14253135^124135^234^234^5^12345142531234515^23^24^4^5^邻接表存贮法如图G是无向图(有向图),有n个顶点和e条边,则图G的邻接表需2e(e)个结点组成的n个链表及由这n个链表的
10、指针组成的顺序表无向图的邻接表中,第i个链表的结点个数即为顶点i的度有向图的邻接表中,第i个链表的结点个数即为顶点i的出度求有向图中结点i的入度,…….图的存贮结构逆邻接表:把邻接到顶点i的所有顶点构成逆邻接表中第i个链表142531234513^5^2^3^4
