图基本概念及存贮

图基本概念及存贮第1页，课件共35页，创作于2023年2月图的基本概念顶点:

图中的一个数据元素边:

两个顶点之间的关系图:

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

G=(V,E)

V={vi|vidataobject}

E={(vi,vj)|vi,vjV}V(G):图G的顶点集合V(E):图G边的集合14253第2页，课件共35页，创作于2023年2月图的基本概念无向图:

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

vi,vj为邻接点有向图:

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

vi,为弧尾（始点）

Vj为弧头（终点）1425314253第3页，课件共35页，创作于2023年2月图的基本概念子图:

设有两个图G和G’,G=(V,E)G’=(V’,E’),且满足V’V,E’E,则称G’是G的子4页，课件共35页，创作于2023年2月142534532541425第5页，课件共35页，创作于2023年2月图的基本概念完全无向图:

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

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

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

具有n个顶点的完全有向图有n*(n-1)条边213213第6页，课件共35页，创作于2023年2月图的基本概念无向图路径:顶点v到w的路径:是由不同顶点组成的顶点序列路径长度:路径上边的数目顶点v和w连通:连通的无向图:1245314253253第7页，课件共35页，创作于2023年2月图的基本概念连通分量:

无向图中极大连通子图12453671245367第8页，课件共35页，创作于2023年2月图的基本概念有向图的路径:顶点v到顶点w的路径路径长度强连通的有向图弱连通的有向图142534532131232541425123第9页，课件共35页，创作于2023年2月图的基本概念强连通分量:

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

有向图的极大弱连通子图1425314253第10页，课件共35页，创作于2023年2月图的基本概念回路(环):

如果图中有一条路径(v0,v1,…vk)且v0=vk则称这路径为一个回路无向回路:有向回路:1425314253第11页，课件共35页，创作于2023年2月图的基本概念无回路的图:

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

是G的包含其全部n个顶点的一个极小连通子图仅包括G的n-1条边142531425314253第12页，课件共35页，创作于2023年2月图的基本概念度:

在无向图中,如vV(G),则与v邻接的顶点个数称为顶点v的度顶点v的入度:邻接到v的个数顶点v的出度:邻接于v的个数1425314253第13页，课件共35页，创作于2023年2月图的存贮结构邻接矩阵邻接表第14页，课件共35页，创作于2023年2月图的存贮结构邻接矩阵

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

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

把邻接到顶点i的所有顶点构成逆邻接表中第i个链表142531234513^5^2^3^4^12第25页，课件共35页，创作于2023年2月图的存贮结构带权图的邻接矩阵

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

0i=j

否则

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

0i=j

否则第26页，课件共35页，创作于2023年2月1425342639A=093049063602420第27页，课件共35页，创作于2023年2月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)}第28页，课件共35页，创作于2023年2月135^124135^234^234^5^12345第29页，课件共35页，创作于2023年2月#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;第30页，课件共35页，创作于2023年2月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;}}第31页，课件共35页，创作于2023年2月教材:P2357.17.27.37.47.57.67.77.87.9第32页，课件共35页，创作于2023年2月对下图所示的有向图,试给出:(1)邻接矩阵(2)邻接表(3)逆邻接表145263第33页，课件共35页，创作于2023年2月回答问题:(1)对于一个具有n个结点的连通无向图,如果它有且只有一个简单回路,那么此图有几条边?(2)一个具有n个结点的弱连通图至少有几条边?