图基本概念及存贮精.ppt

《图基本概念及存贮精.ppt》由会员分享，可在线阅读，更多相关《图基本概念及存贮精.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图基本概念及存贮第1页，本讲稿共35页图的基本概念顶点:图中的一个数据元素边:两个顶点之间的关系图:是n0个顶点组成的顶点集合V与顶点之间的关系(边)的集合E构成 G=(V,E)V=vi|vidata object E=(vi,vj)|vi,vjVV(G):图图G的顶点集合的顶点集合V(E):图图G边的集合边的集合14253第2页，本讲稿共35页图的基本概念无向图无向图:若若(vi,vj)E必有必有(vj,vi)E,并且偶对中的顶点的前后顺序无关并且偶对中的顶点的前后顺序无关 vi,vj为为邻接点邻接点有向图有向图:若若 E是顶点的有序偶对是顶点的有序偶对,.vi,为弧尾（始点）为弧尾（始点）

2、Vj为弧头（终点）为弧头（终点）1425314253第3页，本讲稿共35页图的基本概念子图:设有两个图G和G,G=(V,E)G=(V,E),且满足VV,E E,则称G是G的子图14253453253第4页，本讲稿共35页142534532541425第5页，本讲稿共35页图的基本概念完全无向图:每对顶点之间都有一条边的无向图 具有n个顶点的完全无向图有n*(n-1)/2条边完全有向图:每对顶点之间都有边和的有向图 具有n个顶点的完全有向图有n*(n-1)条边213213第6页，本讲稿共35页图的基本概念无向图路径:顶点v到w的路径:是由不同顶点组成的顶点序列路径长度:路径上边的数目顶点v和w连

3、通:连通的无向图:1245314253253第7页，本讲稿共35页图的基本概念连通分量:无向图中极大连通子图12453671245367第8页，本讲稿共35页图的基本概念有向图的路径:顶点v到顶点w的路径路径长度强连通的有向图弱连通的有向图142534532131232541425123第9页，本讲稿共35页图的基本概念强连通分量:有向图的极大强连通子图弱连通分量:有向图的极大弱连通子图1425314253第10页，本讲稿共35页图的基本概念回路(环):如果图中有一条路径(v0,v1,vk)且v0=vk则称这路径为一个回路无向回路:有向回路:1425314253第11页，本讲稿共35页图的基本

4、概念无回路的图:如果图中没有回路连通图的生成树 是G的包含其全部n个顶点的一个极小连通子图仅包括G的n-1条边142531425314253第12页，本讲稿共35页图的基本概念度:在无向图中,如vV(G),则与v邻接的顶点个数称为顶点v的度顶点v的入度:邻接到v的个数顶点v的出度:邻接于v的个数1425314253第13页，本讲稿共35页图的存贮结构邻接矩阵邻接表第14页，本讲稿共35页图的存贮结构邻接矩阵 如果G是具有n个顶点的无向图无向图,则它的邻接矩阵A是一个n*n阶矩阵,定义A为 a(i,j)=1 若(i,j)E(G)且i!=j 0 否则 如果G是具有n个顶点的有向图有向图,则它的邻接

5、矩阵A是一个n*n阶矩阵,定义A为 a(i,j)=1 若E(G)且i!=j 0 否则第15页，本讲稿共35页14253A1=0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 014253A2=0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0第16页，本讲稿共35页图的邻接矩阵表示法无向图的邻接矩阵定是一个对称矩阵有向图的邻接矩阵不一定是对称的无向图邻接矩阵的第i行(或第i列)非0元素的个数正好是第i个顶点的度有向图邻接矩阵的第i行(第i列)非0元素的个数正好是第i个顶点的出度(入度)可以容易确定图中

6、任意两个顶点之间是否有边第17页，本讲稿共35页有一份电文中共使用五个字符:a,b,c,d,e,它们的出现频率依次为4,7,5,2,9,试画出对应的哈夫曼树,求出每个字符的哈夫曼编码,并求出此哈夫曼树加权路径长度.第18页，本讲稿共35页1.一个无向图的邻接矩阵中各元素之和与图中边的一个无向图的邻接矩阵中各元素之和与图中边的 条数相等条数相等 A.正确正确 B.错误错误2.在一个无向图中在一个无向图中,所有顶点的度数之和等于所有边所有顶点的度数之和等于所有边数的数的()倍倍.A.1/2 B.1 C.2 D.43.在一个有向图中在一个有向图中,所有顶点的入度之和等于所有顶所有顶点的入度之和等于所

7、有顶 点的出度之和的点的出度之和的()倍倍 A.1/2 B.1 C.2 D.44.一个有一个有N个顶点的无向图最多有个顶点的无向图最多有()条边条边.A.N B.N(N-1)C.N(N-1)/2 D.2N第19页，本讲稿共35页5.具有具有6个顶点的无向图至少应有个顶点的无向图至少应有()条边才能条边才能 确保是一个连通图确保是一个连通图.A.5 B.6 C.7 D.86.对于一个具有对于一个具有N个顶点和个顶点和E条边的无向图条边的无向图,若采用若采用 邻接表表示邻接表表示,则表头向量的大小为则表头向量的大小为(),所有邻接所有邻接 表中的结点总数是表中的结点总数是().A.N B.N+1

8、C.N-1 D.N+E A.E/2 B.E C.2E D.N+E第20页，本讲稿共35页图的存贮结构邻接表存贮 由n个链表所组成,且第i个链表的结点是由与顶点i相邻接(或是由邻接于顶点i)的顶点所构成,n个链表的头指针通常按顺序方式进行存贮,构成一个顺序表第21页，本讲稿共35页14253135 124135 234 234 5 12345第22页，本讲稿共35页142531234515 23 24 4 5 第23页，本讲稿共35页邻接表存贮法如图G是无向图(有向图),有n 个顶点和e条边,则图G的邻接表需2e(e)个结点组成的n个链表及由这n个链表的指针组成的顺序表无向图的邻接表中,第i个链

9、表的结点个数即为顶点i的度有向图的邻接表中,第i个链表的结点个数即为顶点i的出度求有向图中结点i的入度,.第24页，本讲稿共35页图的存贮结构逆邻接表:把邻接到顶点i的所有顶点构成逆邻接表中第i个链表142531234513 5 2 3 4 12第25页，本讲稿共35页图的存贮结构带权图的邻接矩阵 A(i,j)=Wij i!=j 且(i,j)E(G)0 i=j 否则 A(i,j)=Wij i!=j 且E(G)0 i=j 否则第26页，本讲稿共35页1425342639A=0 9 3 0 49 0 6 3 6 0 2 4 2 0第27页，本讲稿共35页14253G=(V,E)V=(1,2,3,4

10、,5)E=(4,5),(3,5),(3,4),(2,5),(2,3),(1,4),(1,3),(1,2)第28页，本讲稿共35页135 124135 234 234 5 12345第29页，本讲稿共35页#include#define MAXN 50#define MAXN 100struct l_node int ver;struct l_node*link;typedef struct l_node L_NODE;typedef structint ver1;int ver2;E_NODE;L_NODE*headMAXN;E_NODE eMAXN;int n,m,u;第30页，本讲稿共35

11、页void creat_adj_list(head,n,e,m)L_NODE*head;E_NODE e;int n,m;int i,u,v;L_NODE*p;for(i=1;i=n;i+)headi=NULL;for(i=0;iver=v;p-link=headu;headu=p;p=(L_NODE*)moalloc(sizeof(L_NODE);p-ver=u;p-link=headv;headv=p;第31页，本讲稿共35页教材:P235 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9第32页，本讲稿共35页对下图所示的有向图,试给出:(1)邻接矩阵 (2)邻接表

12、 (3)逆邻接表145263第33页，本讲稿共35页回答问题:(1)对于一个具有n个结点的连通无向图,如果它有且只有 一个简单回路,那么此图有几条边?(2)一个具有n个结点的弱连通图至少有几条边?(3)如果G1是一个具有n个顶点的连通无向图,那么G1最多 有多少条边?G1最少有多少条边?(4)如果G2是一个具有n个顶点的强连通有向图,那么G2最 多有多少条边?G2最少有多少条边?(5)如果G3是一个具有n个顶点的弱连通有向图,那么G3最 多有多少条边?G3最少有多少条边?第34页，本讲稿共35页设G为有n个顶点的无向连通图,证明G至少有n-1条边.若无向图G的顶点度数的最小值大于或等于2,则G必然存在回路,试给出其证明.作业第35页，本讲稿共35页