图基本概念及存贮

图基本概念及存贮第一页，共三十五页，2022年，8月28日图的基本概念顶点:

图中的一个数据元素边:

两个顶点之间的关系图:

是n>0个顶点组成的顶点集合V与顶点之间的关系(边)的集合E构成

G=(V,E)

V={vi|vidataobject}

E={(vi,vj)|vi,vjV}V(G):图G的顶点集合V(E):图G边的集合14253第二页，共三十五页，2022年，8月28日图的基本概念无向图:

若(vi,vj)E必有(vj,vi)E,并且偶对中的顶点的前后顺序无关

vi,vj为邻接点有向图:

若<vi,vj>E是顶点的有序偶对,...

vi,为弧尾（始点）

Vj为弧头（终点）1425314253第三页，共三十五页，2022年，8月28日图的基本概念子图:

设有两个图G和G’,G=(V,E)G’=(V’,E’),且满足V’V,E’E,则称G’是G的子四页，共三十五页，2022年，8月28日142534532541425第五页，共三十五页，2022年，8月28日图的基本概念完全无向图:

每对顶点之间都有一条边的无向图

具有n个顶点的完全无向图有n*(n-1)/2条边完全有向图:

每对顶点之间都有边<vi,vj>和<vj,vi>的有向图

具有n个顶点的完全有向图有n*(n-1)条边213213第六页，共三十五页，2022年，8月28日图的基本概念无向图路径:顶点v到w的路径:是由不同顶点组成的顶点序列路径长度:路径上边的数目顶点v和w连通:连通的无向图:1245314253253第七页，共三十五页，2022年，8月28日图的基本概念连通分量:

无向图中极大连通子图12453671245367第八页，共三十五页，2022年，8月28日图的基本概念有向图的路径:顶点v到顶点w的路径路径长度强连通的有向图弱连通的有向图142534532131232541425123第九页，共三十五页，2022年，8月28日图的基本概念强连通分量:

有向图的极大强连通子图弱连通分量:

有向图的极大弱连通子图1425314253第十页，共三十五页，2022年，8月28日图的基本概念回路(环):

如果图中有一条路径(v0,v1,…vk)且v0=vk则称这路径为一个回路无向回路:有向回路:1425314253第十一页，共三十五页，2022年，8月28日图的基本概念无回路的图:

如果图中没有回路……连通图的生成树

是G的包含其全部n个顶点的一个极小连通子图仅包括G的n-1条边142531425314253第十二页，共三十五页，2022年，8月28日图的基本概念度:

在无向图中,如vV(G),则与v邻接的顶点个数称为顶点v的度顶点v的入度:邻接到v的个数顶点v的出度:邻接于v的个数1425314253第十三页，共三十五页，2022年，8月28日图的存贮结构邻接矩阵邻接表第十四页，共三十五页，2022年，8月28日图的存贮结构邻接矩阵

如果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若<i,j>E(G)且i!=j

0否则第十五页，共三十五页，2022年，8月28日14253A1=011101010111011101010111014253A2=0101010001010010010000010第十六页，共三十五页，2022年，8月28日图的邻接矩阵表示法无向图的邻接矩阵定是一个对称矩阵有向图的邻接矩阵不一定是对称的无向图邻接矩阵的第i行(或第i列)非0元素的个数正好是第i个顶点的度有向图邻接矩阵的第i行(第i列)非0元素的个数正好是第i个顶点的出度(入度)可以容易确定图中任意两个顶点之间是否有边第十七页，共三十五页，2022年，8月28日有一份电文中共使用五个字符:a,b,c,d,e,它们的出现频率依次为4,7,5,2,9,试画出对应的哈夫曼树,求出每个字符的哈夫曼编码,并求出此哈夫曼树加权路径长度.第十八页，共三十五页，2022年，8月28日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.2N第十九页，共三十五页，2022年，8月28日5.具有6个顶点的无向图至少应有()条边才能确保是一个连通图.A.5B.6C.7D.86.对于一个具有N个顶点和E条边的无向图,若采用邻接表表示,则表头向量的大小为(),所有邻接表中的结点总数是().A.NB.N+1C.N-1D.N+EA.E/2B.EC.2ED.N+E第二十页，共三十五页，2022年，8月28日图的存贮结构邻接表存贮

由n个链表所组成,且第i个链表的结点是由与顶点i相邻接(或是由邻接于顶点i)的顶点所构成,n个链表的头指针通常按顺序方式进行存贮,构成一个顺序表第二十一页，共三十五页，2022年，8月28日14253135^124135^234^234^5^12345第二十二页，共三十五页，2022年，8月28日142531234515^23^24^4^5^第二十三页，共三十五页，2022年，8月28日邻接表存贮法如图G是无向图(有向图),有n个顶点和e条边,则图G的邻接表需2e(e)个结点组成的n个链表及由这n个链表的指针组成的顺序表无向图的邻接表中,第i个链表的结点个数即为顶点i的度有向图的邻接表中,第i个链表的结点个数即为顶点i的出度求有向图中结点i的入度,…….第二十四页，共三十五页，2022年，8月28日图的存贮结构逆邻接表:

把邻接到顶点i的所有顶点构成逆邻接表中第i个链表142531234513^5^2^3^4^12第二十五页，共三十五页，2022年，8月28日图的存贮结构带权图的邻接矩阵

A(i,j)=Wiji!=j且(i,j)E(G)

0i=j

否则

A(i,j)=Wiji!=j且<i,j>E(G)

0i=j

否则第二十六页，共三十五页，2022年，8月28日1425342639A=093049063602420第二十七页，共三十五页，2022年，8月28日14253G=(V,E)V=(1,2,3,4,5)E={(4,5),(3,5),(3,4),(2,5),(2,3),(1,4),(1,3),(1,2)}第二十八页，共三十五页，2022年，8月28日135^124135^234^234^5^12345第二十九页，共三十五页，2022年，8月28日#include<stdio.h>#defineMAXN50#defineMAXN100structl_node{intver;structl_node*link;};typedefstructl_nodeL_NODE;typedefstruct{intver1;intver2;}E_NODE;L_NODE*head[MAXN];E_NODEe[MAXN];intn,m,u;第三十页，共三十五页，2022年，8月28日voidcreat_adj_list(head,n,e,m)L_NODE*head[];E_NODEe[];intn,m;{inti,u,v;L_NODE*p;for(i=1;i<=n;i++)head[i]=NULL;for(i=0;i<m;i++){u=e[i].ver1;v=e[i]=ver2;

p=(L_NODE*)moalloc(sizeof(L_NODE));p->ver=v;p->link=head[u];head[u]=p;p=(L_NODE*)moalloc(sizeof(L_NODE));p->ver=u;p->link=head[v];head[v]=p;}}第三十一页，共三十五页，2022年，8月28日教材:P2357.17.27.37.47.57.67.77.87.9第三十二页，共三十五页，2022年，8月28日对下图所示的有向图,试给出:(1)邻接矩阵(2)邻接表(3)逆邻接表145263第三十三页，共三十五页，2022年，8月28日回答问题:(1)对于一个具有n个结点的连通无向图,如果它有且只有一个简单回路,那么此图有几条边?(2)一个具有n个结点的弱连通图至少有几条边?(3