【数据结构】图的基本操作-创新互联
分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作:
成都创新互联是一家专注于成都网站制作、网站设计与策划设计,郴州网站建设哪家好?成都创新互联做网站,专注于网站建设10年,网设计领域的专业建站公司;建站业务涵盖:郴州等地区。郴州做网站价格咨询:028-86922220- 增加一个新结点v,Insert(G,v);
- 删除顶点v及其相关的边,Delete(G,v);
- 增加一条边
,Insert(G,v,w); - 删除一条边
,Delete(G,v,w);
1、邻接矩阵实现:
邻接矩阵实现图的基本操作,主要通过二维数组寻址方式进行数据处理。函数包括:邻接矩阵创建并存储数据、顶点寻址、增加顶点、删除顶点、增加边、删除边、邻接矩阵打印。
邻接矩阵创建并存储,先根据输入的总顶点数、边数对二维数组初始化,边权为MaxInt,表示两点无关联。将顶点信息存储至顶点数组集中。存储数据时,依次循环根据输入边相关的两点以及权重,先通过顶点寻址函数寻找两点位置,后利用二维数组将矩阵相应位置边权赋予新值,完成数据存储。
顶点寻址函数设计,只需根据顶点信息,在顶点数组集中遍历,返回其对应数组下标即可。
增加顶点时,在顶点数组集中增加一位,并将邻接矩阵中多加的一行一列赋值为MaxInt。
删除顶点时,需要通过数组移动,列方面从待删点开始右侧数据,全部左移;行方面从待删顶点开始下方数据,全部上移。最后删除顶点在顶点数组中的位置。上述操作通过数组移动实现开销较大,也可以在删除时,将最后一个顶点相关信息替代删除顶点,因为本身顶点在数组中的位置无现实意义,可减少算法时间复杂度。
增加边时,通过顶点寻址函数获取两个顶点位置,通过二维数组将邻接矩阵中对应的边权赋予新值即可。
删除边时,通过顶点寻址函数获取两个顶点位置,通过二维数组将邻接矩阵中对应的边权赋予MaxInt即可。
邻接矩阵打印,只需通过二维数组,将其各行各列依次输出,为了增加矩阵可观性,可输出行名、列名以及控制权重输出格式。
最后通过主函数测试上述所有的函数。
2、邻接表实现:
邻接表实现图的基本操作,主要通过数组+链表方式进行数据处理。函数包括:邻接表创建并存储数据、顶点寻址、增加顶点、删除顶点、增加边、删除边、邻接表打印。
邻接表创建并存储,先根据输入的总顶点数、边数对邻接表初始化,数组单元接收顶点信息,由于开始无边,将各单元firstarc指针赋NULL,避免野指针。存储边信息时,创建两个边结点并创建相应指针,在边结点中存储边权以及关联点通过顶点寻址函数查找的下标(如a、b两个顶点,则边结点e1中adjvex存放为b的下标,边结点e2中adjvex存放为a的下标)。并将边结点插入各自数组单元的关联顶点链表首结点(即被各单元firstarc指针指向)。
顶点寻址函数设计,只需根据顶点信息,在顶点数组集中遍历,返回其对应数组下标即可。
增加顶点,只需在邻接表数组单元vertices中存储新的顶点信息,并将其firstarc指针赋值为NULL。
删除顶点,下述操作:先删除待删顶点中所有关联顶点链表中其他顶点信息 ;用最后一个顶点替代删除结点位置(目的在于避免顶点表中出现废弃点占位情况)。实现操作需要遍历邻接表数组单元vertices中关联顶点链表中所有的adjvex,与待删顶点的位置下标比对,相同时删除该结点。结点删除时,需要单独优先考虑表头首结点元素中adjvex是否为待删结点下标,循环删除至表头结点adjvex不为待删结点下标为止,遍历后续所有结点(优先考虑的原因是表头结点有一个firstarc指向问题,不考虑则会出现断链情况)。删除完待删结点在其他单元的信息时,循环待删结点所在单元格关联顶点链表所有结点,将firstarc赋值为NULL。最后将数组vertices中最后一个顶点替代待删结点位置(数组前移覆盖会增加额外的开销)。
增加边即为上述邻接表存储步骤单次操作,通过创建两个边结点,分别赋值相应数据后,插入两个对应vertices单元格的关联顶点链表的表头(即成为首结点)。
删除边,即为删除顶点中单次操作,先定位待删边的两个顶点位置,然后遍历两个顶点对应数组vertices单元中的关联顶点链表,查找adjvex的值,删除含有对应顶点位置的边结点,同样注意单独考虑首结点是否含有删除对应顶点位置信息。
用于删除函数多次使用,因此在优化时,将输出函数提取。
邻接表打印时,依次访问vertices所有单元中的关联顶点链表,输出所有其中边结点的adjvex对应的顶点信息以及边权。
最后通过主函数测试上述所有函数。
三、代码展示1、邻接矩阵实现:
#includeusing namespace std;
typedef int Status;
#define OK 1
#define ERROR -1
#define MaxInt 32767 //初始化边权无穷大
#define MVNum 100
#define VerTexType char
#define ArcType int
typedef struct AMGraph{ //定义邻接矩阵
VerTexType vexs[MVNum]; //创建顶点集
ArcType arcs[MVNum][MVNum]; //创建邻接矩阵
int vexnum,arcnum; //存放当前图的总顶点数和边数
};
int VexLocate(AMGraph &G,VerTexType u){ //返回顶点在顶点集的位置
for(int i=0;i>G.vexnum>>G.arcnum; //输入图的顶点数和边数
cout<<"请输入顶点信息:";
for(int i=0;i>G.vexs[i];
}
for(int i=0;i>v1>>v2>>w; //依次输入两个顶点以及所构边的权重
G.arcs[VexLocate(G,v1)][VexLocate(G,v2)]=w;
G.arcs[VexLocate(G,v2)][VexLocate(G,v1)]=w;
}
return OK;
}
Status VexInsert(AMGraph &G,VerTexType v){ //插入顶点
G.vexs[G.vexnum]=v; //由于数组下标比数量少1,可用旧顶点数做下标
//增加新顶点
G.vexnum++; //顶点数加1
for(int i=0;i>v1;
VexInsert(G,v1); //插入顶点
AMGraphPrint(G); //打印无向邻接矩阵
cout<<"请输入要删除的顶点:";
cin>>v2;
VexDelete(G,v2); //删除顶点
AMGraphPrint(G); //打印无向邻接矩阵
cout<<"请输入增加边的两个顶点及边权重:";
cin>>v1>>v2>>w;
ArcInsert(G,v1,v2,w); //插入边
AMGraphPrint(G); //打印无向邻接矩阵
cout<<"请输入删除边的两个顶点:";
cin>>v1>>v2;
ArcDelete(G,v1,v2); //删除边
AMGraphPrint(G); //打印无向邻接矩阵
return 0;
}
2、邻接表实现:
#includeusing namespace std;
typedef int Status;
#define OK 1
#define ERROR -1
#define VerTexType char
#define ArcType int
#define MVNum 50
typedef struct ArcNode{ //边结点
int adjvex; //该边所指向的顶点位置
struct ArcNode* nextarc; //指向下一条边指针
int weight; //边的权重
};
typedef struct VNode{ //顶点信息
VerTexType data; //顶点数据
ArcNode *firstarc; //指向第一条与该点相连的边的指针
}VNode,AdjList[MVNum]; //邻接表
typedef struct{ //定义图
AdjList vertices; //顶点表
int vexnum,arcnum; //图当前顶点数与边数
}ALGraph;
int VexLocate(ALGraph &G,VerTexType v){ //顶点定位,找出其在邻接表
//中数组下标的位置
for(int i=0;iadjvex].data<<"("<weight<<")"<<"\t";
//输出与该顶点相连的所有点以及边的权重
p=p->nextarc;
}
cout<adjvex==pos2){ //由于firstarc指针固定,不能单纯删除p
//的结点,因此表头结点需要单独考虑
G.vertices[pos1].firstarc=p->nextarc; //如果表头结点存放连接信息为
//要删结点位置信息pos2,直接删除
delete p;
}
else{
while(p!=NULL){ //否则从p开始循环遍历表中所有连接点
if(p->nextarc!=NULL&&p->nextarc->adjvex==pos2){ //如果找到要删
//结点pos2,进行链表删除操作
ArcNode* temp=p->nextarc;
p->nextarc=p->nextarc->nextarc;
delete temp;
break;
}
p=p->nextarc; //没有找到,p指针后移
}
}
return OK;
}
Status UDGCreate(ALGraph &G){ //邻接表创建并存储数据
cout<<"请输入图的总顶点数和总边数:";
cin>>G.vexnum>>G.arcnum;
cout<<"请输入顶点信息:";
for(int i=0;i>G.vertices[i].data; //输入顶点数据
G.vertices[i].firstarc=NULL;
}
VerTexType v1,v2;
ArcType w;
int pos1,pos2;
cout<<"请输入边的两顶点及所构边的权重:"<>v1>>v2>>w;
pos1=VexLocate(G,v1); //获取顶点v1位置
pos2=VexLocate(G,v2); //获取顶点v2位置
ArcNode* p1=new ArcNode; //创建边结点
p1->adjvex=pos2; //v1开始的边所连另一端为v2位置
p1->weight=w;
p1->nextarc=G.vertices[pos1].firstarc;
G.vertices[pos1].firstarc=p1; //将边加入v1的边表头部
ArcNode* p2=new ArcNode; //创建边结点
p2->adjvex=pos1; //v2开始的边所连另一端为v1
p2->weight=w;
p2->nextarc=G.vertices[pos2].firstarc;
G.vertices[pos2].firstarc=p2; //将边加入v2的边表头部
}
return OK;
}
Status VexInsert(ALGraph &G,VerTexType v){ //实现顶点的插入
G.vertices[G.vexnum].data=v; //由于数组下标从0开始,则新增顶点存
//放位置为G.vexnum
G.vertices[G.vexnum].firstarc=NULL; //避免野指针情况,指针域为NULL
G.vexnum++; //顶点数自增
}
Status VexDelete(ALGraph &G,VerTexType v){ //顶点删除
int pos=VexLocate(G,v); //查找待删除顶点
for(int i=0;iadjvex==pos){
// G.vertices[i].firstarc=p->nextarc;
// delete p;
// }
// else{
// while(p!=NULL){
// if(p->nextarc!=NULL&&p->nextarc->adjvex==pos){
// ArcNode* temp=p->nextarc;
// p->nextarc=p->nextarc->nextarc;
// delete temp;
// break;
// }
// p=p->nextarc;
// }
// }
}
//下述操作:1、先删除待删顶点中所有连接表中其他顶点信息 2、用最后一个顶
//点替代删除结点位置(目的在于避免顶点表中出现废弃点占位情况)
ArcNode* p=G.vertices[pos].firstarc; //p指向待删顶点的第一个连接
//点的边的指针
G.vertices[pos].firstarc=NULL; //野指针问题,删除记得赋值为NULL,
//否则运行无结果
while(p!=NULL){ //循环删除该点连接表下所有顶点信息
ArcNode* temp=p;
p=p->nextarc;
delete temp;
}
G.vertices[pos]=G.vertices[G.vexnum-1]; //将最后一个顶点替代删除
//顶点的位置
G.vexnum--; //顶点数自减
return OK;
}
Status ArcInsert(ALGraph &G,VerTexType v1,VerTexType v2,int w){
//插入边
int pos1,pos2;
pos1=VexLocate(G,v1);
pos2=VexLocate(G,v2);
ArcNode* p1=new ArcNode; //创建边结点
p1->adjvex=pos2; //v1开始的边所连另一端为v2位置
p1->weight=w;
p1->nextarc=G.vertices[pos1].firstarc;
G.vertices[pos1].firstarc=p1;//将边加入v1的边表头部
ArcNode* p2=new ArcNode; //创建边结点
p2->adjvex=pos1; //v2开始的边所连另一端为v1
p2->weight=w;
p2->nextarc=G.vertices[pos2].firstarc;
G.vertices[pos2].firstarc=p2; //将边加入v2的边表头部
G.arcnum++; //边数自增
return OK;
}
Status ArcDelete(ALGraph &G,VerTexType v1,VerTexType v2){ //删除边
int pos1,pos2;
pos1=VexLocate(G,v1); //存放删除边的第一个顶点位置
pos2=VexLocate(G,v2); //存放删除边的第二个顶点位置
ArcNode* p1=G.vertices[pos1].firstarc; //指向第一个顶点的连接表中
//与该顶点相连的边的指针
ArcNode* p2=G.vertices[pos2].firstarc; //指向第二个顶点的连接表中
//与该顶点相连的边的指针
Delete(G,pos1,pos2); //在第一个顶点连接表中删除第二顶点的信息
Delete(G,pos2,pos1); //在第二个顶点连接表中删除第一顶点的信息
//下半部份代码用Delete()函数进行优化替代
// if(p1&&p1->adjvex==pos2){
// G.vertices[pos1].firstarc=p1->nextarc;
// delete p1;
// }
// else{
// while(p1!=NULL){
// if(p1->nextarc!=NULL&&p1->nextarc->adjvex==pos2){
// ArcNode* temp=p1->nextarc;
// p1->nextarc=p1->nextarc->nextarc;
// delete temp;
// break;
// }
// p1=p1->nextarc;
// }
// }
// if(p2&&p2->adjvex==pos1){
// G.vertices[pos2].firstarc=p2->nextarc;
// delete p2;
// }
// else{
// while(p2!=NULL){
// if(p2->nextarc!=NULL&&p2->nextarc->adjvex==pos1){
// ArcNode* temp=p2->nextarc;
// p2->nextarc=p2->nextarc->nextarc;
// delete temp;
// break;
// }
// p2=p2->nextarc;
// }
// }
G.arcnum--; //边数自减
return OK;
}
int main(){
ALGraph G;
UDGCreate(G); //构建图
ALGraphprint(G); //打印图
VerTexType v1,v2;
int w;
cout<<"请输入要插入的顶点:";
cin>>v1;
VexInsert(G,v1); //插入顶点
ALGraphprint(G);
cout<<"请输入要删除的顶点:";
cin>>v1;
VexDelete(G,v1); //删除顶点
ALGraphprint(G);
cout<<"请输入要插入边的两顶点及边权重:";
cin>>v1>>v2>>w;
ArcInsert(G,v1,v2,w); //插入边
ALGraphprint(G);
cout<<"请输入要删除边的两顶点:";
cin>>v1>>v2;
ArcDelete(G,v1,v2); //删除边
ALGraphprint(G);
return 0;
}
四、结果展示1、邻接矩阵结果:
2、邻接表结果:
五、算法时间复杂度1、邻接矩阵实现图的基本操作,函数包括:邻接矩阵创建并存储数据、顶点寻址、增加顶点、删除顶点、增加边、删除边、邻接矩阵打印。其中操作建立于二维数组,与数据规模有关,设总顶点数与总边数数据规模为n,则总体算法时间复杂度为O(n2)。
2、邻接表实现图的基本操作,主要通过数组+链表方式进行数据处理。函数包括:邻接表创建并存储数据、顶点寻址、增加顶点、删除顶点、增加边、删除边、邻接表打印。其中操作主要建立于链表上,与数据规模有关,设总顶点数与总边数数据规模为n,则总体算法时间复杂为O(n)。
PS:第一次写博客,有问题欢迎交流。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网页名称:【数据结构】图的基本操作-创新互联
文章来源:http://scyanting.com/article/dhpppe.html