数据结构-图的基本概念和存储结构.ppt

图和图的存储结构图和图的存储结构图的结构定义图的结构定义—有向图图的结构定义—无向图图的结构定义—无向图名词和术语名词和术语名词和术语名词和术语名词和术语名词和术语名词和术语名词和术语名词和术语名词和术语名词和术语名词和术语名词和术语名词和术语名词和术语基本操作基本操作基本操作基本操作基本操作基本操作基本操作一、图的数组(邻接矩阵)存储表示图的存储表示--邻接矩阵图的存储表示--邻接矩阵图的存储表示--邻接矩阵图的存储表示--邻接矩阵图的存储表示--邻接矩阵图的存储表示--邻接表图的存储表示--邻接表图的存储表示--邻接表图的存储表示--邻接表图的存储表示--邻接表图的存储表示--邻接表图的存储表示--有向图的十字链表图的存储表示--有向图的十字链表弧的结点结构表示顶点的结点结构表示十字链表无向图的邻接多重表存储表示无向图的邻接多重表存储表示无向图的邻接多重表存储表示无向图的邻接多重表存储表示创建图1、输入参数:vexnum,arcnum,GraghKindStatusCreateGragh(ALGraph&G){//建立邻接表
scanf(”%d%d%d”,&G.vexnum,&G.arcnum,&G.GraghKind);
if……
switch(G.GraghKind){
caseDG:returnCreateDG(G);
caseDN:returnCreateDN(G);
caseUDG:returnCreateUDG(G);
caseUDN:returnCreateUDN(G);
default:returnERROR;}
} StatusCreateDG(ALGraph&G){
for(i=0;i<G.vexnum;i++){
scanf(&data);
G.vertices[i].data=data
}//输入顶点信息
……
} StatusCreateDG(ALGraph&G){
……
for(i=0;i<G.arcnum;i++){//输入边的信息
scanf(”%d%d”,&v,&w)//形式2
p=newarcnode;//建立结点
if(!p)returnERROR;
p.adjvex=w;
p.nextarc=G.vertices[v].firstarc;//顶点v的链表
G.vertices[v].firstarc=p;//添加到最左边
}
} 时间复杂度分析(第2种输入形式)
第1个for:n
第2个for:e
所以O(n+e)存储结构的转换StatusTranlateDG(ALGraphG1,MGraph&G2){//将G1转换为G2
//设置参数
G2.GraghKind=G1.GraghKind;
G2.vexnum=G1.vexnum;
G2.arcnum=G1.arcnum
//复制顶点
for(i=0;i<G1.vexnum;i++)G2.vexs[i]=G1.vertices[i].data;
//复制弧
for(i=0;i<G2.vexnum;i++)
for(j=0;j<G2.vexnum;j++)
G2.arcs[i][j]=0;
} StatusTranlateDG(ALGraphG1,MGraph&G2){
……
for(i=0;i<G1.vexnum;i++){//复制G1每个顶点的邻接点
p=G1.vertices[i].firstarc;
while(p){
G2.arcs[i][p.adjvex]=1;
p=p->nextarc;
}
}
} 课堂练习V2下面关于图的存储的叙述中正确的是（）A）用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关B）用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关C）用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关D）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关小结和作业小结和作业